ТЕОРІЯ АЛГОРИТМІВ

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

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

Другий семестр

http://rozklad.kpi.ua/Schedules/ViewSchedule.aspx?v=c6746e2a-d8f8-4f9f-bb1d-9b0912b188ef
Мова викладання Українська
Інформація про
керівника курсу / викладачів

Лектор: ст. викладач. кафедри ІСТ Халус О.А. selena.ua@gmail.com

Лабораторні заняття: ас. кафедри ІСТ Степанов А.С.
Розміщення курсу https://do.ipo.kpi.ua/course/view.php?id=4320

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

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

Предметом вивчення дисципліни є технології, методи та засоби теорії алгоритмів.

Завдання вивчення дисципліни:

  • освоєння основних теоретичних понять теорії алгоритмів та структур даних;

  • ознайомлення з сучасними технологіями формування і аналізу структур даних;

  • набуття навичок використання технологій теорії алгоритмів для розв’язання.

Мета навчальної дисципліни.

Метою навчальної дисципліни є формування у студентів здатностей:

  • засвоєння базових знань з алгоритмів та структур даних;

  • формування представлення про суть процесів мислення, можливості їх формалізації та шляхах реалізації цієї ідеї

  • здатність використовувати професійно профільовані знання й уміння в галузі практичного використання комп’ютерних технологій;

  • забезпечити можливість переходу до використання спеціалістами-випускниками сучасного математичного апарату для вирішення проблем управління та проектування.

Основні завдання навчальної дисципліни.

Згідно з вимогами освітньо-професійної програми студенти після засвоєння навчальної дисципліни мають продемонструвати такі результати навчання:

знання:

  • алгоритми сортування,

  • злиття та пошуку,

  • комбінаторні алгоритми,

  • рекурсивні алгоритми,

  • фундаментальні алгоритми на графах та деревах,

  • геометричні алгоритми,

  • евристичні алгоритми,

  • алгоритмічні стратегії.

уміння:

  • аналізувати , теоретично та експериментально досліджувати методи, алгоритми, програми апаратно-програмних комплексів і систем

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

досвід:

  • адекватне моделювання предметних областей, створення сучасних програмних та інформаційних систем.;

  • здатність використовувати професійно профільовані знання й уміння в галузі практичного використання комп’ютерних технологій.

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

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

СПЕЦІАЛЬНІ (ФАХОВІ, ПРЕДМЕТНІ) КОМПЕТЕНТНОСТІ:

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

В результаті освоєння дисципліни повинні бути сформовані такі ПРОГРАМНІ РЕЗУЛЬТАТИ НАВЧАННЯ

  • ПРН-2 Застосовувати знання фундаментальних і природничих наук, системного аналізу та
    технологій моделювання, стандартних алгоритмів та дискретного аналізу при
    розв’язанні задач проектування і використання інформаційних систем та технологій

  • .

  • ПРН-3. Використовувати базові знання інформатики й сучасних інформаційних систем та
    технологій, навички програмування, технології безпечної роботи в комп'ютерних
    мережах, методи створення баз даних та інтернет-ресурсів, технології розроблення
    алгоритмів і комп’ютерних програм мовами високого рівня із застосуванням
    об’єктно-орієнтованого програмування для розв’язання задач проектування і
    використання інформаційних систем та технологій

  • ПРН-4. Проводити системний аналіз об’єктів проектування та обґрунтовувати вибір
    структури, алгоритмів та способів передачі інформації в інформаційних системах та
    технологіях

  • ПРН-16. Застосовувати знання відповідних мов програмування та ефективно
    використовувати методи машинного навчання в задачах створення компонентів
    штучного інтелекту в інформаційних система з використання аналізу та оцінки
    складності алгоритмів рішення

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

Пререквізити:

  • Вища математика.

  • Програмування.

Постреквізити:

  • Компютерні мережі.

  • Бази даних.

  • Проектування інфомаційних систем

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

