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

Тип: Нормативний

Відділення: викладачі фундаментальних дисциплін

Навчальний план

СеместрКредитиЗвітність
4Іспит

Лекції

СеместрК-сть годинЛекторГрупа(и)
434доцент Вельгош С. Р.КНК-21

Лабораторні

СеместрК-сть годинГрупаВикладач(і)
434КНК-21доцент Вельгош С. Р.

Практичні

СеместрК-сть годинГрупаВикладач(і)
1

Опис курсу

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

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

знати:
• різновиди, властивості та композиції алгоритмів;
• поняття про алгоритмічні системи;
• нормативні алгоритми Маркова;
• поняття машини Тюрінга;
• поняття машини Поста;
• поняття РАМ-машини;
• поняття про поліноміальні алгоритми та важко-розв’язні задачі.
вміти:
• оцінювати ефективність алгоритму;
• виконувати зведення довільних алгоритмів до числових функцій;
• використовувати рекурсивні функції;
• застосовувати теорію NP-повноти до аналізу задач;
• реалізовувати метод “поділяй і володарюй”, евристичні та жадібні алгоритми, метод гілок та меж;
• використовувати методи динамічного програмування.

Рекомендована література

Базова

1. Клакович Л., Левицькі С., Костів О. Теорія алгоритмів. Навч. посібник. – Львів, 2008.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – Москва, 2000.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – Москва, 1979.
4. Кнут В. Искусство программирования. – Т. 1. Основные алгоритмы: 3-е изд. – Москва, 2000.
5. Кнут В. Искусство программирования. – Т. 3. Сортировка и поиск: 2-е изд. – Москва, 2000.
6. Нікольский Ю., Пасічник В., Щербина Ю. Дискретна математика. – Львів, 2006.
7. Глибовець М. Основи комп’ютерних алгоритмів. – Київ, 2003.
8. Макконнел Дж. Основы современных алгоритмов: 2-е доп. изд. – Москва, 2006.
9. Кожевникова Г. Теория алгоритмов. – Львов, 1986.
10. Кормен Т., Лейзер Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – Москва, 2005

Допоміжна

1. Липский В. Комбинаторика для программистов. – Москва, 1988.
2. Новиков Ф. Дискретная математика для программистов. – Санкт-Петербург, 2000.
3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – Москва,1982.
4. Мальцев А. Алгоритмы и рекурсивные функции. – Москва, 1986.
5. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – Москва, 1980.
6. Трахтенброт Б. Алгоритмы и вычислительные автоматы. – Москва, 1974.
7. Успенский В., Семенов А. Теория алгоритмов: основные открытия и приложения. – Москва, 1987.
8. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – Москва, 1981.