Теорія алгоритмів - Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни
Рівень вищої освіти Перший (бакалаврський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційні системи та технології
Освітня програма Інформаційне забезпечення робототехнічних систем, Інформаційні управляючі системи та технології
Статус дисципліни Нормативна
Форма навчання очна(денна)/заочна/дистанційна/змішана
Рік підготовки, семестр 1 курс, весняний семестр
Обсяг дисципліни 6 кредитів
Семестровий контроль/ контрольні заходи іспит
Розклад занять http://rozklad.kpi.ua
Мова викладання Українська
Інформація про керівника курсу / викладачів

Лектор, лабораторні (комп’ютерні практикуми): к.т.н., Солдатова М. О.,

benten1093@gmail.com
Розміщення курсу

https://classroom.google.com/u/1/w/Mzg1OTEyNTgyMDIx/t/all

https://drive.google.com/drive/u/1/my-drive

Програма навчальної дисципліни

Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання

Мета курсу - сприяти більш глибшому розумінню студентом прикладних задач; сформувати математичний фундамент інженера комп’ютерних систем, здатного використовувати сучасний математичний апарат для дослідження, опису, аналізу, проектування алгоритмів для розв’язку таких задач.

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

Завдання вивчення дисципліни: – оволодіння основними поняттями торії алгоритмів; – ознайомлення з технологіями дослідження, аналізу розробки та застосування алгоритмів; – набуття практичних навичок використання методів і засобів проектування та дослідження алгоритмів.

Навчальна дисципліна покликана допомогти студенту отримати:

знання:

  • методів, що використовуються для побудови алгоритмів;

  • способів опису алгоритмів;

  • методів аналізу розв’язності, обчислюваності задач.

вміння:

  • формалізувати математичну задачу і підготувати її для розв’язування на ЕОМ;

  • провести аналіз розв’язності і обчислюваності задачі;

  • скласти алгоритм вирішення прикладної задачі;

  • оцінити складність алгоритму;

  • проаналізувати отримані результати.

досвід:

  • вибору методів розробки та/або вибору алгоритму для розв’язку задачі.

КОМПЕТЕНТНОСТІ

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

Загальні компетентності

КЗ 1. Здатність до абстрактного мислення, аналізу та синтезу.

КЗ 2. Здатність застосовувати знання у практичних ситуаціях.

КЗ 5 Здатність вчитися і оволодівати сучасними знаннями

КЗ 6 Здатність до пошуку, оброблення та аналізу інформації з різних джерел

Спеціальні (фахові, предметні) компетентності

КС 3 Здатність до проектування, розробки, налагодження та вдосконалення системного, комунікаційного та програмно-апаратного забезпечення інформаційних систем та технологій, Інтернету речей (IoT), комп’ютерно-інтегрованих систем та системної мережної структури, управління ними

КС 11 Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних моделей і методів

КС 13 Здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень

Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

МІСЦЕ ДИСЦИПЛІНИ В НАВЧАЛЬНІЙ ПРОГРАМІ

пререквізити

постреквізити

Зміст навчальної дисципліни

######## Тема 1. Поняття алгоритму.

######## Тема 2. Класи складності алгоритмів.

######## Тема 3. Документування програмного продукту.

######## Тема 4. Вибір методу розв’язку задачі.

######## Тема 5. Метод проміжних цілей. Метод пошуку з поверненням.

######## Тема 6. Метод локального пошуку.

######## Тема 7. Рекурсія.

######## Тема 8. Структурне програмування.

######## Тема 9. Визначення абстрактного типу даних.

######## Тема 10. АТД «Список».

######## Тема 11. АТД «Стек».

######## Тема 12. АТД «Черга».

######## Тема 13. АТД «Однозв’язний лінійний список».

######## Тема 14. АТД «Двозв’язний лінійний список».

######## Тема 15. АТД «Відображення».

######## Тема 16. АТД «Дерево».

######## Тема 17. Основні оператори множин.

######## Тема 18. Словники.

######## Тема 19. Хешування.

######## Тема 20. Відображення.

######## Тема 21. Черги з пріоритетами.

######## Тема 22. Розширені BST-дерева.

######## Тема 23. Низхідні та висхідні 2-3-4-дерева.

######## Тема 24. Червоно-чорні дерева.

######## Тема 25. Інші дерева пошуку.

######## Тема 26. Елементарні методи сортування.

######## Тема 27. Швидке сортування.

######## Тема 28. Сортування злиттям.

######## Тема 29. Пірамідальне сортування.

######## Тема 30. Порозрядне сортування.

######## Тема 31. Методи сортування спеціального призначення.

Навчальні матеріали та ресурси

Базова

  1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы / М.:

    Вильямс, 2000 – 384с.

  2. Гудман С., Хидетниеми С. Введение в разработку и анализ

    алгоритмов/М.: Мир, 1981 – 368 с.

  3. Седжвик Р. Фундаментальные алгоритмы на С++ / К.: ДиаСофт, 2001 –

    688с.

  4. Ковалюк Т.В. Основи програмування / К.: BHV, 2005 – 384 с.

  5. Ананій В. Левітін Алгоритми: введення в розробку й аналіз =

    Introduction to The Design and Analysis of Aigorithms. / М .: "Вильямс", 2006. - С. 275-284. - ISBN 5-8459-0987-2

  6. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6.

    Пірамідальна сортування / / Алгоритми: побудова й аналіз = Introduction to Algorithms / Под ред. І. В. Красикова. - 2-ге вид. / М .: Вільямс, 2005. - С. 182-188. - ISBN 5-8459-0857-4

  7. https://www.toptal.com/developers/sorting-algorithms/

Інформаційні ресурси

  1. https://classroom.google.com/u/1/w/Mzg1OTEyNTgyMDIx/t/all

  2. https://drive.google.com/drive/u/1/my-drive

Навчальний контент

Методика опанування навчальної дисципліни (освітнього компонента)

Форма навчання Семестрові (кредитні) модулі Всього кредитів /годин Розподіл навчального часу за видами занять Семестрова атестація
Лекції Практичні (семінарські) заняття Лабораторні роботи СРС
Денна Всього 6/180 54 0 36 90
2 6/180 54 0 36 90 іспит

Лекційні заняття

№

з/п

 Назва теми лекції та перелік основних питань (перелік дидактичних засобів, посилання на літературу та завдання на СРС)

  1. Побудова і аналіз алгоритмів

    1. Поняття алгоритму. Знання й управління. Визначення знань, їхня роль у процесах управління, уявлення про процес вирішення проблем і необхідність представлення й обробки знань. Алгоритми і їхня роль. Стисла характеристика напрямків представлення знань. ([1] с.9, [2] с.16-28)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Основні етапи побудови алгоритму. Алгоритми, розв’язність, обчислюваність, перераховність. Основні етапи повної побудови алгоритму. Структурне програмування зверху-вниз і правильність програм. Базові структури даних. Розвиток уявлень про структури даних. ([2] с.16-28)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 5], виконати завдання для домашніх робіт [3, стор. 8].