Розділ 1. Алгоритми
Алгоритми та обчислення
Розробка алгоритмів. Метод сортуванням включення
Метод декомпозиції. Сортування злиттям. Підрахунок інверсій
Рекурентні співвідношення
Швидке сортування
Лінійне сортування
Розділ 2. Структури даних
Піраміди
Хеш-таблиці
Бінарні дерева пошуку
Додаткові структури даних
Розділ 3. Підходи до розробки алгоритмів
Жадібні алгоритми
Динамічне програмування
Розділ 4. Класи складності
Теорія складності
Класи Р та NP
NP-повні задачі
Класи за межами NP

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

Основна

  1. Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

    1. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.

  3. Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms. McGraw-Hill Science/Engineering/Math. ISBN-13 978-0073523408

Додаткова

  1. Лисовик Л.П., Редько В.Н. Алгоритми та формальні системи. – К., 1981.

  2. Python's documentation, tutorials, and guides are constantly evolving. –[Електронний ресурс]. – Режим доступу: https://docs.python.org/3/

  3. Tutorialspoint / Python – [Електронний ресурс]. – Режим доступу: http://www.tutorialspoint.com/python/

  4. Самоучитель Python – [Електронний ресурс]. – Режим доступу: https://pythonworld.ru/samouchitel-python

  5. 1. Christopher Pal, Mark Hall, Eibe Frank, Ian Witten. Data Mining: Practical Machine Learning Tools and Techniques, 4rd ed. / Morgan Kaufmann, 2016.

  6. 2. Jennifer Reese, Richard Reese. Java for Data Science / Packt Publishing, 2017.

  7. 3. Bostjan Kaluza. Machine Learning in Java / Packt Publishing, 2016.

  8. 4. David Hand, Heikki Manilla, Padhraic Smyth. Principles of data mining / MIT Press, 2001.

  9. 5. Jason Bell. Machine Learning: Hands-On for Developers and Technical Professionals / John Wiley & Sons, 2014.

  10. 6. Michael Abernethy. Data mining with WEKA / IBM developerWorks, 2010.

  11. 7. Parsaye K A. Characterization of Data Mining Technologies and Processes. The Journal of Data Warehousing. 1998.№ 1

  12. 8. Newquist H. P Data Mining: The AI Metamorphosis. Database Programming and Design. - 1996. № 9

  13. 9. Parsaye K A Characterization of Data Mining Technologies and Processes. The Journal of Data Warehousing. 1998.№ 1

  14. 10. Brand E., Gerritsen R. Data Mining and Knowledge Discovery DBMS. 1998. № 7

  15. 11. John F. Elder IV & Dean W. AbbottKDD-98: A Comparison of Leading Data Mining Tools Fourth International Conference on Knowledge Discovery & Data Mining, August 28, 1998. New York

  16. 12. Damiaan Zwietering, Helena Gottschalk, Hosung Kim, Joerg Reinschmidt Intelligent Miner for Data: Enhance Your Business Intelligence J June 1999, International Technical Support Organization, SG 245422

  17. 13. Jiawei Han and Micheline Kamber Data Mining: Concepts and Techniques, The Morgan Kaufmann Series in Data Management Systems, Jim Gray, Series Editor Morgan Kaufmann Publishers, August 2000. 550 pages. ISBN 1-55860-489-8

  18. 14. Ananth Y. Grama, Naren Ramakrishnan Data Mining-Guest Editors' Introduction: From Serendipity to Science,

  19. Computer, vol. 32, no. 8, pp. 34-37, August, 1999

  20. 15. Ahsan habib, Amalendu Roy, Baojing Lu, David Diaz, Jingkai Zhou, Maria Canton, Md Abdul Maleq Khan, Qin Ding, Qinghua Zou, Qun Wei Data Mining Survey 2000

  21. 16. B. Scholkopf, G. Ratsch, K. Muller, K. Tsuda, S. Mika An Introduction to Kernel-Based Learning Algorithms IEEE Neural Networks, 12(2):181-201, May 2001

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

