Зачет по предмету «Структуры и алгоритмы обработки данных». Роль алгоритмов в вычислениях.

Вопросы к зачету по предмету «Структуры и алгоритмы обработки данных»

1. Роль алгоритмов в вычислениях.
2. Асимптотические обозначения при определении порядка роста функций, характеризующих время работы алгоритма.
3. NP-полные задачи. Определение.
4. Оценка эффективности алгоритма
5. Рекуррентные соотношения. Метод подстановки.
6. Метод деревьев рекурсии.
7. Вероятностный анализ и рандомизированные алгоритмы.
8. Пирамидальная сортировка
9. Быстрая сортировка.
10. Нижние оценки алгоритмов сортировки.
11. Медианы и порядковые статистики
12. Стеки и очереди.
13. Связанные списки
14. Реализация указателей и объектов
15. Представление корневых деревьев.
16. Бинарные деревья поиска.
17. Красно-чёрные деревья
18. Расширение структур данных.
19. Рассписание работы конвейера.
20. Перемножение цепочки матриц.
21. Задачи оптимизации методом динамического программирования.
22. Жадные алгоритмы
23. Амортизационный анализ
24. В-деревья
25. Биноминальные пирамиды
26. Фибоначчиевы пирамиды.
27. Структуры данных для непересекающихся множеств.
28. Поиск в ширину на графах.
29. Поиск в глубину на графах.
30. Топологическая сортировка.
31. Разложение ориентированного графа на сильно связанные компоненты.
32. Минимальные остовные деревья.
33. Кратчайшие пути из одной вершины (single-sourсе shortest path problem).
34. Кратчайшие пути между всеми парами вершин.
35. Задача о максимальном потоке.