'

Лекция

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1


Слайд 2

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


Слайд 3

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


Слайд 4


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11


Слайд 12


Слайд 13


Слайд 14


Слайд 15


Слайд 16


Слайд 17

Древний Вавилон Зародились начала алгебры, т.е. решения систем линейных и квадратичных уравнений. «Я вычел из площади сторону моего квадрата, это 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, сторона квадрата», Перевести!!!


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28


Слайд 29


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37


Слайд 38


Слайд 39


Слайд 40


Слайд 41


Слайд 42


Слайд 43


Слайд 44


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


Слайд 49

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


Слайд 50

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


Слайд 51

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


Слайд 52


Слайд 53

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


Слайд 54


Слайд 55

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


Слайд 56

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


Слайд 57

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


Слайд 58

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


×

HTML:





Ссылка: