Список вопросов к зачету

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

Документы

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

• Темы контрольных работ и рефератов, список вопросов к зачету по «философии культуры», 31.19kb.
• Институт дополнительного профессионального образования, 191.74kb.
• Примерный перечень вопросов к зачету и экзамену Вопросы к зачету, 40.11kb.
• Примерный перечень вопросов к зачету и экзамену Вопросы к зачету, 28.62kb.
• Список вопросов к зачету по дисциплине Физическая культура, 34.12kb.
• Список вопросов к зачету по истории России Социально-экономическое развитие России, 13.45kb.
• Список вопросов для подготовки к зачету по дисциплине «Статистика» (на базе высшего, 53.59kb.
• Комплекс г. Тюмень 2005 «Информационные технологии в экономике»: Учебно-методический, 666.16kb.
• Комплекс Тюмень 2006 математика в экономике: Учебно-методический комплекс. Тюмень:, 383.87kb.
• Примерный перечень вопросов к зачету, 15.19kb.

ЛКШ – 2005. Группа C3.


Список вопросов к зачету

1. Стек, очередь, дек: основные операции, реализация, возможные ошибки функционирования.
   
2. Куча: основные операции, их реализация, оценка сложности.
   
3. HeapSort.
   
4. QSort.
   
5. Бинарный поиск.
   
6. Графы: основные определения. Способы представления графов в компьютере. Теорема о четности числа вершин нечетной степени. Деревья. Теорема о соотношении числа ребер и вершин в дереве.
   
7. Планарные графы. Формула Эейлера. Доказательство непланарности графов K₅ и K_3,3.
   
8. Алгоритмы обхода графа в ширину и в глубину.
   
9. Алгоритмы поиска кратчайших путей: алгоритм Дейкстры (реализация, оценка сложности, область применения).
   
10. Алгоритмы поиска кратчайших путей: алгоритм Флойда (реализация, обоснование, оценка сложности, область применения).
    
11. Алгоритмы поиска кратчайших путей: алгоритм Форда-Белмана (реализация, обоснование, оценка сложности, область применения).
    
12. Алгоритмы построения минимального каркаса: алгоритм Прима.
    
13. Алгоритмы построения минимального каркаса: алгоритм Краскала.
    
14. Топологическая сортировка.
    
15. Построение эйлерового цикла.
    
16. Генерация перестановок в лексикографическом порядке.
    
17. Генерация перестановки по номеру и номера по перестановке.
    
18. Число сочетаний (C_n^k). Треугольник Паскаля. Основные свойства и тождества.
    
19. Метод динамического программирования (на примере нескольки задач).
    
20. Перебор. Основные этапы: отсечения, получение предварительной оценки, эвристики, отсечение по времени.
    
21. Формулы Бэкуса-Науэра для арифметических выражений. Метод рекурсивного спуска.
    
22. Конечные автоматы. Основные определения. Детерминированные и недетерминированные автоматы. Примеры регулярного и нерегулярного языков. Доказательство теоремы о том, что множества языков, распознаваемых детерминированными и недетерминированными автоматами, совпадают.
    
23. Проверка принимаемости слова недетерминированным автоматом. Проверка эквивалентности двух детерминированных автоматов.
    
24. Поиск подстроки в строке. Алгоритм Кнута–Морриса–Пратта.