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

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

2.

Понятие «алгоритм» относится к числу
наиболее фундаментальных понятий
математики

3.

Интуитивное понятие алгоритма
Алгоритм - точное предписание о
выполнении в определённом порядке
некоторой системы операций, ведущих
к решению всех задач данного типа

4.

Происхождение слова алгоритм
Историческая справка
Происхождение слова алгоритм связано с
алгоритмами позиционной арифметики
Правила с числами, записанными в десятичной
системе счисления, были впервые найдены в
средневековой Индии

5.

Происхождение слова алгоритм
Историческая справка
Европейцы познакомились с ними
по книге арабского ученого IX века
Мухаммеда ибн Муса аль-Хорезми, что буквально
означает «Мухаммед сын Мусы, уроженец Хорезма»
В те времена Аральское море называлось «озером
Хорезм», а сам город Хорезм располагался южнее этого
моря в бассейне реки Амударьи
Имя ученого аль-Хорезми латинизировалось и стало
звучать «алхоризм», «алгорифм», «алгоритм»

6.

Понятия, связанные с понятием алгоритма
- Каждый алгоритм имеет исполнителя (устройство или
человек, выполняющий алгоритм)
- Алгоритм задает вычислительный (алгоритмический)
процесс, состоящий из отдельных, элементарных шагов –
тактов алгоритма
- Алгоритм перерабатывает исходный набор данных Р
(входной объект) в результат работы Q (объект на выходе)
- Каждый такт работы алгоритма завершается переходом в
новое состояние, среди которых некоторые опознаются как
заключительные состояния

7.

Варианты протекания алгоритмического процесса
Пусть алгоритм имеет исходный набор данных Р
1) На некотором шаге возникает заключительное
состояние. При этом происходит остановка
вычислений и выдается результат Q

8.

Варианты протекания алгоритмического процесса
2) Каждое следующее состояние сменяется
последующим до бесконечности, т.е. процесс
вычислений никогда не останавливается
(например, зацикливание алгоритма)

9.

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

10.

Алгоритм применим к исходному
набору данных Р, если на некотором
шаге возникает заключительное состояние
и выдается результат Q
Обозначение: Q = (P)
Т.е. алгоритм – процедура вычисления некоторой
функции Q = (P)

11.

Дональд Эрвин Кнут (10.01.1938- ), американский
ученый, иностранный член Российской академии наук,
создатель настольной издательской системы ТЕХ
Алгоритм - это конечный набор правил, который
определяет последовательность операций для
решения конкретного множества задач и обладает
пятью важными чертами:
- конечность,
- определённость,
- ввод,
- вывод,
- эффективность

12.

Основные черты алгоритма
1) Дискретность алгоритма
Алгоритмический процесс – последовательность
элементарных шагов (тактов)
Каждый шаг – смена одного набора данных другими

13.

Основные черты алгоритма
2) Детерминированность алгоритма
Для каждой пары ( ,Р), т.е. данного алгоритма
и исходного набора данных Р однозначно
определяется результат работы Q,
последовательность элементарных шагов и т.д.
Т.е. при повторном выполнении с объектом P
на входе снова получится объект Q. Это
позволяет сообщать алгоритм одним лицом
другому, например, компьютеру

14.

Основные черты алгоритма
3) Массовость алгоритма
Каждый алгоритм решает какую-нибудь
массовую проблему – класс однотипных задач
Частные случаи получаются при варьировании
исходных данных

15.

Для каждого алгоритма существует некоторая
фиксированная, потенциально бесконечная
совокупность Х – возможных начальных данных
Из этой совокупности выбирается объект Р,
поступающий на вход алгоритма

16.

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

17.

Абстракция потенциальной осуществимости
В общей теории алгоритмов не учитывается
практическая осуществимость и считается
возможным выполнить любое конечное
число шагов
Это положение называется абстракцией
потенциальной осуществимости

18.

Абстракция потенциальной осуществимости
Т.е. считается, что можно оперировать со сколь
угодно большими конечными объектами,
например, со сколь угодно длинными словами

19.

Абстракция потенциальной осуществимости
Пример
Число 10100 (единица со ста нулями в
десятичной записи счисления) американский
математик Эдвард Каснер в 1938 году назвал
«гугол», чтобы проиллюстрировать разницу
между невообразимо большим числом и
бесконечностью

20.

