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

Реквізити навчальної дисципліни
Рівень вищої освіти Перший (бакалаврський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційно управляючі системи та технології
Освітня програма Інформаційні управляючі системи та технології
Статус дисципліни Нормативна (обовя'зкова)
Форма навчання очна(денна)/заочна
Рік підготовки, семестр 1 курс, (другий) весняний семестр
Обсяг дисципліни 6 кредитів ECTS /180 годин (54 годин лекцій, 36 годин практичних робіт, 90 СРС)
Семестровий контроль/ контрольні заходи Іспит, ттестування/модульна контрольна робота/захист на практичних роботах
Розклад занять 3 лекції (6 годин) на 2 тижні, 1 практична робота (2 години) на тиждень http://rozklad.kpi.ua
Мова викладання Українська
Інформація про керівника курсу / викладачів Лектор, практичні (комп'ютерні практикуми): ст.викладач Дорошенко Катерина Сергіївна тел.: 0932051821. пошта: doroshenko.kateryna1@lll.kpi.ua
Розміщення курсу https://classroom.google.com/c/NzEwNzgwNjc0NDMz?cjc=uhg2hps ІС-41, https://classroom.google.com/c/NzEwNzgyOTE4MTI4?cjc=2gr7a7q ІС-42, https://classroom.google.com/c/NzEwNzgxNzM1OTU5?cjc=sp2vfcc ІС-43, https://classroom.google.com/c/NzEwNzgyNjUwMTk1?cjc=wlpomis ІС-44. https://www.youtube.com/channel/UCf9xOF5-J_HBrtx0R39_k7g відеолекції

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

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

Силабус освітнього компонента <<Теорія алгоритмів>> складено відповідно до освітньої програми підготовки бакалаврів <<Інформаційні управляючі системи та технології>> спеціальності 126 – Інформаційно управляючі системи та технології.

Мета курсу є формування та закріплення у студентів наступних компетентностей: ЗК 1 Здатність до абстрактного мислення, аналізу та синтезу ЗК 2 Здатність застосовувати знання у практичних ситуаціях ЗК 3 Здатність до розуміння предметної області та професійної діяльності. ЗК 5 Здатність вчитися і оволодівати сучасними знаннями ЗК 6 Здатність до пошуку, оброблення та узагальнення інформації з різних джерел. ФК 3 Здатність до проєктування, розробки, налагодження та вдосконалення системного, комунікаційного та програмно-апаратного забезпечення інформаційних систем та технологій, Інтернету речей (ІоТ), комп'ютерноінтегрованих систем та системної мережної структури, управління ними. ФК 4 Здатність проєктувати, розробляти та використовувати засоби реалізації інформаційних систем, технологій та інфокомунікацій (методичні, інформаційні, алгоритмічні, технічні, програмні та інші) ФК 11 Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів. ФК 13 Здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень. ФК 15 Здатність до алгоритмічного мислення при розробці програмного забезпечення інформаційно-управляючих систем. І таким чином, сприяти більш глибшому розумінню студентом прикладних задач; сформувати математичний фундамент інженера комп'ютерних систем, здатного використовувати сучасний математичний апарат для дослідження, опису, аналізу, проектування алгоритмів для розв'язку задач.

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

Програмні результати навчання, на формування та покращення яких спрямована дисципліна: ПРН 2 Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв'язанні задач проєктування і використання інформаційних систем та технологій. ПРН 4 Проводити системний аналіз об'єктів проєктування та обґрунтовувати вибір структури, алгоритмів та способів передачі інформації в інформаційних системах та технологіях; оволодіння основними поняттями теорії алгоритмів; ПРН 12 Знати та володіти навичками та уміннями мовної діяльності, вміння спілкуватися в діалоговому режимі в галузі професійної діяльності з колегами та експертами предметних областей. ПРН 22 Використовувати методи математичного та імітаційного моделювання при розробці та проєктуванні інформаційних управляючих систем та технологій підтримки прийняття управлінських рішень. Тобто ознайомлення з технологіями дослідження, аналізу розробки та застосування алгоритмів; набуття практичних навичок використання методів і засобів проектування та дослідження алгоритмів.

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

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

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

3. Зміст навчальної дисципліни
Рівень вищої освіти Перший (бакалаврський)
Тема 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. Методи сортування спеціального призначення.

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

Базова

  1. Alfred V. Aho Data Structures and Algorithms Alfred V. Aho, Bell Laboratories, Murray Hill, New Jersey John E. Hopcroft, Cornell University, Ithaca, New York Jeffrey D. Ullman, Stanford University, Stanford, California / https://users.dcc.uchile.cl/~voyanede/cc4102/dS&A%20Book%20By%20Alfred%20-Aho.pdf -620 c.
  2. Goodman, S. and Hedetniemi, S. Introduction to the Design and Analysis of Algorithms. McGraw-Hill, New York. -301c
  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/

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

https://classroom.google.com/c/NzEwNzgwNjc0NDMz?cjc=uhg2hps ІС-41, https://classroom.google.com/c/NzEwNzgyOTE4MTI4?cjc=2gr7a7q ІС-42, https://classroom.google.com/c/NzEwNzgxNzM1OTU5?cjc=sp2vfcc ІС-43, https://classroom.google.com/c/NzEwNzgyNjUwMTk1?cjc=wlpomis ІС-44. https://www.youtube.com/channel/UCf9xOF5-J_HBrtx0R39_k7g відеолекції

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

5. Методика опанування навчальної дисципліни (освітнього компонента)
Форма навчання Денна
Семестрові (кредитні) модулі Лекції/Практичні роботи/СРС
Семестрова атестація МКР/іспит
Лекцій 54 год (27 відповідних пар за розкладом)
Лабораторні роботи 36 год (18 відповідних пар за розкладом)
СРС+МКР 90 годин

Лекційні заняття
№з/п Назва теми лекції та перелік основних питань (перелік дидактичних засобів, посилання на літературу та завдання на СРС)
1 Розділ 1. Побудова і аналіз алгоритмів 1. Поняття алгоритму. Знання й управління. Визначення знань, їхня роль у процесах управління, уявлення про процес вирішення проблем і необхідність представлення й обробки знань. Алгоритми і їхня роль. Стисла характеристика напрямків представлення знань. ([1] с.9, [2] с.16-28)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
2 Основні етапи побудови алгоритму. Алгоритми, розв'язність, обчислюваність, перераховність. Основні етапи повної побудови алгоритму. Структурне програмування зверху-вниз і правильність програм. Базові структури даних. Розвиток уявлень про структури даних. ([2] с.16-28) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 5], виконати завдання для домашніх робіт [3, стор. 8].
3 Класи складності алгоритмів. Методи оцінки складності алгоритмів. Класифікація. Оцінка часу виконання програм. ([1] с.28-32, [2] с.181-185, [3] с.60)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 5], виконати завдання для домашніх робіт [3, стор. 10].
4 Документування програмного продукту. Склад документації, порядок розробки та правила ведення. Тестування програмних продуктів. ([1] с.30, [2] с.67)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 3], виконати завдання для домашніх робіт [5, стор. 4], підготуватися до контрольної роботи.
5 Розділ 2. Методи розробки алгоритмів Вибір методу розв'язку задачі. Огляд методів розробки алгоритмів. ([2] с.106-108, [4] с.178-186) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 15], виконати завдання для домашніх робіт [3, стор. 25,26].
6 Метод проміжних цілей. Основна ідея методу проміжних цілей. Жадібні алгоритми. Евристики. ([1] с.276-291, [2] с.113)для домашніх робіт [3, стор. 25,26].Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
7 Метод пошуку з поверненням. Основна ідея методу пошуку з поверненням. Метод гілок та границь. Альфа-бета відсікання. ([1] с.291-301, [2] с.109-144)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [3, стор. 15], виконати завданняРекурсія. Поняття рекурсії. Область застосування рекурсії в програмуванні. Рекурсивні функції. Розвиток уявлень про рекурсивність арифметичних функцій. Обчислюваність, розв'язуваність та рекурсивність. ([1] с.70-76, [4] с.142-149)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
8 Структурне програмування. Низхідне проектування. Модульне програмування. Методи структурування програм. ([2] с.30-47, [4] с.178-186)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 5], виконати завдання для домашніх робіт [5, с. 6], підготуватися до контрольної роботи.
9 Розділ 3. Абстрактні типи даних Визначення абстрактного типу даних. Абстрактний тип даних, тип даних, структура даних. (с. 23-27 [1], с. 310-311 [4], с.47-84 [2], с.75-245 [3]) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].
10 АТД <<Список>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.45-57, [4] с.310-311) АТД <<Стек>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.58-60, [4] с.312-316) АТД <<Черга>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.57-65, [4] с.316-325)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
11 3. АТД <<Однозв'язний лінійний список>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.60-66, [4] с.319-325) АТД <<Двозв'язний лінійний список>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.57-58) АТД <<Відображення>>. Реалізація за допомогою масиву та за допомогою покажчиків. ([1] с.66-68)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].
12 АТД <<Дерево>>. Реалізація за допомогою масиву та за допомогою покажчиків. Бінарні дерева. ([1] с.77-99, [4] с.326-336)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].
13 Розділ4. АТД засновані на множинах. Задача пошуку Основні оператори множин. Базові поняття про операції з множинами. ([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].
14 Хешування. Поняття хешування. Відкрита за закрита схеми хешування. Методики вирішення колізій при закритому хешуванні. Реструктуризація хеш-таблиць ([1] с.116-128, [3] с.567-601). Відображення. Реалізація за допомогою хеш-таблиць. ([1] с.128-129) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
15 Черги з пріоритетами. Реалізації за допомогою списків, частково впорядкованих дерев та масивів. ([1] с.129-137) Мультисписки. Способи реалізації. Область застосування. ([1] с.137-143)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 7], виконати завдання для домашніх робіт [5, стор. 8].
16 Контрольна робота №1 Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор
17 BST-дерева. Способи реалізації. Область застосування. Збалансовані дерева. ([1] с.146-180, [3] с.523-562) Розширені BST-дерева. Способи реалізації. Область застосування. Ротація. ([3] с.528-540)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
18 Рандомізовані BST-дерева. Способи реалізації. Область застосування. ([3] с.528-540) Низхідні та висхідні 2-3-4-дерева. Способи реалізації. Область застосування. ([3] с.540-545)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 9], виконати завдання для домашніх робіт [5, стор. 10].
19 Червоно-чорні дерева. Способи реалізації. Область застосування. ([3] с.545-555) Інші дерева пошуку. AVL-дерева. 2-3-дерева. Дерева Байєра. Навантажені дерева. Область застосування. (с. 158-165 [1], 551-553 [3], 652-663 [3]) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 9].
20 Розділ 5. АТД засновані на множинах. Задача сортування 1. Задача сортування. Постановка задачі. Класифікація методів сортування. ([3] с.249-298, [1] с.228-235)Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 11], виконати завдання для домашніх робіт [5, стор. 12].
21 Елементарні методи сортування. Сортування вибором (с.257[3], с.232[1]). Сортування вставками (с.258[3], с.231[1]). Бульбашкове сортування (с.261[3], с.228[1]). Сортування методом Шелла с(.269[3], с.262[1]). Сортування по індексам та покажчикам (с.283[3]). Метод розподіляючого підрахунку (с.295[3]). Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
21 Швидке сортування. Базовий алгоритм. Характеристики ресурсоємності. Метод покращення. (с.299-329 [3], с. 235-243 [1], с.223-229[2]) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор. Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 13], виконати завдання для домашніх робіт [5, стор. 14].
23 Сортування злиттям. Двошляхове злиття. Абстрактне обмінне злиття. Низхідне сортування злиттям. Вдосконалення базового алгоритму. Висхідне сортування злиттям. Ресурсоємність сортування злиттям. (с.330-354 [3], с. 116-128 [1]) 2. Пірамідальне сортування. Алгоритми для дерев сортування. Ресурсоємність пірамідального сортування. (с.355-400 [3], с. 244-247 [1], с.229-240[2])Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 15], виконати завдання для домашніх робіт [5, стор. 16].
24 Порозрядне сортування. Область застосування. MSD та LSD алгоритми порозрядного сортування. (с.401-437 [3], с. 247-254 [1]) Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.
25 Методи сортування спеціального призначення. Парно-непарне сортування злиттям Бетчера. Сортуючі мережі. Зовнішнє сортування. Сортування-злиття. (с.438-473 [3])Дидактичні матеріали: Презентація Power Point, комп'ютер, проектор.Завдання на СРС: дати відповіді на контрольні запитання [5, стор. 17], виконати завдання для домашніх робіт [5, стор. 18].
26 Контрольна робота 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 MKP. Виконується протягом семестру. Захист. 2

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

