Выводы: (Понятие алгоритма)
• Не для всякой массовой проблемы существует алгоритм;
• Для одной и той же проблемы могут существовать разные алгоритмы с разной сложностью;
• Алгоритм определяет последовательность действий;
• Данные, алгоритм и вычислительный процесс - конструктивные объекты;
• Исходные данные образуют класс, описываемый некоторым языком;
• Алгоритм и исходные данные определяют вычислительный процесс полностью;
• При одних и тех же исходных данных алгоритм всегда дает один и тот же результат;
• Алгоритм одинаково понимается всеми исполнителями.
• Исполнение алгоритма всегда заканчивается.
Формализация понятия А. Каждый А характеризуется 7 основными параметрами:
1) Совокупность возможных исходных данных (алфавит исходных данных).
2) Совокупность возможных результатов (алфавит результатов).
3) Совокупность возможных промежуточных результатов (алф промеж результатов).
4) Множество действий. 5) Правило начала. 6) Правило окончания.
7) Правило определения расположения результата.
Символом будем называть любой печатный знак. Алфавитом называется любое конечное множество символов. Словом назовем конечную последовательность символов из алфавита. Длиной слова называется число символов в слове. Объектом алгоритма называются слова в некотором заданном алфавите.
Входное слово--алгоритм--выходное слово.
НАМ - один из стандартных способов формального определения понятия алгоритма.
- конечный непустой упорядоченный набор формул подстановки:
ì a1 à b1
í a2 à b2 k ³ 1
÷ …
î ak à bk Определяется сл. образом:
1. Совокупность исходных данных - слова в алфавите S;
2. Совокупность возможных результатов - слова в алфавите W;
3. Совокупность возможных промежуточных результатов - слова в
алфавите P = SÈWÈV, где V - алфавит служебных вспомогательных символов.
4. Действия имеют вид либо a—>b, либо а /->b, где a ,b ÎР', где
Р’ - множество слов над алфавитом Р, и называется правилом
подстановки. Смысл этого правила состоит в том, что обрабатываемое
слово w просматривается слева направо и ищется вхождение в него
слова а.
5 Правило начала - просмотр правил всегда начинается с первого.
6 Правило окончания - выполнение алгоритма заканчивается, если:
• было применено правило подстановки вида а /-> у,
• не применимо ни одно правило подстановки из схемы алгоритма.
7 Правило размещения результата - слово, полученное после окончания выполнения алгоритма.
НАМ называется применимым к входному слову a, если он останавливается на этом слове, и неприменимым – если зацикливается. Множество входных слов, к которым НАМ применим называется его областью применимости.
Тезис Маркова: Для любой интуитивно вычислимой ф-ции сущ НАМ, ее вычисляющий. Принцип нормализации: 1. Объекты любой природы могут быть предст. словами 2. Сколь угодно сложный процесс преобразования слов можно предст в виде НАМ.
МТ – более развито управление, но можно изменять только один символ.
НАМ – жестко фиксированное управление. Две алгоритмические сист наз эквивалентными, если множество алг., котор. можно описать в первой системе равно множ алг, кот можно описать во второй системе. МТ и НАМ несмотря на их различия эквивалентны.
Взаимосвязь алгоритмических систем: Для любой алгоритмической системы существует универсальный исполнитель, который есть интерпретатор множества действий заданной алгоритмической системы;
• В силу тезиса Тьюринга, любой алгоритм реализуем в терминах действий последовательной, параллельной композиций, выбора и цикла и базового набора действий; • Если алгоритмическая проблема не разрешима, то она не разрешима в любой другой эквивалентной алгоритмической системы;
Об универсальных алгоритмах: Идея универсальных машин и алгоритмов широко используется в компьютерах. По существу программы (алгоритмы) почти никогда не пишутся в системе команд компьютера. Программы пишут программы для некоторой абстрактной машины. Причем все эти представления ориентированы на бесконечные машины. На конечных машинах возникает новый тип останова, когда для выполнения программы не хватает памяти. На самом деле так было бы и для МТ, если бы лента МТ, была ограничена. В этой связи алгоритмическая неразрешимость утрачивает смысл. Действительно, эти проблемы связаны с бесконечностью ленты Тьюринга (хотя любая машина использует конечное число клеток ленты, но всегда найдется машина, которая использует на клетку больше – нет верхней границы), аналогично, со словом в алгоритмах Маркова. Ведь опасность может быть в объеме памяти, когда нельзя выполнить программу на данном компьютере из-за нехватки памяти. Другая опасность – время. Выполнение может занять много времени. В силу гипотезы Тьюринга существует машина Тьюринга Т U, способная выполнить работу любой машины Тьюринга над любым заданным словом или, как говорят, способная моделировать любую машину Тьюринга. Машина Т U называется универсальной.
Сложностью алгоритма для набора исходных данных называется количество действий в вычислительном процессе, порождаемом этим алгоритмом на этом наборе данных.
Для того чтобы сравнивать сложность разных алгоритмов, надо чтобы она подсчитывалась для них в терминах одинаковых действий. Например, умножь, сложи.
Алгоритм как функция, преобразующая входные данные (описание одного или нескольких объектов из пространства объектов) и вектор параметров в выходные данные (ответы или прогнозы из множества допустимых ответов для каждого из входных объектов).
Задача обработки информации – это задача построения частичного отображения (функции) F: A * → A *.
Трансля́тор — программа или техническое средство, выполняющее трансляцию программы. Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати тексты программы и т. д.
Трансляция программы — преобразование программы, представленной на одном из языков программирования, в программу на другом языке и, в определённом смысле, равносильную первой.
Формальный язык — это множ конечных слов (строк, цепочек) над конечным алфавитом.
Чтобы осуществить вычисление, нужно записать алгоритм на специальном языке, понятном машине. Такой язык называется машинным языком, а запись алгоритма на машинном языке – машинной программой. Машинный язык не удобен для человека, поскольку является совокупностью двоичных цепочек (слов) – последовательностей из нулей и единиц разной длины.
С развитием программирования появились более удобные для человека способы записи алгоритмов – алгоритмические языки или языки программирования высокого уровня.
Одним из преимуществ алгоритмического языка является то, что он является переносимым, т. е. одну и ту же программу на алгоритмическом языке можно перевести в машинные программы разных компьютеров и запустить на них.
Алгоритмический язык образуют три компоненты: алфавит, синтаксис, семантика.
Алгоритмы, которые применимы к своей записи, называются самоприменимыми.
Понятие алг неразрешимости: Не существует алгоритма, который по записи любого алгоритма определял бы, самоприменим он или нет.
Выходное слово одного алгоритма Н1 можно подать на вход другому алгоритму Н2. Такое последовательное выполнение сначала алгоритма Н1, а затем алгоритма Н2 называется композицией этих алгоритмов. При этом, правда, надо учитывать, что любой из этих алго-
ритмов может зацикливаться, тогда должна зацикливаться и их композиция.
Эти соображения приводят к следующему определению: Композицией алгоритмов H1 и H2 относительно алфавита A называется такой алгоритм H (обозначается Н1 ° Н2 или H2 (H1)), что для любого слова P в алфавите A выполняются следующие условия:
1) если Н1 неприменим к Р, то и Н неприменим к Р;
2) если Н1 применим к Р, но Н2 неприменим к слову Н1 (Р), то и Н непри-
меним к Р; 3) если Н1 применим к Р и Н2 применим к слову Н1 (Р), то Н применим к Р,
причём выполняется равенство Н (Р)= Н2 (Н1 (Р)).
Доказана следующая теорема: для любых нормальных алгоритмов Н1 и Н2
существует нормальный алгоритм Н, который является (относительно соответствующего алфавита) композицией Н1 и Н2. (Аналогичная теорема верна и для машины Тьюринга.)
Параллельная композиция A||B
A(P||R)°B = B(P||R)°A = B(P) || A(R)
Алфавит – набор символов языка. В программах на алгоритмическом языке допускается использовать только символы алфавита и никакие другие.
Синтаксис – набор правил, по которым строятся фразы (конструкции) языка. Эти правила задают допустимые в языке последовательности символов языка (тексты). Недопустимые тексты не могут быть переведены в машинные программы и отвергаются транслятором.
Семантика – набор правил, определяющих смысл каждой конструкции языка. Семантика обеспечивает детерминированность программы, т. е. однозначность порождаемого вычислительного процесса на фиксированных исходных данных.
Для описания синтаксиса алгоритмических языков используются специальные языки, так называемые метаязыки («надъязыки»). Это необходимо для строгого формального описания синтаксиса. При помощи метаязыка каждая конструкция описываемого языка определяется как некоторое понятие, составленное из символов языка и других понятий. Примеры понятий языка: программа, оператор, имя. Семантика языков описывается на естественном (человеческом) языке или при помощи логических исчислений. Рассмотрим два метаязыка для описания синтаксиса: металингвистические формулы и синтаксические диаграммы.
Металингвистические формулы известны также как Бэкуса-Наура формулы (БНФ) или метаформулы. Метаформула состоит из двух частей: левой, в которой указывается описываемое понятие языка (метапеременная), и правой, в которой указывается синтаксическая структура понятия. Т. е. ЛЧ::= ПЧ. Метасимвол::= читается как «по определению есть». В правой части используются символы языка, символы метаязыка (метасимволы): |, {, }, [, ], (,), а также другие понятия (метапеременные). Чтобы отличать метапеременные от символов и цепочек символов языка, они всегда заключены в угловые скобки. Например: <имя>, <программа>.
| <переменная>::= A | B | Переменной является либо символ A либо B |
Иногда понятие определяется через само себя:
<двоичный код>::= <двоичная цифра> | <двоичный код> <двоичная цифра>
Вторым метаязыком являются синтаксические диаграммы. На диаграммах синтаксис задается графически. Узлами диаграммы являются либо цепочки символов языка (заключаются в овалы), либо метапеременные (заключаются в прямоугольники). В узел могут входить стрелки из других узлов, указывая, что его содержимое следует за содержимым этих узлов. В свою очередь, стрелки, выходящие из узла, указывают на то, что может следовать за его содержимым.
| A |
| В |
АЛГОРИТМ ЕВКЛИДА:
Исполнитель алгоритма — это некоторая система, способная выполнить действия, предписываемые алгоритмом. Характеристики исполнителя: сpеда — это "место обитания" исполнителя;
· элементаpные действия — после вызова команды исполнитель совеpшает соответствующее элементаpное действие;
· cистема команд — некий строго заданный список команд, с заданными условиями применимости и описанными результатами выполнения команды;
· отказы — возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.
В информатике универсальным исполнителем алгоритмов является компьютер.
Исполнитель алгоритма — это устройство управления, соединенное с набором инструментов. Устройство управления понимает алгоритмы и организует их выполнение, командуя соответствующими инструментами.
Машина Тьюринга – абстрактная вычислительная машина для формализации понятия алгоритма.
Исполнитель алгоритмов - автомат, состоящий из:
• бесконечной ленты, разбитой на ячейки (в каждой ячейке--один символ из определенного множества символов, называемого алфавитом);
• каретки(головка), способной передвигаться над лентой, от ячейки к ячейке, считывать символы, записанные на ленте, записывать символы в ячейки.
За одно срабатывание головка способна выполнить следующие действия:
• считать символ из ячейки, над которой она находится;
• записать символ в ячейку, над которой она находится;
• переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте.
• изменять свое внутреннее состояние.
1. Совокупность возможных исходных данных - алфавит А;
2. Совокупность возможных результатов - алфавит А,
3. Совокупность возможных промежуточных результатов - алфавит D,
4. Множество действий: множество правил вида ар—>bqw, где a,bÎА; р,qÎQ; wÎ{Л, П, Н}.
А - алфавит символов, которые могут появляться на ленте;
Q - множество символов, обозначающих состояния головки.
Л, П, Н - символы, обозначающие передвижение головки налево, направо или на месте соответственно.
Смысл правила ар—bqw состоит в следующем. Если головка находится над ячейкой, в которой записан символ а, и головка находится в состоянии p, то головка должна:
записать в эту ячейку символ b (символ а при этом стирается), из состояния р перейти в состояние q, переместиться на следующую ячейку влево если w =Л, - вправо, если w =п или остаться на месте если w=н.
5. Правило начала: головка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии q0;
6. Правило окончания: есть специальное состояние, мы его будем обозначать символом! из алфавита Q. Как только головка переходит в состояние!, она останавливается.
Например, если правило имеет вид ар—>b!w, то после его выполнения
вычисление считается законченным.
7. Правило расположения результата: справа от головка до первого символа пустоты.
Тезис Тьюринга –Черча. Для любой интуитивно вычислимой функции существует вычисляющая её значения машина Тьюринга.
Это тезис, не теорема. Его нельзя доказать, так как в нем используется понятие алгоритма, смысл которого определен интуитивно, т.е. не строго.