Абстракция потенциальной осуществимости
Пример
Гугол больше, чем количество частиц в
известной нам части Вселенной, которых, по
разным оценкам, от 1079 до 1081
Длина ребра куба, состоящего из гугола атомов
алюминия, составит около 58 млн световых лет

21.

Абстракция потенциальной осуществимости
Пример
Мы не сможем на практике осуществить работу
со словом из 10100 букв.
Но принцип абстракции потенциальной
осуществимости разрешает оперировать с
такими большими объектами
Замечание:
Название компании Google является искажённым
написанием слова «гугол» («googol»)

22. Необходимость уточнения понятия алгоритм

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

23.

Пусть имеется массовая задача
Если найден алгоритм (в интуитивном
смысле) для ее решения, то не
требуется другого определения
алгоритма

24.

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

25.

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

26.

Пример
В 1900 году Давид Гильберт на
2-м Международном математическом
конгрессе в Париже огласил 23 трудных
математических проблемы
Давид Гильберт (23.01.1862-14.02.1943) – выдающийся немецкий
математик-универсал. В 1910-1920-е годы (после смерти Анри
Пуанкаре) был признанным мировым лидером математиков

27.

Десятая проблема Гильберта
Найти алгоритм, применение которого к
алгебраическому уравнению с целыми
коэффициентами (с произвольным числом
неизвестных) приводило бы к результату
«да», если уравнение имеет целые решения
и к результату «нет» – в противном случае

28.

Десятая проблема Гильберта
Для частного случая (уравнения с одним
неизвестным) такой алгоритм есть
Если уравнение
с целыми коэффициентами имеет целый
корень, то он обязательно является
делителем свободного члена an

29.

Десятая проблема Гильберта
Можно предложить такой алгоритм:
1) Найти все делители an : d1, d2, …, dk
2) Вычислить Pn(x) для каждого di, i = 1..k
3) Если Pn(di) = 0, то di – корень уравнения

30.

Десятая проблема Гильберта
В 1970 году ленинградский
ученый Ю.В. Матиясевич успешно
завершил работу ряда математиков над
доказательством того, что требуемый
алгоритм невозможен
Юрий Владимирович Матиясевич (род. 2.03.1947) – советский и
российский математик, исследователь Санкт-Петербургского
отделения Математического института им. В.А. Стеклова РАН,
академик РАН, доктор физико-математических наук.
Внес существенный вклад в теорию вычислимости, завершив
решение десятой проблемы Гильберта

31.

Направления формализации
понятия алгоритм

32.

1. Рекурсивные функции
Алонзо Чёрч (14.06.1903-11.08.1995) – американский
математик и логик. Разработал теорию лямбдаисчислений, которая позволила показать существование
т.н. «неразрешимых задач»
Вместе с Тьюрингом показал, что лямбда-исчисления и
машина Тьюринга имеют одинаковые свойства – тезис
Чёрча-Тьюринга
Стивен Коул Клини (5.01.1909-25.01.1994) –
американский математик. Участвовал в разработке теории
вычислимости, известен изобретением регулярных
выражений, внес важный вклад в теорию конечных
автоматов

33.

1. Рекурсивные функции
Курт Фридрих Гёдель (1906-1978) – австрийский логик,
математик и философ математики.
Наиболее известный по сформулированной и
доказанной им теоремой о неполноте (1931 г.)
Теорема о неполноте:
Любая эффективно аксиоматизируемая теория, в
достаточно богатом языке, достаточном для
определения натуральных чисел и операций сложения и
умножения является неполной либо противоречивой.
Неполнота означает наличие высказываний, которые
нельзя ни доказать, ни опровергнуть, исходя из аксиом
этой теории. Противоречивость — возможность доказать
любое высказывание: как истинное так и ложное.

34.

1. Рекурсивные функции
Курт Фридрих Гёдель (1906-1978) – австрийский логик,
математик и философ математики.
Кроме того, Гёдель написал работу по общей теории
относительности, в которой предложил вариант решения
уравнений Эйнштейна, из которого следует, что строение
вселенной может иметь такое устройство, в котором
течение времени является закольцованным (метрика
Гёделя), что теоретически допускает путешествия во
времени. Большинство современных физиков считают
это решение верным лишь математически и не имеющим
физического смысла.

35.

1. Рекурсивные функции
В алгоритмическом процессе
вычисляется значение некоторой
функции f(x1, x2, …, xn), определенной
на множестве натуральных чисел
Понятие алгоритма отождествляется со
строгим математическим понятием
«частично рекурсивная функция»

