МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Ковельський промислово – економічний коледж Луцького НТУ

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

ПРОГРАМА

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

підготовки молодшого спеціаліста

галузь знань 12 "Комп’ютерні науки"

спеціальності 122 "Інформаційні технології та інформаційні технології"

Ковель 2018 рік

РОЗРОБЛЕНО: Ковельський промислово – економічний коледж Луцького НТУ

РОЗРОБНИКИ ПРОГРАМИ: Хорунжий Олександр Володимирович, викладач

Обговорено та рекомендовано до затвердження на засіданні випускної методичної комісії зі спеціальності «Обслуговування програмних систем та комплексів»

ВСТУП

Програма вивчення нормативно – навчальної дисципліни «Теорія алгоритмів» складена відповідно до освітньо-професійної програми підготовки – молодшого спеціаліста спеціальності 122 "Комп’ютерні науки"

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

аналізу

Міждисциплінарні зв’язки: "Вступ до спеціальності", "Алгоритмізація та програмування", "Дискретна математика", "Об'єктно-орієнтоване програмування", "Технологія створення програмних продуктів", "Технології захисту інформації".

Програма навчальної дисципліни складається з таких змістових розділів:

1. Алгоритми та їх властивості.

2. Прикладна теорія алгоритмів.

3. Теорія обчислень і математична логіка.

1. Мета та завдання навчальної дисципліни

Мета вивчення дисципліни “Теорія алгоритмів” — опанувати фундаментальним для інформатики поняттям алгоритму, сформувати практичні навички розробки алгоритмів розв’язання прикладних задач та їх програмування. Вивчення цієї дисципліни дасть змогу студентам зрозуміти та засвоїти основні принципи розробки алгоритмів і програм, а також стане підґрунтям для самостійної практичної роботи в галузі інформаційних систем та вивчення нового курсу «Математичні моделі та методи планування прийняття рішень».

Задача вивчення дисципліни полягає в тому, щоб навчити студента розв'язувати наближеними методами за допомогою комп'ютера математичні задачі, що виникають в інженерній практиці в процесі моделювання та проектування.

Згідно з вимогами освітньо – професійної програми студенти повинні:

знати:

· алгоритми та їх властивості, прикладну теорію алгоритмів, теорію множин та обчислень і математичну логіку;

· алгоритмічні проблеми, що виникають при розв’язанні стандартних та нестандартних задач і засоби їх подолання

вміти:

· програмувати алгоритми розв’язання задач перелічених типів

· оцінювати точність одержаних результатів та використовувати математичні моделі та методи

На вивчення навчальної дисципліни відводиться 108 години / 3 кредитів ЕСТS

Тематичний план

Найменування блоків	Кількість годин
	всього	лекції	практичні	Самостійна робота
1	2	3	4	5
Розділ 1. Теорія обчислень і математична логіка.
Тема № 1. Універсальні обчислювальні машини		12	12	16
Всього по розділу		12	12	16
Розділ 2. Алгоритми та їх властивості.
Тема № 1.Алгоритми їх класифікація, типи та можливості		8	8	8
Всього по розділу		8	8	8
Розділ 3. Прикладна теорія алгоритмів.
Тема № 2. Основні етапи розробки алгоритмів		8	8	10
Тема № 3. Методи розробки алгоритмів		4	6	4
Всього по розділу		12	14	4

2. Інформаційний обсяг навчальної дисципліни

Розділ 1. Теорія обчислень і математична логіка

Універсальні обчислювальні моделі: машини Тьюрінга і Поста, алгоритми Маркова, машини з вільним доступом до пам’яті, рекурсивні функції. Формальне визначення алгоритму, тезис Черча. Масові алгоритмічні проблеми, які неможливо розв’язати.

Елементи математичної логіки, обчислення висловлень, поняття логічного висновку, недетерміновані алгоритми. Теорема про повноту для обчислення висловлювань. Обчислення предикатів, формальна арифметика. Теорема Геделя про неповноту арифметики.

