Алгоритми та моделі обчислень
Спеціальність: Комп'ютерна інженерія
Код дисципліни: 6.123.00.O.128
Кількість кредитів: 6.00
Кафедра: Спеціалізовані комп'ютерні системи
Семестр: 4 семестр
Форма навчання: денна
Алгоритми та моделі обчислень
Спеціальність: Комп'ютерна інженерія
Код дисципліни: 6.123.00.O.127
Кількість кредитів: 6.00
Кафедра: Електронні обчислювальні машини
Лектор: ст. викладач Козак Назар Богданович
Семестр: 4 семестр
Форма навчання: денна
Результати навчання: Теоретична підготовка:
1) знання основних понять теорії алгоритмів;
2) знання принципів роботи машини Поста;
3) знання принципів роботи машини Тюрінга;
4) знання теорії складності обчислень.
Практичні навички:
1) вміти розробляти алгоритми;
2) вміти розробляти рекурсивні алгоритми;
3) вміти програмувати алгоритми;
4) виконувати аналіз алгоритмів;
5) виконувати моделювання машин Тюрінга.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Дискретна математика
Програмування частина 1 (Основи алгоритмізації та програмування)
Програмування, частина 2 (Об’єктно орієнтоване програмування)
Короткий зміст навчальної програми: Вступ до теорії алгоритмів.
Машина Поста.
Машина Тюрінга.
Вступ до аналізу алгоритмів.
Трудомісткість алгоритмів та їх часові оцінки.
Теорія складності обчислень і класи складності задач.
Приклад повного аналізу алгоритму вирішення задачі про суму.
Рекурсивні функції та алгоритми.
Рекурсивні алгоритми і методи їх аналізу.
Прямий аналіз рекурсивного дерева викликів.
Методи та критерії оцінювання: Виконання і захист лабораторних та практичних робіт: 30.
Екзаменаційний контроль: 70 (письмова компонента: 60, усна компонента: 10).
Рекомендована література: 1. Ахо, А. Структуры данных и алгоритмы / Ахо А., Хопкрофт Дж., Ульман Дж. – М.: Издательский дом «Вильямс», 2001. –384 с.
2. Вирт Н. Алгоритмы и структуры данных / Н. Вирт – 2-ое изд., испр. – СПб.: Невский диалект, 2001. – 352 с.
3. Карпов, Ю.Г. Теория автоматов / Ю.Г. Карпов – СПб.: Питер, 2002. – 224 с.
4. Кнут, Д. Искусство программирования. Тома 1, 2, 3. 3-е изд. / Д. Кнут. Уч. пос. – М.: Изд. дом "Вильямс", 2001. – 385 с.
5. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест – М.: МЦНМО, 2001. – 960 с.
6. Макконнел Дж. Анализ алгоритмов. Вводный курс / Макконнел Дж. – М.: Техносфера, 2002. –304 с.
7. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков – СПб.: Питер, 2001. – 304 с.
8. Романовский, И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике / И.В. Романовский – Издание 2-ое, исправленное. – СПб.; Невский диалект, 2000. – 240 с.
9. Чмора, А.Л. Современная прикладная криптография / А.Л. Чмора – М.: Гелиос АРВ, 2001.