36.

2. Машина Тьюринга
Алан Тьюринг (23.06.1912-07.06.1954) – английский
математик, логик и криптограф.
Предложенная им в 1936 году абстрактная
вычислительная машина Тьюринга позволила
формализовать понятие алгоритма и до сих пор
используется во множестве теоретических и практических
исследованиях
Теорема Гёделя о неполноте побудила
Тьюринга доказать, что нет общего метода
определения истинности и, таким образом,
математика всегда будет содержать
недоказуемые высказывания

37.

2. Машина Тьюринга
Алан Тьюринг (23.06.1912-07.06.1954) – английский
математик, логик и криптограф.
Во время Второй мировой войны Тьюринг
работал криптографом для раскрытия
кода немецкой военной шифровальной
машины «Энигма».
Немцы пребывали в уверенности, что их система
неуязвима. Но опираясь на работы польских
математиков, А.Тьюринг совместно с У.Уэлчманом
раскрыл шифры, создав дешифровочную машину
«Бомба».

38.

2. Машина Тьюринга
Эмиль Леон Пост (11.02.1897 (Польша) -21.04.1954) –
американский математик и логик. Предложил абстрактную
машину Поста
Машина Поста отличается от машины
Тьюринга большей простотой. Обе машины
«эквивалентны» и были созданы для
уточнения понятия «алгоритм».

39.

2. Машина Тьюринга
Алгоритмический процесс – работа некоторой
«абстрактной вычислительной машины».
Каждая отдельная машина Тьюринга
выполняет только один алгоритм
Лучше подходит термин «программа машины
Тьюринга» – набор инструкций, упрощенных до
однотипной схемы
Все машины Тьюринга отличаются программами, а
общим является описание исполнителя (человеквычислитель, действующий бездумно и
неукоснительно, как машина)

40.

3. Нормальные алгорифмы Маркова
Андрей Андреевич Марков (младший) (22.09.190311.10.1979) – советский математик, сын известного
русского математика А.А.Маркова, основоположник
советской школы конструктивной математики, автор
понятия нормального алгоритма (1947 г.)
Алгоритмический процесс – переработка
слов некоторого алфавита с помощью точно
описанных правил переработки

41.

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

42. Конструктивные объекты

43.

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

44.

Конструктивный объект должен иметь:
1) Конечное множество элементов
1) Внутреннюю систему координат,
позволяющую однозначно локализовать
любой его элемент
(второй элемент справа, элемент пятой
строки и третьего столбца и т.д.)

45.

Простейшим примером конструктивных
объектов являются слова в некотором
алфавите

46.

Алфавитом называется непустое
конечное множество
Элементы множества А называются
буквами (символами)

47.

Словом в алфавите А называется
конечная последовательность
букв алфавита А. Натуральное число
n 0 называется длиной слова u.

48.

В теории алгоритмов удобно считать, что

49.

Слово нулевой длины называется
пустым словом
Обозначение:

50.

Частными видами слов являются
записи натуральных чисел,
конечные десятичные дроби и т.п.
Пример
Алгоритм - сложение натуральных чисел
Р = 12 + 24
Q = 36
P и Q являются словами в алфавите A={0, 1, 2, …, 9, +}

51.

Пример
Конструктивные объекты:
- Натуральные числа, записанные в какой-либо
системе счисления
- Слова в естественном языке
- Формулы алгебры высказываний
- Матрицы в их линейной записи:

52.

Пример
Не конструктивные объекты:
- Действительное число, являющееся
бесконечной десятичной дробью (например,
число )
- Произвольная функция f(x): N N

53.

Всякий конструктивный объект можно
однозначно и полностью закодировать в
виде слова.
Т.о. слова в алфавите – главный вид
конструктивных объектов

54.

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

55.

Вспомним

56.

Пусть
произвольный алфавит.
А+ - множество всех непустых слов в
алфавите А.

57.

Обозначим
слово в алфавите А, где

58.

Доказательство (инъекция)

59.

Доказательство (сюръекция)

60.

Пример

61.

Пример

62.

Задание на СР
Аналогично найти (w),
где w – фамилия студента

63.

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

64.

Замечание
Действительные числа (их записи) не
могут быть исходными данными
алгоритма
Т.к. исполнитель, выписывая слово
посимвольно, ни на каком шаге не
выпишет бесконечное слово целиком
В ПК действительные числа не
реализованы