Алгоритмізація та програмування, частина 2
Спеціальність: Комп'ютерні науки (Проектування і програмування інтелектуальних систем та пристроїв)
Код дисципліни: 6.122.12.O.010
Кількість кредитів: 7.00
Кафедра: Системи автоматизованого проектування
Лектор: д.т.н., професор каф. САП Андрійчук Михайло Іванович
к.т.н., ст.викл. каф. САП Оборська Оксана Володимирівна
Семестр: 2 семестр
Форма навчання: денна
Результати навчання: У результаті вивчення дисципліни, студент повинен знати:
1. поняття алгоритму та його властивості, загальні схеми побудови алгоритмічних систем;
2. основні способи композиції нормальних алгоритмів;
3. основні кількісні характеристики (сигнальні функції) алгоритмів;
4. означення алгоритмічної та обчислювальної складності масової проблеми;
5. поняття і приклад NP-повної проблеми;
6. принципи функціонування периферійних пристроїв.
Вміти:
1. використовувати базові структури даних;
2. використовувати дерева пошуку;
3. будувати нормальні алгоритми, композиції алгоритмів;
4. будувати програми для машин Поста і Тьюрінга;
5. будувати алгоритми сортування;
6. будувати алгоритми Флойда, Дейкстри, Пріма, Краскала;
7. проводити кластеризацію образів за допомогою алгоритмів розпізнавання;
8. будувати алгоритми пошуку.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: пререквізити:
1. Алгоритмізація та програмування,
частина 1.
2. Основи програмування, частина 1.
3. Інноваційні інформаційні технології.
кореквізити:
1. Об’єктно-орієнтоване програмування.
2. Комп’ютерна графіка.
3. Операційні системи.
prerequisites:
Короткий зміст навчальної програми: Тема 1. Основні поняття теорії алгоритмів.
Поняття алгоритму та його властивості. Приклади алгоритмів. Необхідність формалізації поняття алгоритму.
Алгоритмічна система (модель обчислень), загальна схема її побудови. Граф-схеми і блок-схеми алгоритмів. Алфавітні алгоритми. Нормальні алгоритми Маркова. Приклади побудови нормальних алгоритмів.
Принцип нормалізації. Основні способи композиції нормальних алгоритмів. Поняття універсального нормального алгоритму. Теорема про універсальний нормальний алгоритм. Алгоритмічно нерозв’язні проблеми. Обчислювані функції. Елементарні арифметичні функції.
Примітивно рекурсивні функції, їх приклади.
Оператор мінімізації. Частково рекурсивні функції. Теза Черча. Машини Поста і Тюрінга. Структура і функціонування машин Поста і Тюрінга. Поняття команди, програми і конфігурації. Приклади побудови програм для машини Тюрінга. Універсальна машина Тюрінга. Теза Тюрінга. Проблема зупинки та її алгоритмічна нерозв’язність. Зв’язок рекурсивних функцій з машинами Тюрінга.
Тема 2. Аналіз ефективності і складності алгоритмів.
Використання процесора, пам’яті, дискового простору, мережі. Поняття часової складності. Сумування ряду Фібоначчі двома типами алгоритмів. Порівняння складності. Обчислення практичної складності алгоритмів. Оптимістичний, песимістичний та середні випадки. Нотація великого О. Асимптотична складність алгоритмів. Поліноміальні алгоритми vs. експоненційні алгоритми.
Тема 3. Елементарні обчислювальні структури. Бінарні дерева.
Черги, стеки, деки. Зв’язаний розподіл. Бінарні дерева. Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 4. Бінарні дерева пошуку. Збалансовані бінарні дерева.
Бінарні дерева пошуку. Типи обходу дерев. Збалансовані бінарні дерева. 2-3 дерева. Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 5. Червоно-чорні дерева.
Правила побудови червоно-чорних дерев. Обхід дерев.
Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 6. Хеш таблиці.
Ініціалізація. Вставляння елемента. Пошук. Видалення. Обчислення хеш функцій. Вимоги до хеш функцій. Колізії. Методи лінійного зондування, подвійного хешування, зчеплення.
Тема 7. Алгоритми сортування.
Стійке і нестійке сортування. Бульбашкове сортування. Сортування вставками. Сортування вибором. Сортування Шелла. Сортування злиттям. Пірамідальне сортування. Швидке сортування.
Тема 8. Графи і алгоритми на графах.
Представлення графів. Досяжність у графах, знаходження найкоротших шляхів.
Тема 9. Жадібні алгоритми на графах.
Знаходження найкоротших шляхів. Алгоритми Флойда, Дейкстри, Прима, Краскала. Обхід графів.
Тема 10. Жадібні алгоритми. Алгоритм Хафмана.
Тема 11. Алгоритми класу поділяй і владарюй.
Алгоритм сортування Mergesort Quicksort.
Тема 12. Алгоритми класу поділяй і владарюй.
Множення чисел. Рекурентні співвідношення. Множення матриць.
Тема 13. Алгоритми пошуку.
Алгоритм грубої сили, алгоритми Кнута-Морріса-Пратта,
Боєра-Мура, Рабіна-Карпа
Тема 14. Алгоритми штучного інтелекту.
Алгоритми розпізнавання образів. Алгоритм порогової величини. Алгоритм К-внутрішніх групових середніх. Максимінний алгоритм. Альфа-бета алгоритм.
Методи та критерії оцінювання: лабораторні роботи - 40 балів, розрахункова робота- 8 балів.
екзамен-52 бали.
Порядок та критерії виставляння балів та оцінок: 100-88 балів - атестований з оцінкою «відмінно» - Високий рівень: здобувач освіти демонструє поглиблене володіння поняттєвим та категорійним апаратом навчальної дисципліни, системні знання, вміння і навички їх практичного застосування. Освоєні знання, вміння і навички забезпечують можливість самостійного формулювання цілей та організації навчальної діяльності, пошуку та знаходження рішень у нестандартних, нетипових навчальних і професійних ситуаціях. Здобувач освіти демонструє здатність робити узагальнення на основі критичного аналізу фактичного матеріалу, ідей, теорій і концепцій, формулювати на їх основі висновки. Його діяльності ґрунтується на зацікавленості та мотивації до саморозвитку, неперервного професійного розвитку, самостійної науково-дослідної діяльності, що реалізується за підтримки та під керівництвом викладача. 87-71 балів - атестований з оцінкою «добре» - Достатній рівень: передбачає володіння поняттєвим та категорійним апаратом навчальної дисципліни на підвищеному рівні, усвідомлене використання знань, умінь і навичок з метою розкриття суті питання. Володіння частково-структурованим комплексом знань забезпечує можливість їх застосування у знайомих ситуаціях освітнього та професійного характеру. Усвідомлюючи специфіку задач та навчальних ситуацій, здобувач освіти демонструє здатність здійснювати пошук та вибір їх розв’язання за поданим зразком, аргументувати застосування певного способу розв’язання задачі. Його діяльності ґрунтується на зацікавленості та мотивації до саморозвитку, неперервного професійного розвитку. 70-50 балів - атестований з оцінкою «задовільно» - Задовільний рівень: окреслює володіння поняттєвим та категорійним апаратом навчальної дисципліни на середньому рівні, часткове усвідомлення навчальних і професійних задач, завдань і ситуацій, знання про способи розв’язання типових задач і завдань. Здобувач освіти демонструє середній рівень умінь і навичок застосування знань на практиці, а розв’язання задач потребує допомоги, опори на зразок. В основу навчальної діяльності покладено ситуативність та евристичність, домінування мотивів обов’язку, неусвідомлене застосування можливостей для саморозвитку. 49-00 балів - атестований з оцінкою «незадовільно» - Незадовільний рівень: свідчить про елементарне володіння поняттєвим та категорійним апаратом навчальної дисципліни, загальне уявлення про зміст навчального матеріалу, часткове використання знань, умінь і навичок. В основу навчальної діяльності покладено ситуативно-прагматичний інтерес.
Рекомендована література: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009.
2. Donald E. Knuth. The art of computer programming. Vol. 3: Sorting and Searching. Addison-Wesley, Upper Saddle River, NJ, 1998.
3. Algorithms, 4th Edition by Robert Sedgewick, Kevin Wayne
4. Narasimha Karumanchi. Data Structures and Algorithms Made Easyю 2016 CareerMonk Publications and othersю
5. The Algorithm Design Manual, 2nd Edition by Steven S Skiena
6. Яворський Б.І. Теорія алгоритмів/Конспект лекцій.— Тернопіль: ТДТУ імені Івана Пулюя, 2000.— 36 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).