Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри icon

Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри




Скачати 35.53 Kb.
НазваЗадача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри
Дата конвертації26.01.2013
Розмір35.53 Kb.
ТипЗадача

Спеціальність Прикладна математика. Інформатика.

Дисципліна Ефективні алгоритми і структури даних.

Питання до екзамену.

  1. Змістовні постановки задач та їх математичні моделі. Задача про перехрестя доріг.

  2. Метод покрокового уточнення алгоритму.

  3. Псевдо-алгоритмічна мова.

  4. Абстрактні типи даних. Час виконання алгоритму.

  5. О-символіка. Методи аналізу складності алгоритму за часом.

  6. АТД Список. Реалізація списків.

  7. АТД Стек. Реалізація стеків.

  8. АТД Черга. Реалізація черг.

  9. АТД Відображення. Реалізація відображень.

  10. Алгоритм Хафмена оптимального кодування.

  11. Алгоритм Зіва-Лімпела архівації.

  12. Означення дерева. Різні стратегії обходу дерев.

  13. АТД Дерево. Реалізація дерев.

  14. Бінарні дерева. Представлення бінарних дерев. Реалізація бінарних дерев.

  15. Введення в множини. Оператори АТД, засновані на множинах.

  16. Реалізація множин за допомогою бінарних векторів.

  17. Реалізація множин за допомогою зв'язаних списків.

  18. Словники. Реалізація словників.

  19. Структури даних, засновані на хеш-таблицях. Відкрите хешування.

  20. Закрите хешування. Оцінка ефективності хеш-функцій.

  21. Реалізація АТД для відображень. Черги з пріоритетами.

  22. Реалізація черги з пріоритетами за допомогою частково-впорядкованих дерев.

  23. Деякі структури складних множин.

  24. Дерева бінарного пошуку. Аналіз часу виконання. Ефективність дерев бінарного пошуку.

  25. Навантажені дерева. Реалізація множин збалансованими деревами.

  26. Множини з операторами MERGE і FIND.

  27. АТД з операторами MERGE і SPLIT.

  1. Основні означення. Представлення орграфів.

  2. Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри.

  3. Пошук найкоротших шляхів між парами вершин.

  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. Р-складність та NP-складність. NP-повнота. Деякі NP-повні задачі.



Схожі:

Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconЗадача 1 2 Задача 2 2 Фінансово-економічний аналіз 4 Задача 2 5 Інвестиції 6 Задача 1 6 Задача 2 6 Економіка праці 7 Задача 1 7 Маркетинг 8 Задача 1 8 Задача 2 8
Діяльність виробничого підприємства, що займається виробництвом сільськогосподарської продукції, характеризується такими даними
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconЗадача про обчислення шляху
Нехай матеріальна точка рухається прямолінійно з деякою миттєвою швидкістю. Треба знайти шлях, який пройде тіло за проміжок часу...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconТема: Формальне виконання алгоритму; аргументи, результати, проміжні величини
Під формальним виконанням алгоритму розуміється таке його виконання, коли сам виконавець не знає ні постановки задачі, ні змісту...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconТема Значення і теоретичні засади фінансового аналізу
Основні поняття: фінансовий аналіз, мета, об’єкт, предмет, завдання, суб’єкти фінансового аналізу, вертикальний аналіз, горизонтальний...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconЗавдання для підготовки до олімпіади
Знайти середню швидкість руху літака, якщо відомо, що першу третину шляху він летів зі швидкістю 700 км/год, другу третину – зі швидкістю...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри icon10 клас 1
Першу половину часу велосипедист їхав швидше, отже проїхав більшу частину шляху. Тому на першій половині шляху
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри icon10 клас Задача Див. Лабораторна робота №2 (10 клас). Задача Див. Задача 2 (9 клас) 11 клас
Кладемо диск на міліметровий папір і визначаємо внутрішній і зовнішній його діаметри. Тоді
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconПрошу надати висновок щодо містобудівного обгрунтування розміщення об’єкта містобудування
Містобудівне обгрунтування розміщення містобудівних об’єктів, виконане спеціалізованою ліцензованою проектною організацією з містобудівними...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconПрошу надати висновок про історико-містобудівне обгрунтування розміщення об’єкта нового будівництва чи реконструкції будівлі та споруди на території історичного ареалу м. Львова
Сторико-містобудівне обгрунтування (імо), виконане спеціалізованою ліцензованою проектною організацією – 3 примірники та електронна...
Задача пошуку найкоротшого шляху. Обгрунтування та аналіз алгоритму Дейкстри iconЗатвердження містобудівного обгрунтування, історико містобудівного обгрунтування для розміщення об’єкта у
Мета послуги – визначення можливості розміщення об’єкта містобудування для здійснення громадянами нового будівництва
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи