Теория алгоритмов

Лекция Теория алгоритмов  Современная история математики большую роль формированию алгебры в том виде, который мы имеем сейчас, относит к трудам ал-Хорезми, арабского учёного,  «Слово “алгорифм” в форме “алгоризм” часто употреблялось в качестве заглавия изложений индийского счисления в рукописях XII–XV вв. и в книгах XV–XVI вв.». Свои трактаты ал-Хорезми начинал со слов «dixit algorizmi», что означает «Говорит алХорезми    Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть выражено через другие ,а должно рассматриваться как неопределяемое . Алгоритм — это точное предписание, которое задаёт вычислительной процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемого этим исходным данным результата .(определение Маркова)  Формулировка Колмогорова содержит две существенные идеи:  итеративность алгоритмического процесса  локальность каждого отдельного шага. Теория алгоритмов - раздел математики, изучаю щий общие свойства алгоритмов.  Определение Алгоритм - предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за их конечное число к результату.  Исторический обзор  Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Алгоритм Евклида .  Алгоритм Евклида - это способ нахождения НОД двух натуральных чисел  Пример  Пусть а = 525, b = 231. Найдем НОД ( алгоритм Евклида )  525 = 231 · 2 + 63  231 = 63 · 3 + 42  63 = 42 · 1 + 21  42 = 21 · 2  Таким образом, (525, 231) = 21.  Пусть даны числа a и b; a >= 0, b>= 0, считаем, что a > b . Алгоритм:  1. Ввести a и b .  2. Если b = 0 , то Ответ: а . Конец .  3. Заменить r := "остаток от деления а на b ", а := b , b := r .  4. Идти на 2. Древний Вавилон          Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений. «Я вычел из площади сторону моего квадрата, это 14,30» современный язык x2—x=14,30. «Ты берёшь 1, коэффициент. Ты делишь пополам 1, это 0;30. Ты умножаешь 0;30 на 0;30, это 0;15. Ты складываешь [это] с 14,30 и это есть 14,30;15, что является квадратом для 29;30. Ты складываешь 0;30, которое ты умножал, с 29;30, получается 30, сторона квадрата», Перевести!!!  Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы  Аланом Тьюрингом,  Алоизом Черчем и  Эмилем Постом  В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова. Направления в теории алгоритмов      Классическая теория алгоритмов формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, открытие класса NP-полных задач и его исследование);     Теория асимптотического анализа алгоритмов понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок,      Теория практического анализа вычислительных алгоритмов получение явных функции трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов. Основны е свойства алгоритма:     1. Дискретность. Процесс решения протекает в виде последовательности отдельных действий, следующих друг за другом. 2. Элементарность действий. Каждое действие не допускает возможности неоднозначного толкования. 3. Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим. 4. Конечность. Алгоритм заканчивает работу после конечного числа шагов.     5. Результативность. В момент прекращения работы алгоритма известно, что является результатом. 6. Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных. Алгоритм считается правильным, если при любых допустимых данных он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Алгоритм однозначен, если при применении к одним и тем же входным данным он дает один и тот же результат Три класса алгоритмов    1. Вычислительные алгоритмы - работают с простыми видами данных (числа, матрицы). 2. Информационные алгоритмы представляют собой набор сравнительно небольших процедур, но работающих с большими объемами информации Управляющие алгоритмы характерны тем, что данные к ним поступают от внешних процессов, которыми они управляют. Результатом работы этих алгоритмов являются различные управляющие воздействия. Оценка сложности алгоритма  измеряется двумя параметрами: T(временная сложность)  S (пространственная сложность, или требования к памяти).  T и S обычно представляются в виде функций от n , где n - размер входных данных. Пример: Если временная сложность алгоритма описывается как  T(n) = 4n2 + 7n + 12, то вычислительная сложность определяется, как O(n2).  Временная сложность, определяемая таким образом не зависит от реализации Классификация алгоритмов по сложности       1. Постоянный - сложность оценивается как O(1). 2. Линейный - оценка равна O(n). 3. Квадратный - O(n2) 4. Кубический, полиноминальный O(n3),O(nm). 5. Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция. 6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.    Проблемы, которые невозможно решить за полиномиальное время, называют нерешаемыми, потому что нахождение их решений быстро становится невозможным. Нерешаемые проблемы иногда называют трудными. Замечание некоторые проблемы принципиально неразрешимы, то есть даже отвлекаясь от временной сложности, невозможно создать алгоритм их решения Примеры трудных задач  • Задача комивояжера. Комивояжер должен объехать N городов с целью осуществления продажи своих товаров. Все N городов соединены дорогами по принципу "каждый с каждым". Известна стоимость проезда между двумя любыми городами. Найти оптимальный маршрут движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу.      Решение (метод грубого перебора). Произвольно пронумеруем N городов целыми числами от 1 до N, причем базовый город имеет номер N. Каждый тур (один из возможных маршрутов) однозначно соответствует перестановке целых чисел 1, 2, ..N - 1. Для каждой перестановки строим тур и определяем его стоимость. Обрабатывая все перестановки запоминаем маршрут, который имеет на текущий момент самую низкую стоимость.     Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с ним. Алгоритм является факториальным, с оценкой O(n!). В задаче требуется найти (N - 1)! перестановок целых чисел. Если даже требуется только один шаг для каждой перестановки, то эта часть алгоритма потребует O[(n - 1)!] шагов, поэтому любая верхняя граница для общего времени работы должна быть O(n!).    Проблема тройного брака. В комнате n мужчин, n женщин и n чиновников. Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. Если дан этот список троек, то возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?    Быстрыми являются линейны е алгоритмы , которые обладают сложностью порядка n и называются также алгоритмами порядка O(n), где n - размерность входных данных Пример К линейным алгоритмам относится алгоритм нахождения суммы десятичных чисел, состоящих из n1 и n2 цифр. Сложность этого алгоритма - O(n1 + n2).    Определение Полиномиальны й алгоритм (или алгоритм полиномиальной временной сложности, или алгоритм принадлежащим классу P) - алгоритм, у которого временная сложность равна O(nk), где k - целое число > 0. Пример алгоритмы - деление, извлечение квадратного корня, решение систем линейных уравнений и др. - попадают в более общий класс полиномиальных алгоритмов. Класс E: задачи, экспоненциальны е по природе  К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа. Задачи не попадаю щие ни в класс P, ни в класс E       задача о вы полнимости : существует ли для данной булевской формулы, находящейся в КНФ, такое распределение истинностных значений, что она имеет значение И?  задача коммивояжера;  решение систем уравнений с целы ми переменны ми;  составление расписаний, учиты ваю щих определенны е условия ;  размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;     оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости;  оптимальны й раскрой (бумага, картон, стальной прокат, отливки), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка;  задача распознавания простого числа;    Детерминированные алгоритмы - во всех них для любого данного состояния существует не больше одного вполне определенного "следующего" состояния. детерминированный алгоритм в каждый момент времени может делать только что-либо одно. В недерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи.  Недетерминированные алгоритмы не являются в каком-то смысле вероятностными или случайными алгоритмами;  они являются алгоритмами, которые могут находиться одновременно во многих состояниях. Нормальные алгоритмы Маркова      Определение Алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова. Определение Слово - это любая конечная последовательность знаков алфавита. Марков любую последовательность букв называл «словами». Определение Число символов в слове называется его длиной . Определение Слово, длина которого равна нулю, называется пусты м  Определение Нормальная схема подстановок - это конечный набор, состоящий из пар слов, где левое слово переходит в правое (но не наоборот). Нормальный алгоритм Маркова  задается алфавитом А и нормальной схемой подстановок,  где алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова  Тезис Маркова : всякий алгоритм в алфавите А представим в виде нормального алгоритма в этом же алфавите.  Это тезис потому, что его невозможно доказать, т.к. в нем фигурируют с одной стороны, интуитивное расплывчатое понятие "всякий алгоритм", а с другой стороны точное понятие "нормальный алгоритм".  Алгоритм как абстрактная машина  Алгоритмические процессы – это процессы , которы е может осуществлять определенны м образом устроенная машина, моделирую щая тем самы м вы полнение отдельны х операций человеком. Общие требования к машинам    характер их функционирования должен бы ть дискретны м , т.е. состоять из отдельны х шагов , кажды й из которы х вы полняется только после завершения преды дущего; действия должны бы ть детерминированы , т.е. шаги вы полняю тся в строгом порядке, а их результат определяется самим шагом и результатами преды дущих шагов; перед началом работы машине предоставляю тся исходны е данны е из области определения алгоритма;    за конечное число шагов работы машины должен бы ть получен результат (или информация о том, что считать результатом); машина должна бы ть универсальной , т.е. такой, чтобы с ее помощью можно бы ло бы вы полнить лю бой алгоритм. Концепция алгоритма как абстрактной машины бы ла вы двинута одновременно (1936 – 1937 гг.) английским математиком Аланом Тью рингом и Эмилем Постом