Для викладання дисципліни необхідні наступні ресурси:

  • В лекційній аудиторії має бути комп’ютер з доступом до Moodle, а також проектор;

  • В аудиторії, де проводяться лабораторні роботи, мають бути робочі станції з доступом до Інтернету і браузерами, в кількості студентів у групі, для проходження підсумкового тестів. Maє бути забезпечений доступ студентів до Moodle та Google classroom.

  • Програмне забезпечення: бібліотеки R та Python, https://bigml.com/, https://www.philippe-fournier-viger.com/spmf/, які розповсюджуються по безкоштовній ліцензії.

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

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

Кредитів - 6,

Годин – 180:

Аудиторних годин – 90:

Лекції – 54,

Лабораторні роботі – 36,

Самостійна робота – 90.

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

1. Опорний конспект лекцій

2. Навчальні посібники

3. Силабус

4. Програмне забезпечення: бібліотеки R та Python, https://bigml.com/, https://www.philippe-fournier-viger.com/spmf/.

5. Комплект завдань для поточного оцінювання навчальних досягнень,

6. Засоби підсумкового контролю (комплект завдань для підсумкового контролю).

МЕТОДИ НАВЧАННЯ:

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

- Пояснювально-ілюстративного методу Послідовна та логічно ув’язана подача матеріалу надає уявлення та знання у його логічної цілісності

- Метод проблемного викладу надає уяву та методи отримання нових знань та фактів з використанням вже відомих фактів та тверджень

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

Лабораторні заняття проходять з використанням

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

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

Самостійна робота з можливістю особистих консультацій з викладачем

Структура кредитного модуля

Назви розділів і тем
Всього
Лекції Лабораторні (комп’ютерний практикум) СРС
4 180 54 36 90
Розділ 1. Алгоритми
Тема 1. Алгоритми та обчислення 10 2 2 6
Тема 2. Аналіз алгоритмів 16 6 4 6
Тема3. Метод декомпозиції 12 4 4 4
Тема 4. Рекурентні співвідношення 14 6 8
Тема 5. Швидке сортування 12 4 4 4
Тема 6. Сортування за лінійний час 6 2 4
Розділ 2. Структури даних
Тема 1. Піраміди 10 2 4 4
Тема 2. Хеш-таблиці 12 2 4 6
Тема 3. Бінарні дерева пошуку 10 2 4 4
Тема 4. Додаткові структури даних 8 4 2 2
Модульна контрольна робота 1 8 2 6
Розділ 3 Підходи до розробки алгоритмів
Тема 1. Жадібні алгоритми 16 4 4 8
Тема 2. Динамічне програмування 16 4 4 8
Розділ 4 Теорія складності
Тема 1. Складність NP 8 2 6
Тема 2. Задача SAT 2 2
Тема 3. Гамільтонові цикли 8 2 6
Тема 4. Клас задач PSPACE 12 4 8

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

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

Лекція 1. Алгоритми та обчислення. Поняття алгоритму. Для чого вивчати алгоритми? Ефективність алгоритмів. Золоте правило розробників алгоритмів.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Глава 1.

Лекція 2. Аналіз алгоритмів. Сортування включенням. Машина з довільним доступом до пам’яті.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Глава 2, розділи 2.1, 2.2. Глава 3, розділ 3.1.

Лекція 3. Аналіз алгоритмів Аналіз алгоритму сортування методом включення.

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Глава 2, розділи 2.1, 2.2. Глава 3, розділ 3.1.

Лекція 4. Аналіз алгоритмів. Порядок зростання. Асимптотичні позначення. Порівняння функцій.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

Глава 2, розділи 2.1, 2.2. Глава 3, розділ 3.1.

Лекція 5. Метод декомпозиції. Метод декомпозиції. Аналіз алгоритму сортування злиттям.

