Курсовая работа - Теория алгоритмов. Разработка эффективных алгоритмов

Подождите немного. Документ загружается.

ВВЕДЕНИЕ

Актуальность темы

Тео́рия алгори́тмов — наука, изучающая общие свойства и

закономерности алгоритмов и разнообразные формальные модели их

представления. К задачам теории алгоритмов относятся формальное

доказательство алгоритмической неразрешимости задач, асимптотический

анализ сложности алгоритмов, классификация алгоритмов в соответствии с

классами сложности, разработка критериев сравнительной оценки качества

алгоритмов и т. п.

Машина Тьюринга является расширением конечного автомата и, согласно

тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с

помощью задания правил перехода), каким-либо образом реализующие процесс

пошагового вычисления, в котором каждый шаг вычисления достаточно

элементарен.

“Машина Тьюринга за данный большой, но конечный промежуток времени

способна справиться с любым вычислением, которое может выполнить всякий

сколь угодно мощный современный, компьютер”.

Понятие алгоритма

Алгори́тм— точный набор инструкций, описывающих порядок действий

исполнителя для достижения результата решения задачи за конечное время. В

старой трактовке вместо слова «порядок» использовалось слово

«последовательность», но по мере развития параллельности в работе

компьютеров слово «последовательность» стали заменять более общим словом

«порядок». Это связано с тем, что работа каких-то инструкций алгоритма

может быть зависима от других инструкций или результатов их работы. Таким

образом, некоторые инструкции должны выполняться строго после завершения

работы инструкции, от которых они зависят. Независимые инструкции или

инструкции ставшими независимыми из-за завершения работы инструкций, от

которых они зависят, могут выполняться в произвольном порядке, параллельно

или одновременно, если это позволяет используемые процессор и операционная

система.

Признаки алгоритмов

Различные определения алгоритма в явной или неявной форме содержат

следующий ряд общих требований:

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Дискретность — алгоритм должен представлять процесс решения задачи

как последовательное выполнение некоторых простых шагов. При этом для

выполнения каждого шага алгоритма требуется конечный отрезок времени, то

есть преобразование исходных данных в результат осуществляется во времени

дискретно.

Детерминированность — определённость. В каждый момент времени

следующий шаг работы однозначно определяется состоянием системы. Таким

образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же

исходных данных. В современной трактовке у разных реализаций одного и того

же алгоритма должен быть изоморфный граф. С другой стороны, существуют

вероятностные алгоритмы, в которых следующий шаг работы зависит от

текущего состояния системы и генерируемого случайного числа. Однако при

включении метода генерации случайных чисел в список «исходных данных»,

вероятностный алгоритм становится подвидом обычного.

Понятность — алгоритм для исполнителя должен включать только те

команды, которые ему (исполнителю) доступны, которые входят в его систему

команд.

Завершаемость (конечность) — при корректно заданных исходных

данных алгоритм должен завершать работу и выдавать результат за конечное

число шагов. С другой стороны, вероятностный алгоритм может и никогда не

выдать результат, но вероятность этого равна 0.

Массовость — алгоритм должен быть применим к разным наборам

исходных данных.

Результативность — завершение алгоритма определёнными результатами.

Алгоритм содержит ошибки, если приводит к получению неправильных

результатов либо не даёт результатов вовсе.

Алгоритм не содержит ошибок, если он даёт правильные результаты для любых

допустимых исходных данных.

Структуры данных и их представление в памяти ЭВМ

Любые данные могут быть отнесены к одному из двух типов: основному

(простому), форма представления которого определяется архитектурой ЭВМ,

или сложному, конструируемому пользователем для решения конкретных

задач.

Данные простого типа это - символы, числа и т.п. элементы, дальнейшее

дробление которых не имеет смысла. Из элементарных данных формируются

структуры (сложные типы) данных.

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Некоторые структуры:

Массив(функция с конечной областью определения) - простая

совокупность элементов данных одного типа, средство оперирования группой

