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

ID: 6623
Навчальна дисципліна професійної підготовки
Edition: 
2017.
Number of ECTS credits: 
4.00.
Contains calculation and graphic work
Final form of control: 
Test.
Teacher: 
Number of classroom classes: 
16 годин лекційних занять, 30 годин лабораторних робіт..

Анотація навчальної дисципліни

Мета дисципліни:

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

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

 

Програмні компетентності

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

 

Програмні результати навчання

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

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

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

 

Кількість аудиторних занять

16 годин лекційних занять, 30 годин лабораторних робіт.

 

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

  • Л – лекційні заняття;
  • ЛР – лабораторні роботи;
  • СРС – самостійна робота здобувача вищої освіти;
  • РГР – розрахунково-графічна робота;
  • МКР – модульна контрольна робота;
  • К – консультації.

 

Тематика та види навчальних занять

  • 1 тиждень
    • Л1. Вступ до теорії алгоритмів. Інтуїтивне визначення алгоритму. Методика розробки алгоритмів. Основні етапи комп'ютерного вирішення завдань. Аналіз алгоритмів [1, c. 13 - 15].  
    • ЛР1.  Аналіз алгоритмів та алгоритмічні стратегії [1, c. 13 - 15].  
    • СРС. К.
  • 2 тиждень
    • ЛР2.  Аналіз алгоритмів: Евкліда, решето Еротосфени, числа Фібоначчі [1, c. 13 - 15].  
    • СРС. К.
  • 3 тиждень
    • Л2. Алгоритми сортування. Прості сортування як спосіб швидкої реалізації алгоритму. Складні сортування як спосіб створення ефективних алгоритмів. Швидке сортування QuickSort. Сортування злиттям. Сортування підрахунком. Порозрядне сортування [4, 72-84].
    • ЛР3.  Алгоритми сортування. Прості та покращені алгоритми сортування[4, 72-84].
    • СРС. К.
  • 4 тиждень
    • ЛР4. Алгоритми сортування. Прості та покращені алгоритми сортування[4, 72-84].
    • СРС. К.
  • 5 тиждень
    • Л3. Базові структури алгоритмів. Зв'язковий список. Стек. Черга. Дек. Загальне уявлення структури даних [3, 38-42, 4, 96-115].
    • ЛР5. Зв'язковий список [3, 38-42, 4, 96-115].  
    • СРС. К.
  • 6 тиждень
    • ЛР6. Задача пошуку. Лінійний та бінарний пошук. [3, 127-148]
    • СРС. К.
  • 7 тиждень
    • Л4. Задача пошуку. Лінійний та бінарний пошук. Алгоритм бінарного пошуку. Складнощі роботи алгоритму бінарного пошуку [3, 127-148]
    • ЛР7. Реалізація бінарного пошуку. [3, 127-148,4]
    • СРС. К.
  • 8 тиждень
    • ЛР8. Реалізація пошуку з використанням хеш- таблиць [1,4, 239-242]. 
    • МКР1. СРС. К.
  • 9 тиждень
    • Л5. Пошук з використанням хеш- таблиць. Основи хеш-таблиць. Хеш-функції. Дозвіл колізій [4, 239-242].
    • ЛР9. Реалізація колізій в хеш- таблиці [1,4, 239-242,5].  
    • СРС. К.
  • 10 тиждень
    • ЛР10.  Графи: способи їх зберігання і обходу (в ширину і в глибину) [1,3, 83-120, 5]
    • СРС. К.
  • 11 тиждень
    • Л6. Графи: способи їх зберігання і обходи (в ширину і в глибину). Пошук циклів у графі. Алгоритми пошуку найкоротших шляхів та оптимальних маршрутів у графах [3, 83-120, 5]
    • ЛР11.  Алгоритм Дейкстри [1,3, 83-120, 5]
    • СРС. К.
  • 12 тиждень
    • ЛР12. Автомат  Мура [1,4, 90-96]
    • СРС. К.
  • 13 тиждень
    • Л7. Кінцевий автомат. Взаємне перетворення автоматів. Перетворення автомата Мура в Мілі. Реакція автомата на вхідне слово. Визначення реакції на вхідне слово для автомата Мілі. Визначення реакції на вхідне слово для автомата Мура [4, 90-96]
    • ЛР13. Автомат  Міля [1,4, 90-96]
    • СРС. К.
  • 14 тиждень
    • ЛР14. Перетворення автомата Мура в Мілі [1,4, 90-96]
    • СРС. К.
  • 15 тиждень
    • Л8. Машини Тьюрінга. Принцип роботи машини Тьюринга. Табличне представлення роботи МТ.[1, c.41-54]
    • ЛР15. Розв'язання задачі машини Тюрінга.[1, c.41-54]
    • МКР2. СРС. К.

 