Література

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

Глава 2, розділ 2.3.

Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms.

McGraw-Hill Science/Engineering/Math. ISBN-13 978-0073523408. Глава 2, розділ 2.5.

Лекція 6. Метод декомпозиції Підрахунок інверсій. Добуток матриць.

Література

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

Глава 2, розділ 2.3.

Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms.

McGraw-Hill Science/Engineering/Math. ISBN-13 978-0073523408. Глава 2, розділ 2.5.

Лекція 7. Рекурентні співвідношення. Метод підстановки. Метод дерев рекурсії.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 4.

Лекція 8. Рекурентні співвідношення. Основний метод.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 4.

Лекція 9. Рекурентні співвідношення. Доведення основної теореми.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 4.

Лекція 10. Швидке сортування. Опис швидкого сортування. Ефективність швидкого сортування. Випадкова версія швидкого сортування. Аналіз швидкого сортування.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 7, Глава 9, розділ 9.1, 9.2.

Лекція 11. Швидке сортування. Порядкові статистики. Вибір за лінійний час.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 7, Глава 9, розділ 9.1, 9.2.

Лекція 12. Сортування за лінійний час. Нижня оцінка алгоритмів сортування. Сортування підрахунком. Сортування за розрядами.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 8, розділи 8.1 – 8.3.

Лекція 13. Піраміди. Означення піраміди. Підтримка властивості піраміди. Створення піраміди. Алгоритм пірамідального сортування. Черги з пріоритетами.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 6.

Лекція 14. Хеш-таблиці. Таблиці з прямою адресацією. Хеш-таблиці. Уникнення колізій за допомогою ланцюгів. Хеш-функції. Відкрита адресація.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 11.

Лекція 15. Бінарні дерева пошуку. Бінарні дерева пошуку. Робота з бінарними деревами пошуку. Вставка та видалення.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 12.

Лекція 16. Додаткові структури даних . Червоно-чорні дерева. Динамічні порядкові статистики.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Глави 13, 14, 19.

Лекція 17. Додаткові структури даних .Біноміальні піраміди. Операції над біноміальними пірамідами.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Глави 13, 14, 19.

Лекція 18. Жадібні алгоритми. Задача складання розкладів. Складання розкладів з мінімізацією запізнень. Складання розкладів із вагами робіт.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 16.

J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005. Глава 4.

Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms.

McGraw-Hill Science/Engineering/Math. ISBN-13 978-0073523408. Глава 5.

Лекція 19. Жадібні алгоритми.. Мінімальні кістякові дерева. Алгоритм Прима. Алгоритм Крускала.

Література:

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001)

[1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.Глава 16.

J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005. Глава 4.

Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2006) Algorithms.

McGraw-Hill Science/Engineering/Math. ISBN-13 978-0073523408. Глава 5.

Лекція 20. Динамічне програмування. Задача складання розкладу зважених інтервальних робіт. Принципи динамічного програмування. Задача пошуку підмножин сум.

Література:

J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005. Глава 6.

Лекція 21. Динамічне програмування. Задача про рюкзак. Вирівнювання послідовностей.

Література:

J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005. Глава 6.

Лекція 22. Складність NP. Задачі класу NP. Редукція.

Література:

Манін Ю.І. Обчислювальне та необчислювальне. – К., 2007.

Катленд Н. Обчислювальність. - 2012.

Лекція 23. Задача SAT. 3- SAT проблеми. Зведення до 3- SAT. Задача перевірки.

Література:

Манін Ю.І. Обчислювальне та необчислювальне. – К., 2007.

Катленд Н. Обчислювальність. - 2012.

Лекція 24. Гамільтонові цикли. Задача пошуку гамільтонового циклу. Зведення гамільтонового циклу до TSP.

Література:

Манін Ю.І. Обчислювальне та необчислювальне. – К., 2007.

Катленд Н. Обчислювальність. - 2012.