данных одного типа. Отдельный элемент массива задается индексом. Массив

может быть одномерным, двумерным и т.д. Разновидностями одномерных

массивов переменной длины являются структуры типа кольцо, стек, очередь и

двухсторонняя очередь.

Запись(декартово произведение) - совокупность элементов данных разного

типа. В простейшем случае запись содержит постоянное количество элементов,

которые называют полями. Совокупность записей одинаковой структуры

называется файлом. (Файлом называют также набор данных во внешней

памяти, например, на магнитном диске). Для того, чтобы иметь возможность

извлекать из файла отдельные записи, каждой записи присваивают уникальное

имя или номер, которое служит ее идентификатором и располагается в

отдельном поле. Этот идентификатор называют ключом.

Такие структуры данных как массив или запись занимают в памяти ЭВМ

постоянный объем, поэтому их называют статическими структурами. К

статическим структурам относится также множество.

Имеется ряд структур, которые могут изменять свою длину - так

называемые динамические структуры. К ним относятся дерево, список, ссылка.

Важной структурой, для размещения элементов которой требуется

нелинейное адресное пространство является дерево. Существует большое

количество структур данных, которые могут быть представлены как деревья.

Это, например, классификационные, иерархические, рекурсивные и др.

структуры.

Классификация типов данных.

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Эффективность алгоритмов и методы её достижения.

Наличие исходных данных и некоторого результата

Алгоритм — это точно определённая инструкция, последовательно

применяя которую к исходным данным, можно получить решение задачи. Для

каждого алгоритма есть некоторое множество объектов, допустимых в качестве

исходных данных. Например, в алгоритме деления вещественных чисел

делимое может быть любым, а делитель не может быть равен нулю.

Алгоритм служит, как правило, для решения не одной конкретной задачи, а

некоторого класса задач. Так, алгоритм сложения применим к любой паре

натуральных чисел. В этом выражается его свойство массовости, то есть

возможности применять многократно один и тот же алгоритм для любой задачи

одного класса.

Для разработки алгоритмов и программ используется алгоритмизация —

процесс систематического составления алгоритмов для решения поставленных

прикладных задач. Алгоритмизация считается обязательным этапом в процессе

разработки программ и решении задач на ЭВМ. Именно для прикладных

алгоритмов и программ принципиально важны детерминированность,

результативность и массовость, а также правильность результатов решения

поставленных задач.

Форма алгоритмов

Алгоритм может быть записан словами и изображён схематически. Обычно

сначала (на уровне идеи) алгоритм описывается словами, но по мере

приближения к реализации он обретает всё более формальные очертания и

формулировку на языке, понятном исполнителю (например, машинный код).

Например, для описания алгоритма применяются блок-схемы. Другим

вариантом описания, не зависимым от языка программирования, является

псевдокод.

Эффективность алгоритмов

Хотя в определении алгоритма требуется лишь конечность числа шагов,

требуемых для достижения результата, на практике выполнение даже хотя бы

миллиарда шагов является слишком медленным. Также обычно есть другие

ограничения (на размер программы, на допустимые действия). В связи с этим

вводят такие понятия как сложность алгоритма (временна́я, по размеру

программы, вычислительная и др.).

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Для каждой задачи может существовать множество алгоритмов,

приводящих к цели. Увеличение эффективности алгоритмов составляет одну из

задач современной информатики. В 50-х гг. XX века появилась даже отдельная

её область — быстрые алгоритмы. В частности, в известной всем с детства

задаче об умножении десятичных чисел обнаружился ряд алгоритмов,

позволяющих существенно ускорить нахождение произведения.

Машина Тьюринга

Машина Тьюринга (МТ) — математическая абстракция, представляющая

вычислительную машину общего вида. Была предложена Аланом Тьюрингом в

1936 году для формализации понятия алгоритма.

Алан Матисон Тьюринг

Машина Тьюринга является расширением модели конечного автомата и,

согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии

соответствующей программы) любую машину, действие которой заключается в

переходе от одного дискретного состояния к другому.

В состав Машины Тьюринга входит бесконечная в обе стороны лента,

разделённая на ячейки, и управляющее устройство с конечным числом

состояний.

Управляющее устройство может перемещаться влево и вправо по ленте,

читать и записывать в ячейки символы некоторого конечного алфавита.

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех

из них (конечного числа), на которых записаны входные данные.

В управляющем устройстве содержится таблица переходов, которая

представляет алгоритм, реализуемый данной Машиной Тьюринга. Каждое

правило из таблицы предписывает машине, в зависимости от текущего

состояния и наблюдаемого в текущей клетке символа, записать в эту клетку

новый символ, перейти в новое состояние и переместиться на одну клетку

влево или вправо. Некоторые состояния Машины Тьюринга могут быть

помечены как терминальные, и переход в любое из них означает конец работы,

остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой

комбинации состояния и ленточного символа в таблице соответствует не более

одного правила, и недетерминированной в противном случае.

Краткое содержание курсовой работы.

В данной курсовой работе будут рассмотрены такие темы как:

• Опрелеление алгоритма, его значение, виды алгоритмов, типы алгоритмов.

• Эффективность алгоритмов и методы её достижения.

• Построение линейных, циклических и алгоритмов с разветвлением.

• Примеры решения задачи с помощью алгоритма.

• Определение теории алгоритмов.

• Машина Тьюринга, устройство машины, ее описание.

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Разработка эффективных алгоритмов

Алгоритмические структуры (типы алгоритмов)

В рамках структурного программирования задачи, имеющие

алгоритмическое решение, могут быть описаны с использованием следующих

алгоритмических структур:

Следование. Предполагает последовательное выполнение команд сверху

вниз. Если алгоритм состоит только из структур следования, то он является

линейным.

Ветвление. Выполнение программы идет по одной из двух, нескольких или

множества ветвей. Выбор ветви зависит от условия на входе ветвления и

поступивших сюда данных.

Цикл. Предполагает возможность многократного повторения определенных

действий. Количество повторений зависит от условия цикла.

Функция (подпрограмма). Команды, отделенные от основной программы,

выполняются лишь в случае их вызова из основной программы (из любого ее

места). Одна и та же функция может вызываться из основной программы сколь

угодно раз.

Линейный алгоритм

Любой вычислительный процесс может быть представлен как комбинация

этих элементарных алгоритмических структур. Соответственно,

вычислительные процессы, выполняемые на ЭВМ по заданной программе,

можно разделить на три основных вида:

линейные;

ветвящиеся;

циклические.

Линейный алгоритм (линейная структура) – это такой алгоритм, в котором

все действия выполняются последовательно друг за другом и только один раз.

Схема представляет собой последовательность блоков, которые располагаются

сверху вниз в порядке их выполнения. Первичные и промежуточные данные не

оказывают влияния на направление процесса вычисления.

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Задание 1

Вычислить значения переменных по заданным формулам, при заданных

значениях переменных a,b,x.

а)

б)

Словесное описание к заданию 1(а).

1. x+1 = A1

2. x+a = A2

3. x² = A3

4. sin A2 = A4

5. A3*A1 = A5

6. A²4 = A6

7. A5/b = A7

8. A7-A6 = R

Словесное описание к заданию 1(б).

1. x*b=A1

2. A1/a=A2

3. x+b=A3

4. √A2 = A4

5. A²3= A5

6. cos A5=A6

7. A²6=A7

8. A4+A7=S

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Начало

x,b,a

конец

Начало

x,b,a

A1 A2 A3

A4 A5

A6 A7

конец

а)

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Змн. Арк.

Арк.

№ докум. Підпис Дата

Арк.

КР.КС.39.19.00.ПЗ

Начало

x,b,a

конец

Начало

x,b,a

A1 A3

конец

б)