Контрольна робота №1/2

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

Модульна контрольна робота (МКР)

МКР виконується після вивчення Розділів 1-3 та виконання практичних занять 1-5. Контрольна робота проводяться у середовищі Moodle. Кожен студент отримує індивідуальне завдання, відповідно до якого необхідно описати вибрану математичну модель, обгрунтувати обрану структуру даних, описати базовий алгоритм та провести його оцінку складності, реалізувати алгоритм в обраній мові програмування, провести базові тести, виконати оцінку якості коду за результатами яких побувати часові діаграми.

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

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

  1. Підготовки до аудиторних занять https://classroom.google.com/c/NzEwNzgwNjc0NDMz?cjc=uhg2hps ІС-41, https://classroom.google.com/c/NzEwNzgyOTE4MTI4?cjc=2gr7a7q ІС-42, https://classroom.google.com/c/NzEwNzgxNzM1OTU5?cjc=sp2vfcc ІС-43, https://classroom.google.com/c/NzEwNzgyNjUwMTk1?cjc=wlpomis ІС-44. https://www.youtube.com/channel/UCf9xOF5-J_HBrtx0R39_k7g відеолекції

  2. Виконання лабораторних робіт https://classroom.google.com/c/NzEwNzgwNjc0NDMz?cjc=uhg2hps ІС-41, https://classroom.google.com/c/NzEwNzgyOTE4MTI4?cjc=2gr7a7q ІС-42, https://classroom.google.com/c/NzEwNzgxNzM1OTU5?cjc=sp2vfcc ІС-43, https://classroom.google.com/c/NzEwNzgyNjUwMTk1?cjc=wlpomis ІС-44.

  3. Виконання МКР (модульної контрольної роботи). Див методичку в гугл класі. https://classroom.google.com/c/NzEwNzgwNjc0NDMz?cjc=uhg2hps ІС-41, https://classroom.google.com/c/NzEwNzgyOTE4MTI4?cjc=2gr7a7q ІС-42, https://classroom.google.com/c/NzEwNzgxNzM1OTU5?cjc=sp2vfcc ІС-43, https://classroom.google.com/c/NzEwNzgyNjUwMTk1?cjc=wlpomis ІС-44.

Самостійна робота
Тема Години
Основні етапи побудови алгоритму. 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

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

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

  1. Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються: "Положенням про організацію освітнього процесу в Національному технічному університеті України Київському політехнічному інституті імені Ігоря Сікорського";
  2. правила відвідування занять: заборонено оцінювати присутність або відсутність здобувача на аудиторному занятті, в тому числі нараховувати заохочувальні або штрафні бали. Відповідно до РСО даної дисципліни бали нараховують за відповідні види навчальної активності на лекційних та практичних заняттях.
  3. правила поведінки на заняттях: студент має можливість отримувати бали за відповідні види навчальної активності на лекційних та практичних заняттях, передбачені РСО дисципліни. Використання засобів зв’язку для пошуку інформації на гугл-диску викладача, в інтернеті, в дистанційному курсі на платформі Сікорський здійснюється за умови вказівки викладача;
  4. політика дедлайнів та перескладань: якщо студент не проходив або не з’явився на МКР (без поважної причини), його результат оцінюється у 0 балів. Перескладання результатів МКР не передбачено;
  5. політика щодо академічної доброчесності: Кодекс честі Національного технічного університету України «Київський політехнічний інститут» https://kpi.ua/files/honorcode.pdf встановлює загальні моральні принципи, правила етичної поведінки осіб та передбачає політику академічної доброчесності для осіб, що працюють і навчаються в університеті, якими вони мають керуватись у своїй діяльності, в тому числі при вивченні та складанні контрольних заходів з дисципліни «Системи автоматизації»;
  6. при використанні цифрових засобів зв’язку з викладачем (мобільний зв’язок, електронна пошта, спілкування на форумах та у соцмережах тощо) необхідно дотримуватись загальноприйнятих етичних норм, зокрема бути ввічливим та обмежувати спілкування робочим часом викладача.

Політика виставлення оцінок:

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

Відвідування є обов'язковим

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

Порядок зарахування пропущених занять.

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

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

Політика академічної поведінки та доброчесності:

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

Норми академічної етики:

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

Дотримання академічної доброчесності студентів й викладачів

Pегламентується: – Кодекс честі Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікоського» (https://kpi.ua/code); – Статут КПі ім. Ігоря Сікорського (https://kpi.ua/statute);

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

Розподіл балів по дисципліні
Види контролю бали
Лекції (тестування) 24 лекції що оцінюються 1
Практичні роботи (12 робіт) 4
Контрольна робота ( 2 роботи) 5
МКР 18
Іспит 40

R=(24 * 1 + 12 * 4 + 2 * 5 + 18)*0,6+40=100

7.1 Поточний контроль:

вправи на лекційних заняттях або тестування, МКР, виконання та захист практичних робіт.

Тестування по матеріалам лекційних занять

Ваговий бал 1. Максимальна кількість балів за тестування – 1 бал * 24 лекції що оцінюються = 24 балів. Тестування проводиться у системі дистанційного навчання GoogleClass та доступне протягом 5 робочих днів після завершення поточної лекції. У деяких випадках термін проходження тестування може бути продовжений лектором. Тривалість проходження одного тестування – 10 хвилин. Кількість спроб – одна. У деяких випадках, що пов’язані з технічними проблемами студентів, може надатися повторна спроба на окремі тестування. Кожне тестування містить 5 запитань різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо). Критерії оцінювання:

  • запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 0,2 бал, невірна відповідь – 0 балів;
  • запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,025 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 0,1 балів) – невірна відповідь – 0 балів, частково вірна відповідь – 0,01-0,09 балів, вірна відповідь 0,1 бал.

Практичні роботи

Ваговий бал. Практичні роботи - ваговий бал 4. Максимальна кількість балів за всі практичні роботи складає 4 бали * 12 роботи = 24 бали. На практичних роботах студенти перевіряють працездатність написаних програм за попередньо вирішеними вдома задачами. Для допуску до поточної практичної роботи необхідно мати Протокол, оформлений відповідно до норм оформлення технічної документації, який має містити всі необхідні пункти, відповідно до Методичних вказівок. Також для допуску до практичної роботи (окрім 1-ї) необхідно захистити попередню. Студенти, що не захистили попередню практичної роботу можуть бути не допущені до виконання наступної. Практичні роботи виконуються бригадою. Критерії оцінювання практичної роботи з ваговим балом 4:

  • вірно вирішено всі задачі, зображено блоксхему алгоритму, продемонстрована працездатність всіх програм (кодів), вірні відповіді на запитання до захисту – 4 бали;
  • вірно вирішено всі задачі, продемонстрована працездатність всіх програм (кодів), відповіді на питання до захисту мають неточності – 2-3,9 бали;
  • вірно вирішено всі задачі, але деякі з них містять помилки або неточності, продемонстрована працездатність не всіх програм (кодів), відповіді на питання до захисту мають неточності – 1-1,9 бали;
  • вірно вирішено всі задачі, продемонстрована працездатність не всіх програм (кодів), відповіді на питання до захисту мають неточності – 0-0,9 балів;
  • практичнаа робота не виконана або протокол не представлений – повертається на відпрацювання або доопрацювання. УВАГА! Захист всіх практичних робіт є умовою допуску до складання іспиту. Студенти, що на момент консультації перед екзаменом не захистили практичні роботи, не допускаються до основної здачі та готуються до перескладання. УВАГА! Для допуску до перескладання іспиту треба у визначений викладачем термін здати всі заборгованості по практичним роботам.

Модульна контрольна робота

Ваговий бал – 18. Модульна контрольна робота (МКР) виконується протягом семестру та захищається на останньому з лабораторних занять, але обовязково після вивчення Розділу 1 та виконання проктичних занять 1-5. Критерії оцінювання модульної контрольної роботи: На модульній контрольній роботі студент виконує 2 завдання. Кожне завдання оцінюється від 0 до 9 балів:

  • вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм відповідає умові – 9 балів;
  • вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм частково відповідає умові – 6-8,9 балів;
  • вірно виконаний завдання, сформована мат модель, обгрунтовано структуру даних, зображено алгоритм та оцінено його складність, складена програма, виконана тестова симуляція методом часових діаграм не відповідає умові – 3-5,9 балів;
  • задачу виконано з помилками, програма складена не вірно або виконаний вірно тільки алгоритм – 2-3,9 балів;
  • алгоритм та розрахунки виконано з помилками, програма не компілюється – 0-1,9 балів.

7.2 Календарний контроль:

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

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

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

Умови допуску до семестрового контролю:

  1. 24 бали мінімально позитивна оцінка за лабораторні роботи
  2. 6 балів мінімально за дві контрольні
  3. 10 мінімум балів за МКР
  4. 24 тестування по лекції

тобто, - зарахування усіх лабораторних робіт та МКР.

Форма семестрового контролю – іспит Максимальна сума балів за роботу у семестрі складає 60. Необхідною умовою допуску до іспиту - виконані та захищені лабораторні роботи, МКР, семестровий рейтинг не менше 30 балів.

Іспти містить дві складові: теоретичну та практичну. Теоретична складова направлена на перевірку набутих в результаті вивчення освітнього компонента знань студентів у вигляді тестування за лекційним матеріалом семестру. Кожне тестування містить 20 запитань різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо). Максимальна кількість балів за тестування складає 20 питань * 1 бал = 20 балів. Практична складова передбачає перевірку набутими студентами умінь синтезувати алгоритми, проєктувати та перевіряти відповідно до умов завдання з розробки інформаційних систем. Кожному студенту надається окрема задача, відповідно до умов якої необхідно виконати моделювання, скласти алгоритм та програму у вибраному студентом середовищі програмування та виконати симуляцію методом часових діаграм. Максимальна кількість балів за задачу складає 20 балів.

Критерії оцінювання теоретичної складової

  • запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 1 бал, невірна відповідь – 0 балів;
  • запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,25 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 1 бал) – невірна відповідь – 0 балів, частково вірна відповідь – 0,1-0,9 балів, вірна відповідь 1 бал.

Критерії оцінювання практичної складової

  • вірно виконаний синтез алгоритму, складена програма, виконана симуляція роботи розробленого програмного засобу методом часових діаграм відповідає умові – 20 балів;
  • вірно виконаний синтез алгоритму, складена програма, виконана роботи розробленого програмного засобу симуляція методом часових діаграм частково відповідає умові – 15-19 балів;
  • синтез виконано з помилками, складена програма, виконана симуляція роботи розробленого програмного засобуметодом часових діаграм не відповідає умові – 10-14 балів;
  • синтез виконано з помилками, програма складена не вірно але компілюється – 5-9 балів;
  • синтез виконано з помилками, програма не складена або не компілюється – 0-4 бали.

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

7.5 Додаткові (бонусні) бали

Рейтинговою системою оцінювання передбачені додаткові бали за виконання додаткових завдань. Один студент не може отримати більше ніж 10 бонусних балів у семестрі. Бонусні бали можуть бути отримані за такі види робіт: «Івенти», «Вправи на лекційних заняттях», «Додаткові лекції».

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

Вправи на лекційних заняттях Ваговий бал 0,25. Максимальна кількість балів за всі виконані вправи – 0,25 балів * 24 лекцій = 6 балів (на лекціях де заплановано КР1 та КР2, по 10 хв кожна, не проводиться додаткове опитування) Вправи проводяться тільки на лекційних заняттях і доступні тільки у спеціально виділений викладачем час. В інший час незалежно від обставин вправи недоступні. Вправи виконуються студентами у системі дистанційного навчання. Тривалість проходження однієї вправи від 2 до 5 хвилин, в залежності від її складності. Тривалість вправи попередньо озвучується викладачем. Кількість спроб – одна. Після кожної вправи проводиться коротке обговорення її результатів. Кожна вправа – це тестування, яке містить 1 завдання різного формату (вибір правильного варіанту з переліку; вірно/невірно; визначити відповідність; чисельна відповідь; вибір пропущених слів; перетаскування на зображення тощо).

Критерії оцінювання

  • запитання типу «вибір правильного варіанту з переліку», «вірно/невірно», «чисельна відповідь» оцінюються однозначно: вірна відповідь – 0,05 бал, невірна відповідь – 0 балів;
  • запитання, на які немає однієї конкретної відповіді, типу «визначити відповідність», «вибір пропущених слів», «перетаскування на зображення» оцінюються у відповідності до кількості елементів у тесті (наприклад, якщо треба вставити 4 слова у текст, то студент отримає по 0,0125 балів за одне правильне вставлене слово, а за всі 4 правильно вставлені слова отримає відповідно 0,05 балів) – невірна відповідь – 0 балів, частково вірна відповідь – 0,01-0,49 балів, вірна відповідь 0,5 балів.

Додаткові лекції Додаткові лекції – це теми на самостійне опрацювання, які забезпечать здобувачам посилення теоретичних знань з дисципліни. Ваговий бал 0,5. Максимальна кількість балів за опрацювання додаткових лекції – 0,5 балів * 15 лекцій (теми вказано нижче) = 7,5 балів. Бали здобувачі отримують за завантаження у систему GoogleClass конспекту опрацьованої лекції.

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

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

  1. Ієрархія класів складності.
  2. Повнота задач NP-класу.
  3. Розгляд евристичних алгоритмів.
  4. Дослідження застосування АТД в різноманітних алгоритмах.
  5. Використання хешування в криптографії.
  6. Використання хешування в різних галузях діяльності.
  7. Дерева пошуку в теорії ігор.
  8. Дерева пошуку в задачах прйняття рішень.
  9. Сортування Timsort.
  10. Інтроспективне сортування.
  11. Блукаюче сортування.
  12. Млинцеве сортування.
  13. Топологічне сортування.
  14. Мережеве сортування.
  15. Зовнішнє сортування ( методи не розглянуті в лекці).

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

Складено Дорошенко Катерина С. ст викладач каф. ІСТ

Ухвалено кафедрою інформаційних систем та технологій ФІОТ (протокол № 16 від 12.06.2024 р.)

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