Лекция Теория алгоритмов. Современная история математики большую роль формированию алгебры в том виде, который мы имеем сейчас, относит к трудам ал-Хорезми, - презентация

1 Лекция Теория алгоритмов

2

3 Современная история математики большую роль формированию алгебры в том виде, который мы имеем сейчас, относит к трудам ал-Хорезми, арабского учёного, Современная история математики большую роль формированию алгебры в том виде, который мы имеем сейчас, относит к трудам ал-Хорезми, арабского учёного, «Слово алгорифм в форме алгоризм часто употреблялось в качестве заглавия изложений индийского счисления в рукописях XII–XV вв. и в книгах XV–XVI вв.». «Слово алгорифм в форме алгоризм часто употреблялось в качестве заглавия изложений индийского счисления в рукописях XII–XV вв. и в книгах XV–XVI вв.». Свои трактаты ал-Хорезми начинал со слов «dixit algorizmi», что означает «Говорит ал- Хорезми Свои трактаты ал-Хорезми начинал со слов «dixit algorizmi», что означает «Говорит ал- Хорезми

4 Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть выражено через другие,а должно рассматриваться как неопределяемое. Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть выражено через другие,а должно рассматриваться как неопределяемое. Алгоритм это точное предписание, которое задаёт вычислительной процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемого этим исходным данным результата.(определение Маркова) Алгоритм это точное предписание, которое задаёт вычислительной процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемого этим исходным данным результата.(определение Маркова)

5

6 Формулировка Колмогорова содержит две существенные идеи: Формулировка Колмогорова содержит две существенные идеи: итеративность алгоритмического процесса итеративность алгоритмического процесса локальность каждого отдельного шага. локальность каждого отдельного шага.

7 Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Определение Определение Алгоритм - предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за их конечное число к результату. Алгоритм - предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за их конечное число к результату.

8 Исторический обзор Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида).

9 Алгоритм Евклида. Алгоритм Евклида - это способ нахождения НОД двух натуральных чисел Алгоритм Евклида - это способ нахождения НОД двух натуральных чисел Пример Пример Пусть а = 525, b = 231. Найдем НОД Пусть а = 525, b = 231. Найдем НОД ( алгоритм Евклида )

10 525 = 231 · = 231 · = 63 · = 63 · = 42 · = 42 · = 21 · 2 42 = 21 · 2 Таким образом, (525, 231) = 21. Таким образом, (525, 231) = 21.

11 Пусть даны числа a и b; a >= 0, b>= 0, считаем, что a > b. Пусть даны числа a и b; a >= 0, b>= 0, считаем, что a > b. Алгоритм: Алгоритм: 1. Ввести a и b. 1. Ввести a и b. 2. Если b = 0, то Ответ: а. Конец. 2. Если b = 0, то Ответ: а. Конец. 3. Заменить r := "остаток от деления а на b ", а := b, b := r. 3. Заменить r := "остаток от деления а на b ", а := b, b := r. 4. Идти на Идти на 2.

12

13

14

15

16

17

18 Древний Вавилон Древний Вавилон Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений. Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений. «Я вычел из площади сторону моего квадрата, это 14,30» - «Я вычел из площади сторону моего квадрата, это 14,30» - современный язык x2x=14,30. современный язык x2x=14,30. «Ты берёшь 1, коэффициент. «Ты берёшь 1, коэффициент. Ты делишь пополам 1, это 0;30. Ты делишь пополам 1, это 0;30. Ты умножаешь 0;30 на 0;30, это 0;15. Ты умножаешь 0;30 на 0;30, это 0;15. Ты складываешь [это] с 14,30 и это есть 14,30;15, что является квадратом для 29;30. Ты складываешь [это] с 14,30 и это есть 14,30;15, что является квадратом для 29;30. Ты складываешь 0;30, которое ты умножал, с 29;30, получается 30, сторона квадрата», Ты складываешь 0;30, которое ты умножал, с 29;30, получается 30, сторона квадрата», Перевести!!! Перевести!!!

19 Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Аланом Тьюрингом, Алоизом Черчем и Алоизом Черчем и Эмилем Постом Эмилем Постом В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова. В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова.