Лекція 25. Клас задач PSPACE. Означення класу задач PSPACE.

Література:

Манін Ю.І. Обчислювальне та необчислювальне. – К., 2007.

Катленд Н. Обчислювальність. - 2012.

Лекція 26. Клас задач PSPACE. QSAP – задача. Фільтрація вхідних даних.

Література:

Манін Ю.І. Обчислювальне та необчислювальне. – К., 2007.

Катленд Н. Обчислювальність. - 2012.

Усього 54 год.

Деякі теми можуть переставлятися місцями чи доповнюватися на розсуд викладача. Кількість годин, відведених на певну тему. Теж може змінюватися.

Лабораторні заняття

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

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

Тематично-календарний план проведення лабораторних занять

№ з/п Назва комп’ютерного практикуму Кількість ауд. годин
Вступне 2
Л.р.№ 1 Проектування і аналіз алгоритмів внутрішнього сортування 4
Л.р.№ 2 Метод декомпозиції. Сортування злиттям. Підрахунок інверсій 4
Л.р.№ 3 Швидке сортування Quick_Sort 4
Л.р.№ 4 Прикладні задачі теорії графів 4
Л.р.№ 5 Піраміди 4
Л.р.№ 6 Хеш-таблиці. Додаткові структури даних 4
Л.р.№ 7 Бінарні дерева пошуку 4
Л.р.№ 8 Жадібні алгоритми 4
Л.р.№ 9 Динамічне програмування 4

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

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

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

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

№ з/п Назва теми, що виноситься на самостійне опрацювання Кількість годин СРС
Розділ 1. Алгоритми . Тема 1. Алгоритми та обчислення Характеристики алгоритмів: швидкість роботи, пам’ять 6
Розділ 1. Алгоритми . Тема 5. Швидке сортування Рандомізоване швидке сортування. Порядкові статистики. Алгоритм вибору порядкових статистик на основі методу швидкого сортування 4
Розділ 1. Алгоритми Тема 4. Рекурентні співвідношення Означення Медіани 8
Розділ 1. Алгоритми . Тема 6. Сортування за лінійний час Сортування підрахунком (counting sort). Сортування за розрядами (radix sort) 4
Розділ 1. Алгоритми . Тема 2. Аналіз алгоритмів Нижня оцінка алгоритмів сортування, які засновані на порівняннях 6
Розділ 2. Структури даних Тема 1. Піраміди Підтримка властивості піраміди. Збільшення значення ключа у пірамідах. Черги з пріоритетами 4
Розділ 2. Структури даних Тема 2. Хеш-таблиці Метод ланцюгів. Відкрита адресація 6
Розділ 2. Структури даних Тема 3. Бінарні дерева пошуку Метод ділення 4
Підготовка до модульної контрольної роботи 6
Розділ 3 Підходи до розробки алгоритмів Тема 2. Динамічне програмування Динамічні порядкові статистики. Задача пошуку мінімального кістякового дерева в графі. Задача вирівнювання послідовностей 8
Розділ 3 Підходи до розробки алгоритмів Тема 1. Жадібні алгоритми Задача складання розкладу інтервальних робіт. Задача складання розкладу з мінімізацією максимального запізнення. Алгоритм Крускала 8
Розділ 4 Теорія складності Тема 1. Складність NP Поняття редукції задач: коли задача зводиться до іншої 6
Розділ 4 Теорія складності Тема 2. Задача SAT Задачі оптимізації (optimization problems) та задачі пошуку рішень (decision problems). Задача виконання булевої формули (3-SAT) до незалежної множинивершинного 6
Розділ 4 Теорія складності Тема 3. Гамільтонові цикли Відомі співвідношення між класами P та NP 6
Розділ 4 Теорія складності Тема 4. Клас задач PSPACE Задача перевірки логічної схеми. Теорема Кука-Левіна 8

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

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

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

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

