Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча. Машины Тьюринга. Тезис Тьюринга
| Вид материала | Документы |
- Учебно-методический комплекс Специальность 010400 Информационные технологии, 135.47kb.
- Задача об остановке произвольной машины Тпри обработке произвольного слова t алгорифмически, 97kb.
- Экзамен Количество кредитов, 16.65kb.
- Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
- Задача точного определения понятия алгоритма была полностью решена в 30-х годах, 519.73kb.
- Базовые программы для машины тьюринга реферат по дисциплине «Дискретная математика», 52.31kb.
- Программа по дисциплине: информатика (алгоритмы и алгоритмические языки). Продвинутый, 140.13kb.
- Программа по дисциплине информатика (алгоритмы и алгоритмические языки). Основной курс, 103.21kb.
- Сложность вычислений, 29.79kb.
- Рабочая программа дисциплины: Теория алгоритмов для специальности 050202 «Информатика», 196.64kb.
Список вопросов к экзамену
- Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча. Машины Тьюринга. Тезис Тьюринга. Рекурсивные и рекурсивно перечислимые множества. Неразрешимые проблемы.
- Временная сложность алгоритма. Θ, Ω, Ο – символика. Правила подсчета временной сложности.
- Полиномиальная и экспоненциальные сложности. Классы P и NP. NP-полные задачи. Примеры.
- Метод ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке.
- Динамическое программирование. Пример применения динамического программирования для решения задачи об оптимальной последовательности перемножения матриц. Свойства задач, для которых применимо динамическое программирование.
- Динамическое программирование. Пример применения динамического программирования для решения задачи о линейном раскрое. Свойства задач, для которых применимо динамическое программирование.
- Жадные алгоритмы. Свойство жадного выбора. Задача о выборе заявок. Свойства задач, для которых применим жадный алгоритм.
- Приближенные методы решения задач: ослабление задачи, локальный поиск, эвристика жадного выбора и локального поиска. Примеры.
- Абстрактные типы данных. АТД словарь. Реализация при помощи нагруженного дерева. Способы реализации нагруженного дерева в ЭВМ.
- Очереди с приоритетом. Способы реализации. Частично-упорядоченное дерево (пирамида или двоичная куча). Реализация пирамиды.
- Корневые деревья. Реализация корневого дерева. Представление «левый сын – правый брат».
- Поиск в графе в глубину, поиск в ширину.
- Определение компонент связности неориентированного графа.
- Определение компонент сильной связности ориентированного графа.
- Поиск мостов. Поиск точек сочленения.
- Топологическая сортировка.
- Поиск кратчайших путей в бесконтурном графе.
- Алгоритм Форда-Беллмана.
- Алгоритм Дейкстры.
- Алгоритм Флойда.
- Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала.
Критерии оценок:
«Отлично» – умение обосновать правильность работы алгоритма, оценить его сложность.
«Хорошо» – знание формулировок задач, определений, умение объяснить, как устроены алгоритмы и используемые структуры данных.
«Удовлетворительно» – твердые знания определений, методов, алгоритмов.
«Неудовлетворительно» – незнание предмета, либо знания бессистемные, обрывочные.