Класи складності алгоритмів. Методи оцінки складності алгоритмів. Класифікація. Оцінка часу виконання програм. ([1] с.28-32, [2] с.181-185, [3] с.60)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 5], виконати завдання для домашніх робіт [3, стор. 10].

Документування програмного продукту. Склад документації, порядок розробки та правила ведення. Тестування програмних продуктів. ([1] с.30, [2] с.67)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 3], виконати завдання для домашніх робіт [5, стор. 4], підготуватися до контрольної роботи.

  1. Методи розробки алгоритмів

    1. Вибір методу розв’язку задачі. Огляд методів розробки алгоритмів. ([2] с.106-108, [4] с.178-186)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 15], виконати завдання для домашніх робіт [3, стор. 25,26].

Метод проміжних цілей. Основна ідея методу проміжних цілей. Жадібні алгоритми. Евристики. ([1] с.276-291, [2] с.113)

для домашніх робіт [3, стор. 25,26].

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Метод пошуку з поверненням. Основна ідея методу пошуку з поверненням. Метод гілок та границь. Альфа-бета відсікання. ([1] с.291-301, [2] с.109-144)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 15], виконати завдання

Рекурсія. Поняття рекурсії. Область застосування рекурсії в програмуванні. Рекурсивні функції. Розвиток уявлень про рекурсивність арифметичних функцій. Обчислюваність, розв’язуваність та рекурсивність. ([1] с.70-76, [4] с.142-149)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Структурне програмування. Низхідне проектування. Модульне програмування. Методи структурування програм. ([2] с.30-47, [4] с.178-186)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 5], виконати завдання для домашніх робіт [5, с. 6], підготуватися до контрольної роботи.

  1. Абстрактні типи даних

    1. Визначення абстрактного типу даних. Абстрактний тип даних, тип даних, структура даних. (с. 23-27 [1], с. 310-311 [4], с.47-84 [2], с.75-245 [3])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].

  1. АТД «Список». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.45-57, [4] с.310-311)

  2. АТД «Стек». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.58-60, [4] с.312-316)

  3. АТД «Черга». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.57-65, [4] с.316-325)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

  1. АТД «Однозв’язний лінійний список». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.60-66, [4] с.319-325)

  2. АТД «Двозв’язний лінійний список». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.57-58)

  3. АТД «Відображення». Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.66-68)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].

