Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Теорія алгоритмів Екзаменаційні питання

Скачати 36.47 Kb.

Теорія алгоритмів Екзаменаційні питання




Скачати 36.47 Kb.
Дата конвертації10.06.2017
Розмір36.47 Kb.

Теорія алгоритмів

Екзаменаційні питання


  1. Основи аналізу алгоритмів. Асимптотичний аналіз поведінки алгоритмів в середньому і в крайніх випадках.

  2. Відмінності між поведінкою в кращому, середньому і найгіршому випадку. Нотація: О велике, о мале, ω і θ.

  3. Емпіричні вимірювання ефективності. Компроміс між часом та обсягом пам'яті в алгоритмах. Використання рекурентних відносин для аналізу рекурсивних алгоритмів.

  4. Засоби порівняння алгоритмів, вплив структур даних і особливостей реалізації на ефективність алгоритмів.

    В математичному аналізі асимптотичний аналіз - це метод опису граничної поведінки. Дана методологія має багато застосувань в природничих науках. Наприклад

    Структура даних В програмуванні та комп'ютерних науках структу́ри да́них - це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру.



  5. Алгоритмічні стратегії. Алгоритми повного перебору.

    Метод «грубої сили» (від англ. Brute force; або повний перебір) - метод рішення криптографічної задачі шляхом перебору всіх можливих варіантів ключа. Складність повного перебору залежить від кількості всіх можливих рішень задачі.



  6. Алгоритми «розділяй та володарюй».

  7. Перебір з поверненням.

  8. Метод гілок і меж.

  9. Евристичні алгоритми.

  10. Алгоритми обробки строк тексту.

  11. Алгоритми чисельної апроксимації.

  12. Поняття обчислюваною функції. Властивість покрокового виконання алгоритму.

  13. Розв'язані множини і їх властивості. Перераховуванні множини і їх властивості.

  14. Перерахована множина, як множина визначення обчислюваної функції.

    Область визначення (старіший термін - область задавання[джерело?]) - множина допустимих значень аргументу функції. Позначатиметься як D(y), якщо вказується область визначення функції y=f(x).

    Обч́ислювана функція (англ. computable function) - основний об'єкт вивчення теорії обчислень. Обчислюваною функцією f : N k → N ^\rightarrow \mathbb } називають таку функцію, результат якої може бути отримано за допомогою деякого ефективного процесу.

    Перерахована множина, як множина значень обчислюваної функції.

  15. Теорема Поста. Теорема про графік обчислюваної функції.

  16. Поняття складності обчислення. Функція складності обчислень (за часом).

  17. Аксіоми Блюма. Теорема про прискорення.

  18. Класи складності. Опис класів P і NP. Приклади завдань, що належать цим класам.

  19. Ототожнення класу P з класом реально обчислювальних функцій.

  20. Поліноміальне зведення NP-повні задачі.

    NP-повна задача NP-повна задача (англ. NP-complete) - в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. Зміст 1 Формальне визначення 1.

    Теорема Кука. Приклади NP-повних задач.

  21. Проблема перебору (P = NP?). Застосування теорії NP-повноти для аналізу складності завдань.

  22. Класифікація сортувань. Характеристики сортувань. Прості сортування як спосіб швидкої реалізації алгоритму.

  23. Метод простого включення.

  24. Метод простого обміну (бульбашкове сортування).

  25. Шейкерне сортування.

  26. Сортування вставками.

  27. Сортування підрахунком.

  28. Цифрове сортування. Переваги і недоліки простих сортувань.

  29. Складні сортування як спосіб створення ефективних алгоритмів. Приклади складних сортувань.

  30. Сортування Шелла.

  31. Сортування Хоара (швидке сортування).

  32. Сортування злиттям.

  33. Переваги і недоліки складних сортувань. Порівняння простих та складних сортувань.

  34. Поняття комбінаторної задачі. Перестановки. Підрахунок кількості можливих перестановок. Організація перестановок.

  35. Розміщення та сполучення. Підрахунок кількості. Організація знаходження всіх можливих розміщень і сполучень.

  36. Методи організації повного перебору.

  37. Метод гілок і границь. Обмеження варіантів перебору.

  38. Алгоритми пошуку з повертанням.

  39. Задача про розстановку дужок.

  40. Основні поняття теорії графів. Матричне подання графів. Матриця зв’язності та матриця відстаней на графі.

  41. Пошук найкоротших шляхів та оптимальних маршрутів у графах. Алгоритм Дейкстри.

  42. Метод Беллмона.

  43. Знаходження мінімального остовного дерева графа за алгоритмом Прима Краскала.

  44. Перевірка зв’язності графів. Алгоритм Тар’яна знаходження найменшого спільного пращура.

  45. Задача про найменше вершинне покриття.

    Алгоритм Дейкстри - алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

    Теорія графів Теорія графів - розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E - підмножина V × V.

    Вершинне покриття графа - це множина вершин така, що кожне ребро графа інцидентне хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм.



  46. Задача про Гамільтонові шляхи на графі.

  47. Пошук у ширину на графах.

  48. Пошук у глибину на графах.

  49. Алгоритми пошуку в рядках: бінарний пошук, алгоритм Бойера – Мура.

    Двійкóвий пóшук - алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево пошуку)



  50. Алгоритм Кнута – Морріса – Пратта.

  51. Алгоритм Карпа – Рабіна, наближений пошук.

  52. Прості алгоритми побудови дерева суфіксів. Алгоритм Укконена.

  53. Масиви суфіксів. Задача про найбільший спільний під рядок двох рядків.

  54. Основні алгоритми обробки рядків – розбиття рядків, об’єднання рядків, алгоритми вставки, видалення, заміни.

  55. Основні формули обчислювальної геометрії.

    Обчислювальна геометрія (англ. computational geometry) - галузь комп'ютерних наук присвячена вивченню алгоритмів що описуюються в термінах геометрії.



  56. Знаходження довжини відрізку в n-вимірному просторі.

  57. Відстань від точки до прямої.

  58. Координати точок перетину відрізків і прямих.

  59. Рівняння прямої, кола, площини.

  60. Знаходження площі багатокутника.

  61. Метод триангуляції. Метод трапецій.

  62. Перевірка опуклості багатокутника.

  63. Векторна геометрія. Колінеарність векторів.

  64. Перевірка належності точок прямій.

  65. Ліві та праві трійки векторів.

  66. Знаходження порядку обходу вершин опуклого багатокутника.

  67. Задачі мінімізації в геометричній інтерпретації.

  68. Поняття "жадібного" алгоритму. Теоретичні основи "жадібних" алгоритмів. Переваги та недоліки "жадібних" алгоритмів.

  69. Задача про вкладання рюкзака.

  70. Розв’язання задач із застосуванням "жадібних" алгоритмів. Геометричні, транспортні, економічні задачі.

  71. Поняття про динамічне програмування. Основні підходи до розв’язання задач методом динамічного програмування.

  72. Матричне числення. Перемноження декількох матриць.

  73. Знаходження найбільшої спільної підпослідовності множин. Визначення оптимальної тріангуляції багатокутника.

  74. Задачі лінійного програмування. Симплекс-метод розв’язання задач економічного планування.

  75. Криптографічні алгоритми та їх застосування для захисту інформації.

    Динамічне програмування - розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління.

    Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) - метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі чиї вимоги представлені через лінійні відношення.

    Зáхист інформáції (англ. Data protection) - сукупність методів і засобів, що забезпечують цілісність, конфіденційність і доступність інформації за умов впливу на неї загроз природного або штучного характеру, реалізація яких може призвести до завдання шкоди власникам і користувачам інформації.




Скачати 36.47 Kb.