Слайд 3Современная история математики большую роль формированию алгебры в том виде, который мы
![Современная история математики большую роль формированию алгебры в том виде, который мы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-2.jpg)
имеем сейчас, относит к трудам ал-Хорезми, арабского учёного,
«Слово “алгорифм” в форме “алгоризм” часто употреблялось в качестве заглавия изложений индийского счисления в рукописях XII–XV вв. и в книгах XV–XVI вв.».
Свои трактаты ал-Хорезми начинал со слов «dixit algorizmi», что означает «Говорит ал-Хорезми
Слайд 4Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть
![Понятие алгоритма принадлежит к числу понятий столь фундаментальных, что не может быть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-3.jpg)
выражено через другие ,а должно рассматриваться как неопределяемое .
Алгоритм — это точное предписание, которое задаёт вычислительной процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемого этим исходным данным результата .(определение Маркова)
Слайд 6Формулировка Колмогорова содержит две существенные идеи:
итеративность алгоритмического процесса
локальность каждого
![Формулировка Колмогорова содержит две существенные идеи: итеративность алгоритмического процесса локальность каждого отдельного шага.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-5.jpg)
отдельного шага.
Слайд 7Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов.
Определение
Алгоритм
![Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Определение Алгоритм -](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-6.jpg)
- предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за их конечное число к результату.
Слайд 8Исторический обзор
Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной
![Исторический обзор Первым дошедшим до нас алгоритмом в его интуитивном понимании –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-7.jpg)
последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида).
Слайд 9Алгоритм Евклида .
Алгоритм Евклида - это способ нахождения НОД двух натуральных
![Алгоритм Евклида . Алгоритм Евклида - это способ нахождения НОД двух натуральных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-8.jpg)
чисел
Пример
Пусть а = 525, b = 231. Найдем НОД
( алгоритм Евклида )
Слайд 10525 = 231 · 2 + 63
231 = 63 · 3 +
![525 = 231 · 2 + 63 231 = 63 · 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-9.jpg)
42
63 = 42 · 1 + 21
42 = 21 · 2
Таким образом, (525, 231) = 21.
Слайд 11Пусть даны числа a и b; a >= 0, b>= 0, считаем,
![Пусть даны числа a и b; a >= 0, b>= 0, считаем,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-10.jpg)
что a > b .
Алгоритм:
1. Ввести a и b .
2. Если b = 0 , то Ответ: а . Конец .
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
Слайд 18 Древний Вавилон
Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений.
![Древний Вавилон Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-17.jpg)
«Я вычел из площади сторону моего квадрата, это 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, сторона квадрата»,
Перевести!!!
Слайд 19Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году
![Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-18.jpg)
годы
Аланом Тьюрингом,
Алоизом Черчем и
Эмилем Постом
В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова.
Слайд 20Направления в теории алгоритмов
Классическая теория алгоритмов
формулировка задач в терминах формальных языков,
![Направления в теории алгоритмов Классическая теория алгоритмов формулировка задач в терминах формальных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-19.jpg)
понятие задачи разрешения,
введение сложностных классов,
открытие класса NP-полных задач и его исследование);
Слайд 21Теория асимптотического анализа алгоритмов
понятие сложности и трудоёмкости алгоритма,
критерии оценки алгоритмов,
![Теория асимптотического анализа алгоритмов понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-20.jpg)
методы получения асимптотических оценок,
Слайд 22Теория практического анализа вычислительных алгоритмов
получение явных функции трудоёмкости,
интервальный анализ функций,
![Теория практического анализа вычислительных алгоритмов получение явных функции трудоёмкости, интервальный анализ функций,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-21.jpg)
практические критерии качества алгоритмов,
методика выбора рациональных алгоритмов.
Слайд 23Основные свойства алгоритма:
1. Дискретность. Процесс решения протекает в виде последовательности отдельных действий,
![Основные свойства алгоритма: 1. Дискретность. Процесс решения протекает в виде последовательности отдельных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-22.jpg)
следующих друг за другом.
2. Элементарность действий. Каждое действие не допускает возможности неоднозначного толкования.
3. Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим.
4. Конечность. Алгоритм заканчивает работу после конечного числа шагов.
Слайд 245. Результативность. В момент прекращения работы алгоритма известно, что является результатом.
6. Массовость.
![5. Результативность. В момент прекращения работы алгоритма известно, что является результатом. 6.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-23.jpg)
Алгоритм описывает некоторое множество процессов, применимых при различных входных данных.
Алгоритм считается правильным, если при любых допустимых данных он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи.
Алгоритм однозначен, если при применении к одним и тем же входным данным он дает один и тот же результат
Слайд 25Три класса алгоритмов
1. Вычислительные алгоритмы - работают с простыми видами данных (числа,
![Три класса алгоритмов 1. Вычислительные алгоритмы - работают с простыми видами данных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-24.jpg)
матрицы).
2. Информационные алгоритмы представляют собой набор сравнительно небольших процедур,
но работающих с большими объемами информации
Управляющие алгоритмы характерны тем, что данные к ним поступают от внешних процессов, которыми они управляют. Результатом работы этих алгоритмов являются различные управляющие воздействия.
Слайд 26Оценка сложности алгоритма
измеряется двумя параметрами: T(временная сложность)
S (пространственная сложность, или требования
![Оценка сложности алгоритма измеряется двумя параметрами: T(временная сложность) S (пространственная сложность, или](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-25.jpg)
к памяти).
T и S обычно представляются в виде функций от n, где n - размер входных данных.
Слайд 27Пример:
Если временная сложность алгоритма описывается как
T(n) = 4n2 + 7n
![Пример: Если временная сложность алгоритма описывается как T(n) = 4n2 + 7n](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-26.jpg)
+ 12, то вычислительная сложность определяется, как O(n2).
Временная сложность, определяемая таким образом не зависит от реализации
Слайд 28Классификация алгоритмов по сложности
1. Постоянный - сложность оценивается как O(1).
2. Линейный -
![Классификация алгоритмов по сложности 1. Постоянный - сложность оценивается как O(1). 2.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-27.jpg)
оценка равна O(n).
3. Квадратный - O(n2)
4. Кубический, полиноминальный - O(n3),O(nm).
5. Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция.
6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
Слайд 31Проблемы, которые невозможно решить за полиномиальное время, называют нерешаемыми, потому что нахождение
![Проблемы, которые невозможно решить за полиномиальное время, называют нерешаемыми, потому что нахождение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-30.jpg)
их решений быстро становится невозможным.
Нерешаемые проблемы иногда называют трудными.
Замечание некоторые проблемы принципиально неразрешимы, то есть даже отвлекаясь от временной сложности, невозможно создать алгоритм их решения
Слайд 32Примеры трудных задач
• Задача комивояжера.
Комивояжер должен объехать N городов с
![Примеры трудных задач • Задача комивояжера. Комивояжер должен объехать N городов с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-31.jpg)
целью осуществления продажи своих товаров.
Все N городов соединены дорогами по принципу "каждый с каждым".
Известна стоимость проезда между двумя любыми городами.
Найти оптимальный маршрут движения так, чтобы побывать во всех городах и при этом иметь минимальные затраты на дорогу.
Слайд 33Решение (метод грубого перебора).
Произвольно пронумеруем N городов целыми числами от 1 до
![Решение (метод грубого перебора). Произвольно пронумеруем N городов целыми числами от 1](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-32.jpg)
N, причем базовый город имеет номер N.
Каждый тур (один из возможных маршрутов) однозначно соответствует перестановке целых чисел 1, 2, ..N - 1.
Для каждой перестановки строим тур и определяем его стоимость.
Обрабатывая все перестановки запоминаем маршрут, который имеет на текущий момент самую низкую стоимость.
Слайд 34Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с
![Если находится маршрут с меньшей стоимостью, то все дальнейшие сравнения осуществляем с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-33.jpg)
ним.
Алгоритм является факториальным, с оценкой O(n!).
В задаче требуется найти (N - 1)! перестановок целых чисел.
Если даже требуется только один шаг для каждой перестановки, то эта часть алгоритма потребует O[(n - 1)!] шагов, поэтому любая верхняя граница для общего времени работы должна быть O(n!).
Слайд 35Проблема тройного брака.
В комнате n мужчин, n женщин и n чиновников.
![Проблема тройного брака. В комнате n мужчин, n женщин и n чиновников.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-34.jpg)
Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника.
Если дан этот список троек, то возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?
Слайд 36Быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n и называются также
![Быстрыми являются линейные алгоритмы, которые обладают сложностью порядка n и называются также](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-35.jpg)
алгоритмами порядка O(n), где n - размерность входных данных
Пример
К линейным алгоритмам относится алгоритм нахождения суммы десятичных чисел, состоящих из n1 и n2 цифр. Сложность этого алгоритма - O(n1 + n2).
Слайд 37Определение Полиномиальный алгоритм (или алгоритм полиномиальной временной сложности, или алгоритм принадлежащим классу
![Определение Полиномиальный алгоритм (или алгоритм полиномиальной временной сложности, или алгоритм принадлежащим классу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-36.jpg)
P) - алгоритм, у которого временная сложность равна O(nk), где k - целое число > 0.
Пример
алгоритмы - деление, извлечение квадратного корня, решение систем линейных уравнений и др. - попадают в более общий класс полиномиальных алгоритмов.
Слайд 46Класс E: задачи, экспоненциальные по природе
К экспоненциальным задачам относятся задачи, в
![Класс E: задачи, экспоненциальные по природе К экспоненциальным задачам относятся задачи, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-45.jpg)
которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа.
Слайд 47Задачи не попадающие ни в класс P, ни в класс E
задача
![Задачи не попадающие ни в класс P, ни в класс E ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-46.jpg)
о выполнимости: существует ли для данной булевской формулы, находящейся в КНФ, такое распределение истинностных значений, что она имеет значение И?
задача коммивояжера;
решение систем уравнений с целыми переменными;
составление расписаний, учитывающих определенные условия;
размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;
Слайд 48 оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости;
оптимальный
![ оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости; ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-47.jpg)
раскрой (бумага, картон, стальной прокат, отливки), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка;
задача распознавания простого числа;
Слайд 49Детерминированные алгоритмы - во всех них для любого данного состояния существует не
![Детерминированные алгоритмы - во всех них для любого данного состояния существует не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-48.jpg)
больше одного вполне определенного "следующего" состояния.
детерминированный алгоритм в каждый момент времени может делать только что-либо одно.
В недерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи.
Слайд 50Недетерминированные алгоритмы не являются в каком-то смысле вероятностными или случайными алгоритмами;
они
![Недетерминированные алгоритмы не являются в каком-то смысле вероятностными или случайными алгоритмами; они](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-49.jpg)
являются алгоритмами, которые могут находиться одновременно во многих состояниях.
Слайд 51Нормальные алгоритмы Маркова
Определение Алфавит - конечное, непустое множество элементов называемых буквами.
![Нормальные алгоритмы Маркова Определение Алфавит - конечное, непустое множество элементов называемых буквами.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-50.jpg)
Различные сочетания букв образуют слова.
Определение Слово - это любая конечная последовательность знаков алфавита.
Марков любую последовательность букв называл «словами».
Определение Число символов в слове называется его длиной.
Определение Слово, длина которого равна нулю, называется пустым
Слайд 52Определение Нормальная схема подстановок - это конечный набор, состоящий из пар слов,
![Определение Нормальная схема подстановок - это конечный набор, состоящий из пар слов,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-51.jpg)
где левое слово переходит в правое (но не наоборот).
Слайд 54Нормальный алгоритм Маркова
задается алфавитом А и нормальной схемой подстановок,
где алфавит -
![Нормальный алгоритм Маркова задается алфавитом А и нормальной схемой подстановок, где алфавит](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-53.jpg)
конечное, непустое множество элементов называемых буквами.
Различные сочетания букв образуют слова
Слайд 56Тезис Маркова : всякий алгоритм в алфавите А представим в виде нормального
![Тезис Маркова : всякий алгоритм в алфавите А представим в виде нормального](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-55.jpg)
алгоритма в этом же алфавите.
Это тезис потому, что его невозможно доказать, т.к. в нем фигурируют с одной стороны, интуитивное расплывчатое понятие "всякий алгоритм", а с другой стороны - точное понятие "нормальный алгоритм".
Слайд 57Алгоритм как абстрактная машина
Алгоритмические процессы – это процессы, которые может осуществлять
![Алгоритм как абстрактная машина Алгоритмические процессы – это процессы, которые может осуществлять](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-56.jpg)
определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком.
Слайд 58Общие требования к машинам
характер их функционирования должен быть дискретным, т.е. состоять
![Общие требования к машинам характер их функционирования должен быть дискретным, т.е. состоять](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/417369/slide-57.jpg)
из отдельных шагов , каждый из которых выполняется только после завершения предыдущего;
действия должны быть детерминированы, т.е. шаги выполняются в строгом порядке, а их результат определяется самим шагом и результатами предыдущих шагов;
перед началом работы машине предоставляются исходные данные из области определения алгоритма;