АТД «Дерево». Реалізація за допомогою масиву та за допомогою покажчиків. Бінарні дерева. ([1] с.77-99, [4] с.326-336)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].

  1. АТД засновані на множинах. Задача пошуку

    1. Основні оператори множин. Базові поняття про операції з множинами. ([1] с.105-109)

    2. Словники. Реалізації словників та їх порівняння. ([1] с.113-128, [3] с.567-601)

    3. Хешування. Поняття хешування. Відкрита за закрита схеми хешування. Методики вирішення колізій при закритому хешуванні. Реструктуризація хеш-таблиць ([1] с.116-128, [3] с.567-601)

    4. Відображення. Реалізація за допомогою хеш-таблиць. ([1] с.128-129)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 6], виконати завдання для домашніх робіт [5, стор. 7].

  1. Хешування. Поняття хешування. Відкрита за закрита схеми хешування. Методики вирішення колізій при закритому хешуванні. Реструктуризація хеш-таблиць ([1] с.116-128, [3] с.567-601)

  2. Відображення. Реалізація за допомогою хеш-таблиць. ([1] с.128-129)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

  1. Черги з пріоритетами. Реалізації за допомогою списків, частково впорядкованих дерев та масивів. ([1] с.129-137)

  2. Мультисписки. Способи реалізації. Область застосування. ([1] с.137-143)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].

Контрольна робота 1

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор

  1. BST-дерева. Способи реалізації. Область застосування. Збалансовані дерева. ([1] с.146-180, [3] с.523-562)

  2. Розширені BST-дерева. Способи реалізації. Область застосування. Ротація. ([3] с.528-540)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

  1. Рандомізовані BST-дерева. Способи реалізації. Область застосування. ([3] с.528-540)

  2. Низхідні та висхідні 2-3-4-дерева. Способи реалізації. Область застосування. ([3] с.540-545)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 9], виконати завдання для домашніх робіт [5, стор. 10].

  1. Червоно-чорні дерева. Способи реалізації. Область застосування. ([3] с.545-555)

  2. Інші дерева пошуку. AVL-дерева. 2-3-дерева. Дерева Байєра. Навантажені дерева. Область застосування. (с. 158-165 [1], 551-553 [3], 652-663 [3])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 9].

  1. АТД засновані на множинах. Задача сортування

    1. Задача сортування. Постановка задачі. Класифікація методів сортування. ([3] с.249-298, [1] с.228-235)

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 11], виконати завдання для домашніх робіт [5, стор. 12].