20 Направления в теории алгоритмов Классическая теория алгоритмов Классическая теория алгоритмов формулировка задач в терминах формальных языков, формулировка задач в терминах формальных языков, понятие задачи разрешения, понятие задачи разрешения, введение сложностных классов, введение сложностных классов, открытие класса NP-полных задач и его исследование); открытие класса NP-полных задач и его исследование);

21 Теория асимптотического анализа алгоритмов Теория асимптотического анализа алгоритмов понятие сложности и трудоёмкости алгоритма, понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, критерии оценки алгоритмов, методы получения асимптотических оценок, методы получения асимптотических оценок,

22 Теория практического анализа вычислительных алгоритмов Теория практического анализа вычислительных алгоритмов получение явных функции трудоёмкости, получение явных функции трудоёмкости, интервальный анализ функций, интервальный анализ функций, практические критерии качества алгоритмов, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов. методика выбора рациональных алгоритмов.

23 Основные свойства алгоритма: 1. Дискретность. Процесс решения протекает в виде последовательности отдельных действий, следующих друг за другом. 1. Дискретность. Процесс решения протекает в виде последовательности отдельных действий, следующих друг за другом. 2. Элементарность действий. Каждое действие не допускает возможности неоднозначного толкования. 2. Элементарность действий. Каждое действие не допускает возможности неоднозначного толкования. 3. Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим. 3. Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим. 4. Конечность. Алгоритм заканчивает работу после конечного числа шагов. 4. Конечность. Алгоритм заканчивает работу после конечного числа шагов.

24 5. Результативность. В момент прекращения работы алгоритма известно, что является результатом. 5. Результативность. В момент прекращения работы алгоритма известно, что является результатом. 6. Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных. 6. Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных. Алгоритм считается правильным, если при любых допустимых данных он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Алгоритм считается правильным, если при любых допустимых данных он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Алгоритм однозначен, если при применении к одним и тем же входным данным он дает один и тот же результат Алгоритм однозначен, если при применении к одним и тем же входным данным он дает один и тот же результат

25 Три класса алгоритмов 1. Вычислительные алгоритмы - работают с простыми видами данных (числа, матрицы). 1. Вычислительные алгоритмы - работают с простыми видами данных (числа, матрицы). 2. Информационные алгоритмы представляют собой набор сравнительно небольших процедур, 2. Информационные алгоритмы представляют собой набор сравнительно небольших процедур, но работающих с большими объемами информации но работающих с большими объемами информации Управляющие алгоритмы характерны тем, что данные к ним поступают от внешних процессов, которыми они управляют. Результатом работы этих алгоритмов являются различные управляющие воздействия. Управляющие алгоритмы характерны тем, что данные к ним поступают от внешних процессов, которыми они управляют. Результатом работы этих алгоритмов являются различные управляющие воздействия.

26 Оценка сложности алгоритма измеряется двумя параметрами: T(временная сложность) измеряется двумя параметрами: T(временная сложность) S (пространственная сложность, или требования к памяти). S (пространственная сложность, или требования к памяти). T и S обычно представляются в виде функций от n, где n - размер входных данных. T и S обычно представляются в виде функций от n, где n - размер входных данных.

27 Пример: Если временная сложность алгоритма описывается как Если временная сложность алгоритма описывается как T(n) = 4n2 + 7n + 12, то вычислительная сложность определяется, как O(n2). T(n) = 4n2 + 7n + 12, то вычислительная сложность определяется, как O(n2). Временная сложность, определяемая таким образом не зависит от реализации Временная сложность, определяемая таким образом не зависит от реализации

28 Классификация алгоритмов по сложности 1. Постоянный - сложность оценивается как O(1). 1. Постоянный - сложность оценивается как O(1). 2. Линейный - оценка равна O(n). 2. Линейный - оценка равна O(n). 3. Квадратный - O(n2) 3. Квадратный - O(n2) 4. Кубический, полиноминальный - O(n3),O(nm). 4. Кубический, полиноминальный - O(n3),O(nm). 5. Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция. 5. Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция. 6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов. 6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.

29

30

31 Проблемы, которые невозможно решить за полиномиальное время, называют нерешаемыми, потому что нахождение их решений быстро становится невозможным. Проблемы, которые невозможно решить за полиномиальное время, называют нерешаемыми, потому что нахождение их решений быстро становится невозможным. Нерешаемые проблемы иногда называют трудными. Нерешаемые проблемы иногда называют трудными. Замечание некоторые проблемы принципиально неразрешимы, то есть даже отвлекаясь от временной сложности, невозможно создать алгоритм их решения Замечание некоторые проблемы принципиально неразрешимы, то есть даже отвлекаясь от временной сложности, невозможно создать алгоритм их решения