Література [3; 5; 6]

Розділ 2. Алгоритми та їх властивості

Неформальне поняття і визначення алгоритму. Алгоритм пошуку мінімуму в масиві як приклад алгоритму. Блок-схема алгоритму. Основні властивості алгоритмів: функціональність, результативність, визначеність, елементарність. Алгоритмічні мови високого рівня. Оператор присвоювання. Умовний оператор. Оператор умовного та безумовного циклу. Виклик процедури. Чисельні алгоритми. Алгоритм Евкліда пошуку найбільшого спільного дільника двох чисел. Доведення правильності та результативності алгоритму Евкліда. Алгоритм помнож на три і додай одиницю” і проблемні (не результативні) алгоритми. Алгоритм пошуку шляху в лабіринті (нитка Аріадни) як приклад алгоритму на графі. Операції зі стеком.

Література [1; 2; 4; 6]

Розділ 3. Прикладна теорія алгоритмів

Основні етапи розробки алгоритму: постановка завдання і побудова моделі, розробка і реалізація алгоритму, доведення правильності та тестування алгоритму, аналіз складності алгоритму, підготовка документації. Основні інформаційні структури даних: масиви, списки, черги, стеки. Зображення дерев, графів і множин. Методи розробки алгоритмів: структурне програмування, рекурсія, обходи дерев, “поділяй і пануй”, балансування, динамічне програмування, програмування з відходом назад, метод “гілок і меж”, евристичні та наближені алгоритми. Проходження повного циклу розробки на прикладі алгоритму пошуку кістякового дерева мінімальної ваги. Алгоритми комп’ютерної математики. Алгоритми додавання і множення чисел. Аналіз та обчислення арифметичних і логічних виразів. Алгоритми на графах, пошук у глибину, пошук найкоротшого шляху. Сортування і пошук даних. Ігрові та комбінаторні алгоритми. Чисельні методи, обчислення дійсних констант і функцій. Ймовірнісні алгоритми. Алгоритми ідентифікації текстових рядків і скінченні автомати.

Література [1; 2; 4; 6]

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

Основна література:

1. Матвієнко М.П. Теорія алгоритмів: Ліра-К, 2018. – 340 с.

2. Калужнін Л. А., Королюк В. С. Алгоритми і математичні машини.

— К.: Вища шк., 1964.

3. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической

логике и теории алгоритмов. — М.: Наука, 1975.

4. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів: Навч. посібник.- К.:  Видавничий поліграфічний центр “Київський університет”, 2003.-163 с.

5. Хромой Я. В. Математична логіка. — К.: Вища шк., 1983.

6. Хромой Я. В. Збірник задач і вправ з математичної логіки. — К.:

Вища шк., 1978.

Додаткова:

7. Алферова. З.В. Теория алгоритмов.- М.: Статистика, 1973.- 164 с.

8. Вирт. Н Алгоритмы + структуры данных = программы.- М.: Мир, 1985.-406c.

9. Грин Д., Кнут Д. Математические методы анализа алгоритмов.- М.: Мир, 1987.- 120 с.

10. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование. — 3-е изд., перераб. и доп. — К.: Наук. думка, 1989. 14

11. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.

— М.: Мир, 1981.

12. Грин Д., Кнут Д. Математические методы анализа алгоритмов.- М.: Мир, 1987.- 120 с.

13. Мендельсон Э. Введение в математическую логику. — М.: Мир, 1976.

14. Минский М. Вычисления и автоматы. — М.: Мир, 1971.

15. Трахтенброт Б. А. Алгоритмы и вычислительные машины. — М.:

Сов. радио, 1974.

16. Тьюринг А. Может ли машина мыслить? — М.: Физматгиз, 1960.

17. Шкільняк С.С. Математична логіка: приклади і задачі. – Київ: ВПЦ "Київський університет", 2002. – 56 с.

4. Форма підсумкового контролю успішності навчання екзамен