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

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

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

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

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

Лекції

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

Лабораторні

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

Практичні

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

Опис курсу

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

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

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

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

Базова

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

Допоміжна

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