Студенти можуть додатково до завдань курсу проходити аналогічні дистанційні курси, але рейтингові бали за це зараховуватися не будуть. Це пов’язано з неможливістю контролю дотримання студентами принципів академічної доброчесності при їх проходженні та із тим, що всі студенти мають знаходитися в однакових умовах при вивченні курсу.

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

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

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

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

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

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

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

  1. Лабораторні роботи

Вагові бали кожної практичної роботи наведені у таблиці 1. Сумарний ваговий бал за даний контрольний захід складає 71 балів.

Критерії оцінювання лабораторних робіт включають якість її виконання, звіту, захисту та відповідь на запитання (таблиця 1).

Таблиця 1 – Вагові бали та критерії оцінювання лабораторної роботи

Назва роботи Бали
Виконання Звіт Захист Дод Сума
Л.р.№ 1 Проектування і аналіз алгоритмів внутрішнього сортування 2 1 2 5
Л.р.№ 2 Метод декомпозиції. Сортування злиттям. Підрахунок інверсій 3 2 3 2 7(9)
Л.р.№ 3 Швидке сортування Quick_Sort 3 2 3 2 7(9)
Л.р.№ 4 Прикладні задачі теорії графів 3 2 3 1
Л.р.№ 5 Піраміди 3 2 3 2 7(9)
Л.р.№ 6 Хеш-таблиці. Додаткові структури даних 3 2 3 1 7(8)
Л.р.№ 7 Бінарні дерева пошуку 3 2 3 7
Л.р.№ 8 Жадібні алгоритми 3 2 3 1 7
Л.р.№ 9 Динамічне програмування 3 2 3 1 7
Разом за практичні роботи 27 17 27 8 71(79)

Критерії оцінювання практичних робіт 1-7:

“відмінно” – робота виконана та захищена без зауважень, (7;5) балів;

“добре” – достатньо повне виконання роботи з деякими похибками, (6-3;4,5-3) балів;

“задовільно” – неповна відповідь (не менше 60% потрібної інформації), 2,5-1 бала;

“незадовільно” – при виконанні або під час захисту роботи були виявлені помилки, 0,9-0 балів.

2. Тестування

Ваговий бал кожного тесту1-5 7 балів, а для тесту 6 10 балів. Ваговий бал– 45 балів

Критерії оцінювання кожної частини тесту:

  • “відмінно”, повна відповідь (не менше 90% потрібної інформації)

    –6,5 -7 балів;

  • “добре”, достатньо повна відповідь (не менше 75% потрібної

    інформації), або повна відповідь з незначними помилками – 6,4-3,5 бала;

  • “задовільно”, неповна відповідь (не менше 60% потрібної

    інформації) та незначні помилки – 3,4-0,7 бала;

  • “незадовільно”, незадовільна відповідь–0 балів.

3. МКР

Критерії оцінювання МКР у вигляді тесту 7 Ваговий бал – 15 балів:

  • “відмінно”, повна відповідь (не менше 90% потрібної інформації)

    –13,5 -15 балів;

  • “добре”, достатньо повна відповідь (не менше 75% потрібної

    інформації), або повна відповідь з незначними помилками – 10-13 бала;

  • “задовільно”, неповна відповідь (не менше 60% потрібної

    інформації) та незначні помилки – 7-12,5 бала;

  • “незадовільно”, незадовільна відповідь–0-7 балів.

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

Ваговий бал– 10 балів.

Студенти готують доповіді та презентації до тем, самостійного опрацювання, виступають з ними.

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

  • “відмінно”, повна доповідь (не менше 90% потрібної інформації) –

    10 балів;

  • “добре”, достатньо повна доповідь (не менше 75% потрібної

    інформації), або повна доповідь з незначними помилками – 6-4 бала;

  • “задовільно”, неповна доповідь (не менше 60% потрібної інформації)

    та незначні помилки – 3-1,5 бала;

  • “незадовільно”, незадовільна доповідь, яка не розкриває змісту

    теми –1-0 балів.