Елементарні методи сортування. Сортування вибором (с.257[3], с.232[1]). Сортування вставками (с.258[3], с.231[1]). Бульбашкове сортування (с.261[3], с.228[1]). Сортування методом Шелла с(.269[3], с.262[1]). Сортування по індексам та покажчикам (с.283[3]). Метод розподіляючого підрахунку (с.295[3]).

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Швидке сортування. Базовий алгоритм. Характеристики ресурсоємності. Метод покращення. (с.299-329 [3], с. 235-243 [1], с.223-229[2])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 13], виконати завдання для домашніх робіт [5, стор. 14].

  1. Сортування злиттям. Двошляхове злиття. Абстрактне обмінне злиття. Низхідне сортування злиттям. Вдосконалення базового алгоритму. Висхідне сортування злиттям. Ресурсоємність сортування злиттям. (с.330-354 [3], с. 116-128 [1])

  2. Пірамідальне сортування. Алгоритми для дерев сортування. Ресурсоємність пірамідального сортування. (с.355-400 [3], с. 244-247 [1], с.229-240[2])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 15], виконати завдання для домашніх робіт [5, стор. 16].

Порозрядне сортування. Область застосування. MSD та LSD алгоритми порозрядного сортування. (с.401-437 [3], с. 247-254 [1])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Методи сортування спеціального призначення. Парно-непарне сортування злиттям Бетчера. Сортуючі мережі. Зовнішнє сортування. Сортування-злиття. (с.438-473 [3])

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор.

Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 17], виконати завдання для домашніх робіт [5, стор. 18].

Контрольна робота 2

Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор

Залік.

Лабораторні заняття (комп’ютерні практикуми)

Лабораторна робота Тема Години
Лабораторна робота 1 Комп’ютерний практикум 1. Побудова і аналіз алгоритмів. 4
Лабораторна робота 2 Комп’ютерний практикум 2. Методи створення алгоритмів. Частина 1. 4
Лабораторна робота 3 Комп’ютерний практикум 3. Методи створення алгоритмів. Частина 2. 4
Лабораторна робота 4 Комп’ютерний практикум 4. Абстрактні типи даних 4
Лабораторна робота 5 Комп’ютерний практикум 5. Пошук у масиві. Відкрите хешування. 2
Лабораторна робота 6 Комп’ютерний практикум 6. Пошук у масиві. Закрите хешування. 2
Лабораторна робота 7 Комп’ютерний практикум 7. Двійкові дерева пошуку. 4
Лабораторна робота 8 Комп’ютерний практикум 8. Основні типи двійкових дерев. 2
Лабораторна робота 9 Комп’ютерний практикум 9. Алгоритми сортування. Прості методи сортування. 2
Лабораторна робота 10 Комп’ютерний практикум 10. Алгоритми сортування. Методи сортування малих обсягів даних. 2
Лабораторна робота 11 Комп’ютерний практикум 11. Алгоритми сортування. Методи сортування великих обсягів даних. 2
Лабораторна робота 12 Комп’ютерний практикум 12. Алгоритми сортування. Методи сортування даних з великими ключами. 2
Лабораторна робота 13 Індивідуальне завдання. Виконується протягом семестру. Захист. 2

Всього на лабораторні заняття виділено 36 годин.

Самостійна робота студента

Самостійна робота студентів складається з:

  • Підготовки до аудиторних занять

https://classroom.google.com/u/1/w/Mzg1OTEyNTgyMDIx/t/all,

https://drive.google.com/drive/u/1/my-drive,

  • Виконання лабораторних робіт

https://classroom.google.com/u/1/w/Mzg1OTEyNTgyMDIx/t/all

https://drive.google.com/drive/u/1/my-drive,

  • Виконання індивідуального завдання.

Самостійна робота

Тема

 Години

Основні етапи побудови алгоритму.

 3

Класи складності алгоритмів.

 3

Документування програмного продукту.

 3

Вибір методу розв’язку задачі.

 3

Метод пошуку з поверненням.

 3

Структурне програмування. Низхідне проектування. Модульне програмування.

 3

Визначення абстрактного типу даних.

 3

АТД «Однозв’язний лінійний список».

 3

АТД «Двозв’язний лінійний список».

 3

АТД «Відображення».

 3

АТД «Дерево».

 3

Хешування.

 3

Відображення.

 3
Черги з пріоритетами. 3

Мультисписки.

 3

Рандомізовані BST-дерева.

 3

Низхідні та висхідні 2-3-4-дерева.

 3

Інші дерева пошуку.

 3

Задача сортування.

 3

Швидке сортування.

 3

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

 3

Пірамідальне сортування.

 3

Методи сортування спеціального призначення.

 3

Індивідуальне завдання

 21

Всього

 90

Політика та контроль

Політика навчальної дисципліни (освітнього компонента)

Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються Положенням про організацію освітнього процесу в Національному технічному університеті України «Київському політехнічному інституті імені Ігоря Сікорського».

Політика виставлення оцінок: кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (лабораторних робіт, індивідуального завдання) до екзамену він не допускається; пропущені заняття обов’язково мають бути відпрацьовані.

Відвідування є обов'язковим (за винятком випадків, коли існує поважна причина, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились в комп’ютерному класі.

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

Реферати також можуть підготувати студенти, у яких недостатньо рейтингових балів.

Політика академічної поведінки та доброчесності: конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі індивідуальні завдання та курсову роботу студент має виконати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту лабораторних робіт, на контрольних роботах, на іспиті.

Норми академічної етики: дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених командних результатів. При виконанні лабораторних робіт студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань лабораторних робіт не слід використовувати ноутбуки, смартфони, планшети чи комп’ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача.

Дотримання академічної доброчесності студентів й викладачів регламентується кодекс честі Національного технічного університету України «Київський політехнічний інститут», положення про організацію освітнього процесу в КПІ ім. Ігоря Сікорського

Види контролю та рейтингова система оцінювання результатів навчання (РСО)

РОЗПОДІЛ БАЛІВ, ЯКІ ОТРИМУЮТЬ СТУДЕНТИ ПІД ЧАС ВИВЧЕННЯ ДИСЦИПЛІНИ

Види контролю бали
Лабораторні роботи (12 робіт) 5
Контрольна робота ( 2 роботи) 5
Індивідуальне завдання 30
Іспит 40

R=(12*5+2*5+30)*0,6+40=100

Календарний контроль: провадиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу.

За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 16 балів. На першій атестації (8-й та 9-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 10 балів.

За результатами 13 тижнів навчання максимально можлива кількість балів – 55 балів. На другій атестації (14-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 30 балів.

Семестровий контроль: іспит

Умови допуску до семестрового контролю: 30 балів та мінімально позитивна оцінка за лабораторні роботи та індивідуальне завдання / зарахування усіх лабораторних робіт та індивідуального завдання.

Таблиця відповідності рейтингових балів оцінкам за університетською шкалою:

Кількість балів Оцінка
100-95 Відмінно
94-85 Дуже добре
84-75 Добре
74-65 Задовільно
64-60 Достатньо
Менше 60 Незадовільно
Не виконані умови допуску (<40) Не допущено

Додаткова інформація з дисципліни (освітнього компонента)

Рекомендовані теми рефератів.

  1. Ієрархія класів складності.

  2. Повнота задач NP-класу.

  3. Розгляд евристичних алгоритмів.

  4. Дослідження застосування АТД в різноманітних алгоритмах.

  5. Використання хешування в криптографії.

  6. Використання хешування в різних галузях діяльності.

  7. Дерева пошуку в теорії ігор.

  8. Дерева пошуку в задачах прйняття рішень.

  9. Сортування Timsort.

  10. Інтроспективне сортування.

  11. Блукаюче сортування.

  12. Млинцеве сортування.

  13. Топологічне сортування.

  14. Мережеве сортування.

  15. Зовнішнє сортування ( методи не розглянуті в лекці).

Робочу програму навчальної дисципліни (силабус):

Складено доц., к.т.н. Солдатова М. О.

Ухвалено кафедрою ІСТ(протокол № 1 від 30.08.2021 р.)

Погоджено Методичною комісією факультету[1] (протокол № 1 від 30.08.2021 р.)

[1] Методичною радою університету – для загальноуніверситетських дисциплін.