TA

Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча. Машины Тьюринга. Тезис Тьюринга. Рекурсивные и рекурсивно перечислимые множества. Неразрешимые проблемы

Интуитивное понятие алгоритма Свойства алгоритма

Задачи рассматриваемые в теории алгоритмов Вычислимая функция(неформ)

Различные формальные определения алгоритма -по Черчу -по Маркову -по Посту -по Тьюрингу

Формальное определение алгоритма(по Черчу) Частичная функция Область определения частичной функции

Местность числовой частичной функции

Рекурсивные функции -примитивно рекурсивные функции

-примеры примитивно-рекурсивных функций -частично-рекурсивные функции -общерекурсивные функции -тезис Черча-(Тьюринга).

-круговая диаграмма отношения множеств рекурсивных функций.

Формальное определение алгоритма(по Тьюрингу) Машины Тьюринга-Поста -конечный автомат -детерминированный -недетерминированный -детерминированая МТ -недетерминированая МТ -тезис Тьюринга-(Черча)

-пример сложения/вычитания двух чисел в машине Тьюринга

Рекурсивные(Разрешимые) множества -характеристическая функция

1

-примеры Рекурсивно-перечислимые множества -примеры Теорема Поста -доказательство

-следствие из теоремы Поста Круговая диаграмма отношения множеств. Нумерация множества Алгоритмическая проблема -разрешимая -неразрешимая

Примеры неразрешимых алгоритмических проблем

Временная сложность алгоритма., , символика. Правила подсчета временной сложности

Вычислительная сложность алгоритма -временная сложность -пространственная сложность Ассимптотическая сложность алгоритма Символика Правила подсчета временной сложности. -правило суммы

-правило произведения Пример подсчета временной сложности алгоритма

Полиномиальные и экспоненциальные сложности. Классы P и NP. NP-полные задачи.

Полиномиальная сложность Экспоненциальная сложность Субсложности

Формально Класс сложности Класс P

Класс NP

2

Предикат

Алфавит

Слово

Язык Сводимость языка по Карпу

NP-трудный язык

NP-полный язык

Неформально классP

класс NP

NP полная задача

Примеры

Задачи принадлежность которых к классу P неизвестна Задача проверки числа на простоту

Метод ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке

Метод ветвей и границ Функция ветвления Функция оценки Рекорд

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

Динамическое программирование. Пример применения динамического программирования для задачи об оптимальной последовательности перемножения матриц и о линейном раскрое. Свойства задач для которых применимо динамическое программирование

Метод Динамического программирования Свойства задач для которых применимо ДП -оптимальность для подзадач Кратчайший путь в графе -наличие перекрывающихся подзадач Задача о линейном раскрое

3

Задача об оптимальном перемножении матриц Другие задачи решаемые ДП

Жадный алгоритм. Свойство жадного выбора. Задача о выборе заявой. Свойства задач, для которых применим жадный алгоритм

Жадный алгоритм Свойства задач для которых применим жадный алгоритм

-оптимальность жадного выбора -оптимальность для подзадач Задача о выборе заявок -постановка

-доказательство применимости жадного алгоритма -решение Эвристика жадного выбора.

Другие задачи решаемые жадным методом

Приближенные методы решения задач: ослабление задачи, локальный поиск, эвристика жадного выбора и локального поиска. Примеры

Эвристический(приближенный) алгоритм Свойства эвристических алгоритмов Эвристика жадного выбора и локального поиска -задача о гамильтоновом пути -задача о максимальном взвешеном покрытии -задача о камнях

Применение приближенных алгоритмов

Абстрактные типы данных. АТД словарь. Реализация при помощи нагруженного дерева. Способы реализации нагруженного дерева в ЭВМ

Абстрактный тип данных Примеры АТД

4

АТД-словарь Нагруженое дерево -конечная вершина -промежуточная вершина

-оптимизации нагруженого дерева Реализация АТД-словарь

Способы реализации нагруженого дерева в ЭВМ

Очереди с приоритетом. Способы реализации. Частичноупорядоченое дерево(пирамида или двоичная куча). Реализация пирамиды

Очередь с приоритетом Способы реализации очереди с приоритетом -список,массив -пирамида Реализация пирамиды

Применение очереди с приоритетом -сортировка

Корневые деревья. Реализация корневого дерева. Представление ¾левый сын правый брат¿

Дерево Корневое дерево Высота дерева Двоичное дерево

Сбалансированое двоичное дерево Представление ¾левый сын правый брат¿ Реализация корневого дерева Массив предков

Поиск в графе в глубину, поиск в ширину, определение компонент связности

Поиск в глубину Дерево поиска в глубину

5

Виды ребер -прямое -обратное

Компонента связности Лес деревьев обхода

Подсчет компонент связности Применения поиска в глубину Поиск в ширину Применения поиска в ширину

Определение компонент сильной связности ориентированого графа

Слабосвязаные вершины Односторонне связаные вершины Сильносвязаные вершины Сильносвязный орграф Сильносвязаная компонента орграфа Граф конденсаций

Алгоритм определения компонент сильной связности Доказательство корректности алгоритма

Применения алгоритма

Поиск мостов. Поиск точек сочленения

Мост Точка сочленения

Поиск мостов и точек сочленения Доказательство корректности работы алгоритма Применения алгоритма

Топологическая сортировка

Топологическая сортировка Пример

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

6

Топологическая сортировка для графа Алгоритм топологической сортировки

Поиск кратчайших путей в бесконтурном графе

Цикл в графе Контур в графе Путь в графе Вес пути в графе

Вес кратчайшего пути в графе Кратчайший путь в графе Варианты задачи о кратчайших путях -из одной вершины -в одну вершину -между парой вершин

-между всеми парами вершин -в ациклическом графе -без дуг отрицательного веса

-без циклов отрицательного веса. Функция ослабления пути Бесконтурный граф Свойства бесконтурных графов

Связь с топологической сортировкой Алгоритм поиска кратчайшего пути в бесконтурном графе

Алгоритм Форда-Беллмана

Алгоритм Форда-Беллмана Доказательство корректности алгоритма Поиск отрицательных циклов Оптимизация алгоритма Оценка сложности и Метод построения Особенности применения

Алгоритм Дейкстры

Алгоритм Дейкстры Доказательство корректности алгоритма

7

Оптимизация алгоритма Оценка сложности и Метод построения Особенности применения

Алгоритм Флойда

Алгоритм Флойда Доказательство корректности алгоритма

Оценка сложности и Метод построения Особенности применения Построение транзитивного замыкания графа

Алгоритм Прима и Краскала

Остовное дерево Минимальное остовное дерево Алгоритм Прима

Доказательство корректности алгоритма Прима Оценка сложности и Метод построения алгоритма Прима Алгоритм Краскала Доказательство корректности алгоритма Краскала Оптимизация алгоритма Краскала

Оценка сложности и Метод построения алгоритма Краскала Применение алгоритмов MST

Вопросы на консультацию

Формальное определение и обоснование для топологической сортировки Является ли нагруженое дерево детерминированым конечным автоматом Метод ветвей и границ (обоснование)

Поиск в глубину в ширину (обоснование) Тезис Тьюринга-Черча Машина Тьюринга-Поста

Принадлежит ли задача Факторизации числа классу NP Что рассказывать про приближенные алгоритмы Напомнить что такое "ослабление"в жадных алгоритмах

8

При выборе списка L состоящего из подмножеств множества Q допусти-

мых решений в методе Ветвей и границ является ли L подмножеством 2Q ( булеана)

Обоснование алгоритма поиска мостов и точек сочленения

9