Штрафні та заохочувальні бали:

  • лабораторні роботи мають чітку послідовність виконання;

  • за одну пару (здачі) студентом може бути здано не більше двох лабораторних робіт;

  • кожна лабораторна робота має кінцевий термін виконання до настання котрого студент має можливість отримати максимальну кількість балів;

  • при здачі лабораторних робіт (при формуванні черги на здачу) пріоритет мають студенти, які здають лабораторні роботи згідно графіку;

  • виконання додаткових завдань – дивись таблицю 1. Всього додадаткових балів 10, додаткові бали можна отримати тільки на першому тижні сдачі комп’ютерного практикуму.

Студенти готують доповіді та презентації до тем, самостійного опрацювання, виступають з ними.

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

  • “відмінно”, повна доповідь (не менше 90% потрібної інформації) –

    10 балів;

  • “добре”, достатньо повна доповідь (не менше 75% потрібної

    інформації), або повна доповідь з незначними помилками – 6-4 бала;

  • “задовільно”, неповна доповідь (не менше 60% потрібної інформації)

    та незначні помилки – 3-1,5 бала;

  • “незадовільно”, незадовільна доповідь, яка не розкриває змісту

    теми –1-0 балів.

Умови позитивної проміжної атестації

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

Для отримання “зараховано” з першої проміжної атестації (8 тиждень) студент повинен мати не менше ніж 13 балів (за умови, якщо на початок 8 тижня згідно з календарним планом контрольних заходів “ідеальний” студент має отримати 26 балів).

Для отримання “зараховано” з другої проміжної атестації (14 тиждень) студент повинен мати не менше ніж 41 бал (за умови, якщо на початок 14 тижня згідно з календарним планом контрольних заходів “ідеальний” студент має отримати 82 бали)

Умови зарахування лабораторних №5,6,7,9 за рахунок проходження курсів на ресурсі Coursera

При проходженні та отриманні сертифікату не менше ніж 85% з Перших два курса на Сoursera https://www.coursera.org/specializations/data-structures-algorithms#courses - Algorithmic Toolbox, Data Structures дають можливість закрити 5,6,7,9 лабораторні роботи на бали без урахування захисту. Максимальний бал 20 балів.

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

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

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

Розрахунок шкали рейтингу :

Згідно Додатку1 до наказу 7/86 від 8.05.2020 Національного технічного університету України “Кіївського політехнічного інституту імені Ігоря Сікорського” Про затведження Тимчасового регламенту проведення семестрового контролю в дистанційному режимі та Тимчасового регламенту організації і проведення захистів дипломних робіт/магістерських дисертацій та випускних екзаменів, пункту 3.15 семестровий контроль передбачений у формі залік з дисципліни “Алгоритми та структури даних” підхід щодо виставлення оцінки з освітньої компоненти за РСО-1 (“автоматом”) шляхом пропорційного перерахунку стартових балів у підсумкові бали за 100-бальною шкалою.

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

Таким чином:

Максимальна сума вагових балів контрольних заходів протягом семестру складає:

Rcб = 71+45+15=131бал

Залік виставляється автоматом, з урахуванням набраних балів за семестр та переводиться у відповідну 100 бальну систему.

Залікова складова , а саме:

де R – оцінка за 100-бальною шкалою;

Ri\ – сума балів, набраних здобувачем протягом семестру;

Rcб\ - максимальна сума вагових балів контрольних заходів протягом семестру.

Необхідною умовою допуску до заліку є:

  • виконання всіх комп’ютерних практикумів на оцінку не нижче ніж “задовільно”;

  • сума балів, набраних здобувачем протягом семестру не менше 60% від Rcб, тобто 78 балів.

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

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

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

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

Складено старший викладач Халус О.А.

Ухвалено кафедрою ІСТ (протокол №21 від 29.06.2023р

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