Індивідуальна робота

Виконується РГР. 

Мета РГР: систематизувати, розширити та закріпити теоретичні знання здобувачів вищої освіти з дисципліни «Теорія алгоритмів».  

  • 1–7 тижні Отримання завдання. Перетворення автоматів Мілі у Мура.
  • 8–14 тижні Розв’язання задачі машини Тюрінга. 
  • 15 тиждень Захист роботи.

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

Самостійна робота складає 74 години. Розподіл самостійної роботи за видами навчальних робіт:

  • підготовка до лекційних занять – 14 годин;
  • підготовка до лабораторних робіт та до виконання модульних контрольних завдань – разом 45 годин;
  • виконання РГР – 15 годин;

 

Процедура оцінювання

Система оцінювання рівня навчальних досягнень ґрунтується на принципах ЄКТС та є накопичувальною. Дисципліна поділяється на два семестрові модулі. Здобувачі протягом семестру готуються до лекційних та лабораторних робіт, виконують 2 модульні контрольні роботи.

Модульні контрольні роботи № 1 та № 2 виконуються у письмовій формі. Модульна робота складається з теоретичної частини (2 запитання) та практичної частини (1 задача). Відповідь на кожне теоретичне питання оцінюється максимум 10 балами. Правильне розв’язання задачі оцінюється в 5 балів.

Кожний модуль оцінюється у максимально можливі 50 балів.

Семестровий модуль № 1

  • ЛР1- ЛР4.  Оцінка за виконання –20 балів. Термін виконання – 1-8 тиждень.
  • РГР(ч.1). Оцінка за виконання – 10 балів. Термін надання – 8 тиждень.
  • МК1. Модульна контрольна робота – 20 балів (8 тиждень). Перескладання можливе протягом 9–11 тижнів за розкладом консультацій.

Семестровий модуль № 2

  • ЛР5- ЛР8.  Оцінка за виконання – 20 балів. Термін виконання – 9-15 тиждень.
  • РГР(ч.2). Оцінка за виконання – 10 балів. Термін надання – 14–15 тижні 
  • МК2. Модульна контрольна робота – 20 балів (15 тиждень). 

Максимальна оцінка за повний обсяг виконаних навчальних елементів дисципліни – 100 балів.

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

 

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

До екзамену допускаються здобувачі вищої освіти, які виконали всі види навчальних елементів навчальної дисципліни на не менш, ніж на 60 %.

Екзамен відбувається за всіма тематичними (змістовними) модулями дисципліни.

Складання/перескладання екзаменів – за встановленим деканатом розкладом.

 

Політика освітнього процесу

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

Відсутність здобувача на лабораторній роботі відповідає оцінці «0».

Виконаний не свій варіант завдання здобувачем не оцінюється.

Робота, яка виконана після встановлених викладачем термінів, не приймається.

Під час лекції здійснювати телефонні дзвінки забороняється.

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

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

  1. Методичні вказівки до виконання лабораторних робіт студентів з дисципліни “Теорія алгоритмів”, для студентів II курсу денної та заочної форм навчання спеціальності - 126 Інформаційні системи та технології / Укладачі: І.М.Шпінарева, М.Д. Рудніченко, Н.О. Шибаєва.– Одеса: ОНПУ, 2020. – 57 с. (Електронна версія), Реєстраційний номер № MВ11558 -9.10.2020 
  2. Методичні вказівки до виконання РГР студентів з дисципліни “Теорія алгоритмів”, для студентів II курсу денної та заочної форм навчання спеціальності - 126 Інформаційні системи та технології / Укладачі: Н.О. Шибаєва, І.М.Шпінарева – Одеса: ОНПУ, 2020. – 33 с. (Електронна версія), Реєстраційний номер № MВ11557 -9.10.2020 
  3. Левітін В.Алгоритми Введення в розробку і аналіз. М.: "Вільямс", 2006. - 576 с. 
  4. Robert Lafore Data Structures and Algorithms in Java 2nd Edition. 2nd ed. - SPb .: Peter , 2013. - 704 p.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms Third Edition The MIT Press Cambridge, Massachusetts London, England, 2009 -1296р.