32 Примеры трудных задач Задача комивояжера. Задача комивояжера. Комивояжер должен объехать N городов с целью осуществления продажи своих товаров. Комивояжер должен объехать N городов с целью осуществления продажи своих товаров. Все N городов соединены дорогами по принципу "каждый с каждым". Все N городов соединены дорогами по принципу "каждый с каждым". Известна стоимость проезда между двумя любыми городами. Известна стоимость проезда между двумя любыми городами. Найти оптимальный маршрут движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу. Найти оптимальный маршрут движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу.

33 Решение (метод грубого перебора). Решение (метод грубого перебора). Произвольно пронумеруем N городов целыми числами от 1 до N, причем базовый город имеет номер N. Произвольно пронумеруем N городов целыми числами от 1 до N, причем базовый город имеет номер N. Каждый тур (один из возможных маршрутов) однозначно соответствует перестановке целых чисел 1, 2,..N - 1. Каждый тур (один из возможных маршрутов) однозначно соответствует перестановке целых чисел 1, 2,..N - 1. Для каждой перестановки строим тур и определяем его стоимость. Для каждой перестановки строим тур и определяем его стоимость. Обрабатывая все перестановки запоминаем маршрут, который имеет на текущий момент самую низкую стоимость. Обрабатывая все перестановки запоминаем маршрут, который имеет на текущий момент самую низкую стоимость.

34 Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с ним. Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с ним. Алгоритм является факториальным, с оценкой O(n!). Алгоритм является факториальным, с оценкой O(n!). В задаче требуется найти (N - 1)! перестановок целых чисел. В задаче требуется найти (N - 1)! перестановок целых чисел. Если даже требуется только один шаг для каждой перестановки, то эта часть алгоритма потребует O[(n - 1)!] шагов, поэтому любая верхняя граница для общего времени работы должна быть O(n!). Если даже требуется только один шаг для каждой перестановки, то эта часть алгоритма потребует O[(n - 1)!] шагов, поэтому любая верхняя граница для общего времени работы должна быть O(n!).

35 Проблема тройного брака. Проблема тройного брака. В комнате n мужчин, n женщин и n чиновников. Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. В комнате n мужчин, n женщин и n чиновников. Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. Если дан этот список троек, то возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак? Если дан этот список троек, то возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?

36 Быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n и называются также алгоритмами порядка O(n), где n - размерность входных данных Быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n и называются также алгоритмами порядка O(n), где n - размерность входных данных Пример Пример К линейным алгоритмам относится алгоритм нахождения суммы десятичных чисел, состоящих из n1 и n2 цифр. Сложность этого алгоритма - O(n1 + n2). К линейным алгоритмам относится алгоритм нахождения суммы десятичных чисел, состоящих из n1 и n2 цифр. Сложность этого алгоритма - O(n1 + n2).

37 Определение Полиномиальный алгоритм (или алгоритм полиномиальной временной сложности, или алгоритм принадлежащим классу P) - алгоритм, у которого временная сложность равна O(nk), где k - целое число > 0. Определение Полиномиальный алгоритм (или алгоритм полиномиальной временной сложности, или алгоритм принадлежащим классу P) - алгоритм, у которого временная сложность равна O(nk), где k - целое число > 0. Пример Пример алгоритмы - деление, извлечение квадратного корня, решение систем линейных уравнений и др. - попадают в более общий класс полиномиальных алгоритмов. алгоритмы - деление, извлечение квадратного корня, решение систем линейных уравнений и др. - попадают в более общий класс полиномиальных алгоритмов.

38

39

40

41

42

43

44

45

46 Класс E: задачи, экспоненциальные по природе К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа. К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа.

47 Задачи не попадающие ни в класс P, ни в класс E задача о выполнимости: существует ли для данной булевской формулы, находящейся в КНФ, такое распределение истинностных значений, что она имеет значение И? задача о выполнимости: существует ли для данной булевской формулы, находящейся в КНФ, такое распределение истинностных значений, что она имеет значение И? задача коммивояжера; задача коммивояжера; решение систем уравнений с целыми переменными; решение систем уравнений с целыми переменными; составление расписаний, учитывающих определенные условия; составление расписаний, учитывающих определенные условия; размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров; размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;

48 оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости; оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости; оптимальный раскрой (бумага, картон, стальной прокат, отливки), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка; оптимальный раскрой (бумага, картон, стальной прокат, отливки), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка; задача распознавания простого числа; задача распознавания простого числа;

49 Детерминированные алгоритмы - во всех них для любого данного состояния существует не больше одного вполне определенного "следующего" состояния. Детерминированные алгоритмы - во всех них для любого данного состояния существует не больше одного вполне определенного "следующего" состояния. детерминированный алгоритм в каждый момент времени может делать только что-либо одно. детерминированный алгоритм в каждый момент времени может делать только что-либо одно. В недерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи. В недерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи.

50 Недетерминированные алгоритмы не являются в каком-то смысле вероятностными или случайными алгоритмами; Недетерминированные алгоритмы не являются в каком-то смысле вероятностными или случайными алгоритмами; они являются алгоритмами, которые могут находиться одновременно во многих состояниях. они являются алгоритмами, которые могут находиться одновременно во многих состояниях.

51 Нормальные алгоритмы Маркова Определение Алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова. Определение Алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова. Определение Слово - это любая конечная последовательность знаков алфавита. Определение Слово - это любая конечная последовательность знаков алфавита. Марков любую последовательность букв называл «словами». Марков любую последовательность букв называл «словами». Определение Число символов в слове называется его длиной. Определение Число символов в слове называется его длиной. Определение Слово, длина которого равна нулю, называется пустым Определение Слово, длина которого равна нулю, называется пустым

52 Определение Нормальная схема подстановок - это конечный набор, состоящий из пар слов, где левое слово переходит в правое (но не наоборот). Определение Нормальная схема подстановок - это конечный набор, состоящий из пар слов, где левое слово переходит в правое (но не наоборот).

53

54 Нормальный алгоритм Маркова задается алфавитом А и нормальной схемой подстановок, задается алфавитом А и нормальной схемой подстановок, где алфавит - конечное, непустое множество элементов называемых буквами. где алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова Различные сочетания букв образуют слова

55

56 Тезис Маркова : всякий алгоритм в алфавите А представим в виде нормального алгоритма в этом же алфавите. Тезис Маркова : всякий алгоритм в алфавите А представим в виде нормального алгоритма в этом же алфавите. Это тезис потому, что его невозможно доказать, т.к. в нем фигурируют с одной стороны, интуитивное расплывчатое понятие "всякий алгоритм", а с другой стороны - точное понятие "нормальный алгоритм". Это тезис потому, что его невозможно доказать, т.к. в нем фигурируют с одной стороны, интуитивное расплывчатое понятие "всякий алгоритм", а с другой стороны - точное понятие "нормальный алгоритм".

57 Алгоритм как абстрактная машина Алгоритмические процессы – это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком. Алгоритмические процессы – это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком.

58 Общие требования к машинам характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов, каждый из которых выполняется только после завершения предыдущего; характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов, каждый из которых выполняется только после завершения предыдущего; действия должны быть детерминированы, т.е. шаги выполняются в строгом порядке, а их результат определяется самим шагом и результатами предыдущих шагов; действия должны быть детерминированы, т.е. шаги выполняются в строгом порядке, а их результат определяется самим шагом и результатами предыдущих шагов; перед началом работы машине предоставляются исходные данные из области определения алгоритма; перед началом работы машине предоставляются исходные данные из области определения алгоритма;

59 за конечное число шагов работы машины должен быть получен результат (или информация о том, что считать результатом); за конечное число шагов работы машины должен быть получен результат (или информация о том, что считать результатом); машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно было бы выполнить любой алгоритм. машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно было бы выполнить любой алгоритм. Концепция алгоритма как абстрактной машины была выдвинута одновременно (1936 – 1937 гг.) английским математиком Аланом Тьюрингом и Эмилем Постом Концепция алгоритма как абстрактной машины была выдвинута одновременно (1936 – 1937 гг.) английским математиком Аланом Тьюрингом и Эмилем Постом