Вопросы к зачету

Вид материала

Задача

Подобный материал:

• Курс специальности «Математика», 7 семестр, 2011-2012 уч г., Одо требования к зачету, 39.3kb.
• Примерный перечень вопросов к зачету и экзамену Вопросы к зачету, 40.11kb.
• Примерный перечень вопросов к зачету и экзамену Вопросы к зачету, 28.62kb.
• Вопросы к дифференцированному зачету II этапа аттестации, 36.22kb.
• В. М. Земсков Вопросы к зачету по курсу Анализ финансовой отчет, 19.8kb.
• Вопросы к зачету, 127.77kb.
• Права М. В. Осмоловский Вопросы к зачёту по курсу «Философия права» для студентов онюа, 2706.13kb.
• Бодрийяр, «Система вещей» ? Вопросы к зачету = вопросы к контрольной работе 17 июня, 61.96kb.
• Вопросы к зачёту по истории России, 11 класс, 35.02kb.
• Контрольные вопросы по курсу в целом Вопросы к зачету, 87.71kb.

ЛКШ—2003, Группа D

Вопросы к зачету

1. Структуры данных. Реализация стека и очереди. Примеры использования. Задача о правильности скобочной последовательности.
   
2. Способы представления графов.
   
3. Обход в ширину. Описание алгоритма. Решаемые задачи. Реализация. Оценка сложности.
   
4. Обход в глубину. Описание алгоритма. Решаемые задачи. Реализация. Оценка сложности.
   
5. Мосты, точки сочленения и методы их нахождения.
   
6. Поиск кратчайших путей в графе с неотрицательными весами ребер. Алгоритм Дейкстры.
   
7. Поиск кратчайших путей. Алгоритм Форда-Беллмана.
   
8. Поиск кратчайших путей между всеми парами вершин. Алгоритм Флойда.
   
9. Работа с указателями. Выделение и освобождение динамической памяти. Указатели на статические переменные. Побочные и неожиданные эффекты, которые могут возникать.
   
10. Реализация списков.
    
11. Деревья поиска, сбалансированные деревья. Балансировка. АВЛ-деревья.
    
12. Heap. Heapsort.
    
13. Деревья. Теоремы о свойствах и признаках деревьев.
    
14. Остовное дерево. Алгоритм Крускала. Описание, реализация, оценка сложности. Доказательство правильности алгоритма.
    
15. Остовное дерево. Алгоритм Прима. Описание, реализация, оценка сложности. Доказательство правильности алгоритма. Аналогия между алгоритмом Дейкстры и алгоритмом Прима.
    
16. Топологическая сортировка. Постановка задачи, описание алгоритма, реализация, оценка сложности. Примеры задач.
    
17. Динамическое программирование. Общая идея метода. Примеры задач.
    
18. Динамическое программирование на ориентированном графе без циклов. Задача о поиске самого длинного пути. Задача о вычислении количества путей.
    
19. Динамическое программирование. Задача о поиске наибольшей возрастающей подпоследовательности. Задача о поиске общей подстроки.
    
20. Динамическое программирование. Задача о количестве разбиений числа на слагаемые. Задача о количестве способов получения заданной подстроки из заданной строки.
    
21. Динамическое программирование в игровых задачах.
    
22. Комбинаторика. Генерация всех перестановок, сочетаний, разбиений числа на слагаемые, правильных скобочных последовательностей.
    
23. Комбинаторика. Генерация объекта по его номеру, вычисление номера по объекту.
    
24. Переход от рекурсивной функции с параметром к динамическому программированию («Ленивые вычисления»).
    
25. Неразрешимость проблемы останова алгоритма.