Лекции 3—5. Формализация понятия алгоритма (1107980)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекции 3 – 5 Формализация понятия алгоритма1. Неформальное (интуитивное) определение алгоритма.1.1. Определение. Под алгоритмом в математике понимают точное предписание, задающеевычислительный процесс, ведущий от начальных данных, которые могут варьироваться, к искомому результату.
Синоним алгоритма – вычислительная (эффективная) процедура, которая после какого-либо числа шагов (вычислений) приводит к решению поставленной задачи. При этом в интуитивном определении алгоритма слова “вычисления”, “вычислительный процесс” понимаются в широком смысле как любой процессобработки информации: вычисление некоторой величины, поиск решения некоторой(математической) задачи, четкое и ясное предписание по обработке информации.1.2. Замечание. В рамках данного курса понятие информации считается интуитивно ясными не дается определения этого понятия. При этом необходимо уточнить, что, имея ввиду обработку информации на компьютере, рассматривается только такая информация, которую можно задать в дискретном виде, т.е. конечным числом отдельных знаков(символов). В рамках такого ограничения, предполагается, что в дискретном виде можно задать любую информацию.
Более точно: любую информацию в задачах обработкиинформации можно "подменить" дискретной информацией. Например, цветную картину можно изобразить в виде описания цветов и фактуры пусть большого, но конечногочисла отдельных точек (растровое изображение).
Следует отметить, что предположение о возможности дискретного представления информации подкреплено тысячелетиями проверенной практикой использования человечеством письменности.1.3. Основные свойства интуитивно определенного алгоритма.(1) Конечность (результативность). Алгоритм должен заканчиваться за конечное число шагов и получать результат, обеспечивая решение тех задач, для которых он и создавался. Хотя число шагов не ограничено сверху.(2) Определенность (детерминированность). Каждый шаг алгоритма и переход от шагак шагу должны быть точно определены и каждое применение алгоритма к одним итем же исходным данным должно приводить к одинаковому результату.(3) Простота и понятность. Каждый шаг алгоритма должен быть четко и ясно определен, чтобы выполнение алгоритма можно было “поручить” любому исполнителю(человеку или механическому устройству).(4) Массовость.
Алгоритм задает процесс вычисления для множества исходных данных (чисел, строк букв и т.п.), он представляет общий метод решения класса задач.Не имеет смысла строить, например, алгоритм нахождения НОД только для чисел10 и 15.1.4. Основной недостаток интуитивного определения – не определены базовые понятия: конечность (допустимы ли ситуации бесконечного зацикливания), исходные данные (какие исходные данные допустимы, как они представляются), результат, исполнитель(что значит можно поручить любому исполнителю), класс задач и др.2. Пример: Алгоритм Евклида нахождения наибольшего общего делителя двух целых положительных чисел НОД(а, b) (в геометрической форме это алгоритм нахождения общеймеры двух отрезков).Даны два целых числа а и b.
Алгоритм Евклида состоит в выполнении следующих шагов:(1) Разделить нацело а на b; получить остаток r.1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год(2) Если r = 0, то НОД(а, b) = b(3) Если r ≠ 0, заменить: а на b, b на r и возвратиться к шагу (1).3. Почему необходимо формальное определение алгоритма.
После того, как в 30-е годы прошлого века была доказана алгоритмическая неразрешимость некоторых задач в разных разделах математики, возникла совершенно новая ситуация. До тех пор, пока ученые верили ввозможность построения алгоритмов для всех поставленных задач, не было повода уточнять интуитивное понятие алгоритма. Доказательство существования алгоритмически неразрешимых проблем означало, что существуют классы задач, для решения которых алгоритм не просто не найден, а его не будет найдено никогда.
В отличие от конкретных алгоритмов, доказательство алгоритмической неразрешимости, т.е. доказательство невозможности, в котором содержалось бы высказывание обо всех мыслимых алгоритмах, потребовалоформального уточнения понятия «алгоритм». Не имея формального определения, невозможно говорить обо всех мыслимых алгоритмах.4. Для формального определения алгоритма требуется предварительно рассмотреть некоторыеобщие понятия, часто используемые в математике.4.1. Множество.
Элемент множества. Примеры множеств.4.2. Мощность множества. Понятие подмножества. Операции над множествами.4.3. Декартово произведение множеств. Отображение множеств.4.4. Частично определенная функция.5. Алфавиты и отображения.5.1. Алфавит – конечное множество Ap элементов ai: Ap = {a1, a2, …, ap}. Элементы алфавита Ap называются символами. Последовательность m символов алфавита Ap называетсясловом длины m над алфавитом Ap. Слово длины 0 называется пустым словом и обозначается ε.5.2. Слово длины 2 над алфавитом Ap можно рассматривать как символ декартова произведения алфавита Ap на себя: если ai ∈ Ap и aj ∈ Ap, то aiaj ∈ Ap × Ap = Ap2.
Следовательно,0*если определить {ε} = Ap , то множество Ap всех слов над алфавитом An можно представить в виде объединения множеств:∞mm= 0pA*p = {ε } ∪ Ap ∪ Ap2 ∪ ... ∪ Apm ∪ ... = ∪ A∞В объединении m∪= 0 Amp– бесконечно много членов, но бесконечность здесь не актуаль-ная (как в математическом анализе), а потенциальная в том смысле, что допустимы*слова произвольно большой длины. Длину слова w ∈ Ap будем обозначать |w|. Итак,A*p является счетным множеством (в смысле потенциальной бесконечности).5.3.
Если в алфавит A включить не только буквы (например, латинские и русские, строчныеи прописные), но и цифры, знаки препинания, такие символы как «конец строки», «конец страницы», «знак абзаца», «знак табуляции» и т.п., то любой текст (страницу лю-2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годбой книги или даже всю книгу)1 можно представить в виде слова над алфавитом A (илив виде символа алфавита A* ).5.4. Кодирование: представление символов алфавита A словами над алфавитом B.Утверждение.
Для любой пары алфавитов A и B существует простой алгоритм, определяющий взаимно-однозначное отображение A* ↔ B* .В самом деле, пусть для определенности |A| > |B|. Будем представлять символы алфавита A словами над алфавитом B (первые |B| символов – однобуквенными словами, следующие |B| символов – двухбуквенными и т.д.). При этом может понадобиться дополнительный символ ι («конец кода символа»).
Обратное отображение очевидно.Из утверждения следует, что любой алфавит, в том числе и двухсимвольный алфавит A2(символы 0 и 1) и даже односимвольный алфавит A1 (обычно в качестве единственногосимвола алфавита A1 используется («палочка»)), пригоден для представления любоготекста.Отметим, что кодирование позволяет ограничиться одним алфавитом. В теории алгоритмов в качестве такого алфавита обычно рассматриваются A1 или A2.6. Задача обработки информации.6.1.
Задача обработки информации – это задача построения частичного отображения (функции) F : A* → A* .Любой алгоритм можно рассматривать как набор правил, позволяющих реализоватьтребуемое частичное отображение на множестве слов конечного алфавита А.6.2. Нумерация. Каждому элементу (слову) множества A* можно присвоить его номер –неотрицательное целое число.Утверждение. Существует взаимно-однозначное отображение (функция) # : A* → N ,*где N – множество целых неотрицательных чисел, которое любому слову w ∈ A ставит в соответствие его номер n ∈ N.(1) Построение отображения. Пустому слову ε присваивается номер 0 (#(ε) = 0). Каждому односимвольному слову w = ai ∈ A*p присваивается номер i (i = 1, 2, … p).
Произвольному слову w = ai0 ai1 ...aim длины m присваивается номерm#(w) = i0 + p⋅i1 + p ⋅i2 +… + p ⋅im =2m∑s= 0p s ⋅ is (is – номер односимвольного*слова ais ∈ Ap ).(2) Обратное отображение # − 1 строится очевидным образом.6.3. Нумерация позволяет каждой частичной функции F : A* → A* единственным образомпоставить в соответствие частичную числовую функцию f : N → N . В самом деле,1Здесь не указано количество символов алфавита A, это означает, что рассматривается алфавит с произвольнымколичеством символов, либо алфавит, точное количество символов которого не представляет интереса.3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годесли v = F(w), то # (v) = # ( F ( w)) = # ( F (#− 1 (# ( w)))) = (#− 1°F °# )(# ( w)) = f (# ( w)) , следовательно, #(v) = f(#(w)), где f = # − 1°F °# 2.Аналогичным образом можно установить, что F = # ° f ° # − 1 .Связь частичных функций F и f можно представить в виде двух коммутативных диаграмм:A*FA*#-1#NfNfNN#-1#FA*A*Таким образом, показано что:(1) Каждый алгоритм F : A* → A* определяет частично вычислимую функциюf :N → N(2) Каждая частично вычислимая функцияf :N → Nопределяет алгоритмF : A* → A*7.
Машина Тьюринга.7.1. Основная идея предложенного Тьюрингом подхода к уточнению понятия алгоритма, заключается в том, что алгоритмами должны называться те и только те отображенияF : A* → A* , которые могли бы осуществлять достаточно простые машины-автоматы.Выполнение отображения понимается при этом следующим образом: машине-автомату*предъявляется любое исходное слово w ∈ A , а она в результате обработки этого слова«выдает» слово v = F(w). Таким образом, каждая машина Тьюринга (МТ) строит отображение F : A* → A* для соответствующей функции F.
При этом каждая частичнаяфункция F, для которой можно построить МТ называется вычислимой по Тьюрингу. МТ,вычисляющую функцию F, будем обозначать TF.7.2. Для задания МТ необходимо задать алфавит состояний Q = {q0, q1, q2, …, qn} и рабочий алфавит S = A ∪ A', где A – алфавит входных символов, A' – алфавит вспомогательных символов (маркеров), который, в частности, может быть пустым.У МТ есть внешняя память – лента, размеченная на ячейки, каждая из которых можетбыть «пустой» (пустая ячейка представляется символом Λ (лямбда большое)), либо содержать один символ рабочего алфавита S. МТ связана с лентой посредством управ2Операция° означает композицию (последовательное применение) функций. По определению (f ° g)(x) = g(f(x)).4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годляющей головки (УГ), которая в каждый данный момент располагается под некоторойячейкой ленты (эта ячейка называется обозреваемой ячейкой (ОЯ).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
