Geum.ru

Робоча навчальна програма кредитного модуля

Вид материалаДокументы

Содержание


денної форми навчання
Загальні відомості
Ii. розподіл навчального часу
Iii. мета і завдання дисципліни
Завдання курсу
Iv. тематичний план
Iv. 2. лекції
Iv.3. практичні заняття
Модульна контрольна робота 1
Iv.6. індивідуальні завдання
Iv.7. контрольні роботи
V. методичні вказівки
Vi. навчально-методичні матеріали
Подобный материал:
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ "КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

ТЕПЛОЕНЕРГЕТИЧНИЙ ФАКУЛЬТЕТ

Кафедра автоматизації проектування енергетичних процесів та систем




“Затверджую”

Декан теплоенергетичного факультету


__________ Є.М.Письменний

(підпис) (ініціали, прізвище)

«____»_______________ 2011р.



__________ Є.М.Письменний

(підпис) (ініціали, прізвище)

«____»_______________ 2012р.




РОБОЧА НАВЧАЛЬНА ПРОГРАМА


КРЕДИТНОГО МОДУЛЯ

“Теорія алгоритмів”, код НФ-04



для напряму підготовки 6.050101 комп’ютерні науки”

програма професійного спрямування “Інформаційні технології проектування ”

«Комп'ютерний еколого-економічний моніторинг»

денної форми навчання




Програму рекомендовано


кафедрою АПЕПС

Протокол № ___

від __ .__.2011 р.

Завідувач кафедри АПЕПС


_________С.О. Лук’яненко


Київ – 2011


  1. ЗАГАЛЬНІ ВІДОМОСТІ

Дисципліна “ Теорія алгоритмів ” - це одна з важливих складових дисциплін підготовки спеціалістів напряму «Комп'ютерні науки» тому, що знання та програмна реалізація алгоритмів є невід'ємною частиною діяльності інженера по створенню та застосуванню нових інформаційних технологій та програмуванню перспективних інноваційних програмних продуктів.

Зазначена дисципліна включена до циклу «Професійної та практичної підготовки».

У структурно-логічній схемі навчання зазначена дисципліна розміщена тоді, коли студенти вже прослухали «Дискретна математика», «Теорія ймовірності, ймовірності процедури і математична статистика», «Алгоритмізація та програмування», «Архітектура комп’ютера», що достатньо для виконання лабораторних робіт з даної дисципліни. З іншого боку, викладений матеріал може бути використаний при вивченні дисциплін «Моделювання складних процесів та систем», «Основи системного аналізу комп'ютерних інформаційних систем », які подаються у наступних семестрах.

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


II. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ


Семестр/код

кредитного

модуля
Всього годин



Розподіл годин за видами занять
Кількість МКР
Вид індивідуального завдання
Семестрова атестація

Лекції
Практичні заняття
Семінарські заняття
Лабораторні роботи
Комп 'ютерний практикум
СРС

Всього
Утому числі

на виконання

індивідуального

завдання


3/НФ-04

144

36

-

-

-

18

90

-

1

-

Іспит



III. МЕТА І ЗАВДАННЯ ДИСЦИПЛІНИ


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

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

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

графіки, розпізнавання образів тощо.


В результаті вивчення дисципліни студент повинен


ЗНАТИ:
  • Алгоритми та їх властивості, прикладну теорію алгоритмів, теорію множин та обчислень і математичну логіку;
  • Алгоритмічні проблеми, що виникають при розв’язанні стандартних та нестандартних задач і засоби їх подолання


ВМІТИ:
  • програмувати алгоритми розв’язання задач перелічених типів
  • оцінювати точність одержаних результатів та використовувати математичні моделі та методи


IV. ТЕМАТИЧНИЙ ПЛАН

IV.I. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ ЗА ТЕМАМИ

Найменування розділів, тем
Розподіл за семестрами та видами занять

Всього
Лекції
Практ. зан. (контр. раб.)
Комп’ютерний практикум
СРС

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



6
20

Тема 1.1. Алгоритми їх класифікація, типи та можливості

24
10



2
12

Тема 1.2. Алгоритми та алгоритмічні мови
16
4



4
8

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



6
20

Тема 2.1. Основні етапи розробки алгоритмів
30
12



4

14

Тема 2.2. Методи розробки алгоритмів
12
4



2
6

Контрольна робота з розділів 1,2
2






1
1

Розділ 3.

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



6
13

Тема 3.1. Універсальні обчислювальні машини
13
4



2
7

Тема 3.2. Основи мат логіки
12
2



4
6

Підготовка до іспиту
36









36

Всього в 3 семестрі
144
36



18
90



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

Неформальне поняття і визначення алгоритму. Алгоритм пошуку мінімуму в масиві як приклад алгоритму. Блок_схема алгоритму. Основні властивості алгоритмів: функціональність,

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

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

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

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

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


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

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

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

арифметики.

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

IV. 2. ЛЕКЦІЇ


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

Тема 1.1. Алгоритми їх класифікація, типи та можливості

Л1. Неформальне поняття і визначення алгоритму.

(Завдання для самостійної роботи: Побудувати алгоритм єфективної співпраці «Викладач-Студент)

Л2. Алгоритм пошуку мінімуму в масиві як приклад алгоритму. Блок-схема

алгоритму.

(Завдання для самостійної роботи: Побудувати блок-схему алгоритму якості засвоєння учбового матеріалу)

ЛЗ. Основні властивості алгоритмів: функціональність, результативність, визначеність, елементарність тощо

(Завдання для самостійної роботи: Вивчити застосування основних властивостей алгоритмів до проектування евристичних алгоритмів)

Л4. Алгоритмічні мови високого рівня. Оператор присвоювання. Умовний оператор.

Оператор умовного та безумовного циклу. Виклик процедури.

(Завдання для самостійної роботи: Реалізувати алгоритми з переліченими операторами)

Л5. Чисельні алгоритми. Алгоритм Евкліда пошуку найбільшого спільного дільника двох чисел. Доведення правильності та результативності алгоритму Евкліда.

(Завдання для самостійної роботи: Реалізувати чисельний алгоритм за вибором)

Тема 1.2. Алгоритми та алгоритмічні мови

Л6. Алгоритм “помнож на три і додай одиницю” і проблемні (не результативні) алгоритми

(Завдання для самостійної роботи: Спроектувати наведений алгоритм)

Л7. Алгоритм пошуку шляху в лабіринті (нитка Аріадни) як приклад алгоритму на графі. Операції зі стеком.

(Завдання для самостійної роботи: Побудувати блок схему і графічну реалізацію наведеного алгоритму)

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


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

Тема 2.1. Основні етапи розробки алгоритмів

Л8. Основні етапи розробки алгоритму: постановка завдання і побудова моделі, розробка і реалізація алгоритму, доведення правильності та тестування алгоритму, аналіз складності алгоритму, підготовка документації.

(Завдання для самостійної роботи: Вивчити відповідні теореми та методику побудови розглянутих алгоритмів)

Л9. Основні інформаційні структури даних: масиви, списки, черги, стеки. Зображення дерев, графів і множин.

(Завдання для самостійної роботи: Спроектувати вивчені інформаційні структури у вигляді ієрархічних алгоритмів)

Л10. Методи розробки алгоритмів: структурне програмування, рекурсія, обходи дерев, “поділяй і пануй”, балансування, динамічне програмування, програмування з відходом назад, метод “гілок і меж”, евристичні та наближені алгоритми.

(Завдання для самостійної роботи: Побудувати модель розглянутих алгоритмів)

Л11. Проходження повного циклу розробки на прикладі алгоритму пошуку кістякового дерева мінімальної ваги.

(Завдання для самостійної роботи: Вивчити методологію реалізації вивченого алгоритму)

Л12. Проходження повного циклу розробки на прикладі алгоритму пошуку кістякового дерева мінімальної ваги.

(Завдання для самостійної роботи: Реалізувати зазначений алгоритм на алгоритмічній мові)

Л13. Алгоритми комп’ютерної математики. Алгоритми додавання і множення чисел. Аналіз та обчислення арифметичних і логічних виразів. Алгоритми на графах, пошук у глибину, пошук

найкоротшого шляху.

(Завдання для самостійної роботи: Спроектувати граф-схему алгоритмів комп»ютерної математики)

Тема 2.2. Методи розробки алгоритмів

Л14. Сортування і пошук даних. Ігрові та комбінаторні алгоритми. Чисельні методи, обчислення дійсних констант і функцій.

(Завдання для самостійної роботи: Вивчити технологію реалізації наведених алгоритмів)

Л15. . Ймовірнісні алгоритми. Алгоритми ідентифікації текстових рядків і скінченні автомати.

(Завдання для самостійної роботи: Реалізувати розглянуті алгоритми на алгоритмічній мові)

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


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

Тема 3.1. Універсальні обчислювальні машини

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

(Завдання для самостійної роботи: Побудувати гафічну реалізацію зазначених обчислювальних моделей)

Л17. Формальне визначення алгоритму, тезис Черча. Масові алгоритмічні проблеми, які неможливо розв’язати.

(Завдання для самостійної роботи: Вивчити галузі застосування наведених алгоритмів)

Тема 3.2. . Основи матлогіки

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

(Завдання для самостійної роботи: Реалізувати наведені алгоритми за допомогою генетичних алгоритмів)

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


IV.3. ПРАКТИЧНІ ЗАНЯТТЯ

Не передбачені навчальним планом.


IV.4. СЕМІНАРСЬКІ ЗАНЯТТЯ

Не передбачені навчальним планом.


IV.5. КОМП’ЮТЕРНИЙ ПРАКТИКУМ


Мета циклу комп’ютерних практикумів полягає в тому, щоб студенти отримали основні практичні навички розв’язування за допомогою комп’ютера різноманітних математичних задач.


№ роботи
Тема роботи
Кільк .год

1
Евристичні алгоритми
4

2
Генетичні алгоритми
2

3
Паралельні алгоритми
2

4
Фаззі- алгоритми
2

5
Акмеологічні алгоритми
4




Модульна контрольна робота 1
2

6
Алгоитми з працевлаштування
2

7
Кіберакмеологічні алгоритми
2

8








IV.6. ІНДИВІДУАЛЬНІ ЗАВДАННЯ

Навчальним планом не передбачено виконання у 3-му семестрі курсової роботи. Для самостійного вивчення пропонуються розділи «Алгоритми розмитих множин», «Обчислення генетичних алгоритмів». Для студентів, які планують перехід на магістерську підготовку, бажано ознайомитися з інноваційними алгоритмами та новими технологіями обробки комп»ютерних знань.


IV.7. КОНТРОЛЬНІ РОБОТИ


Для проведення контрольної роботи виділяється одна учбова година за рахунок комп’ютерних практикумів. У 3-му семестрі проводяться одна модульна контрольна робота - на 14-му учбовому тижні. Вона охоплює усі теми розділу 2 “ Прикладна теорія алгоритмів ” Мета роботи полягає у перевірці засвоєння матеріалу по вибору оптимального для поставленої задачі обчислювального методу та його програмній реалізації.

Теми контрольних робіт.

1. Поняття алгоритму та його властивості. Приклади алгоритмічних

процедур.

2. Граф-схеми і блок-схеми алгоритмів. Алфавітні алгоритми.

3. Нормальні алгоритми Маркова.

4. Побудова нормальних алгоритмів виконання основних арифметичних

дій (додавання, віднімання, множення, визначення НСД

та ін.) та алфавітних перетворень.

5. Основні способи композиції нормальних алгоритмів.

6. Поняття універсального нормального алгоритму. Схема побудови

універсального нормального алгоритму.

7. Приклад алгоритмічно нерозв’язної проблеми (проблема самозастосовності).

8. Елементарні арифметичні функції. Оператори суперпозиції і

примітивної рекурсії.

9. Поняття примітивно рекурсивної функції. Приклади.

10. Оператор мінімізації. Частково рекурсивні функції. Теза Черча.

11. Машина Тьюрінга: структура і принцип функціонування.

12. Поняття команди, програми і конфігурації.

13. Приклади побудови програм для машини Тьюрінга.

14. Універсальна машина Тьюрінга, схема побудови. Теза Тьюрінга.

15. Проблема зупинки та її алгоритмічна нерозв’язність.

16. Зв’язок рекурсивних функцій з машинами Тьюрінга.

17. Розмірність масової проблеми.

18. Побудова та оцінка алгоритмів. Оптимізація алгоритмів за різними

показниками.

19. Порівняльний аналіз алгоритмів.

20. Означення і властивості алгоритмічної складності. Теорема Колмогорова.

21. Міри складності обчислень (сигнальні функції).

22. Класифікація проблем: класи P і NP. Поняття і приклад NP-повної

проблеми.

23. Поліномна трансформованість проблем. Обґрунтування NP-повноти

різних проблем.

24. Легкорозв’язні дискретні задачі. Алгоритми пошуку в масиві.

25. Алгоритми сортування.

26. Алгоритми на графах (пошук шляхів, перевірка зв’язності, побудова

кістякових дерев, максимальні потоки та ін.).

27. Приклади важкорозв’язних проблем.

28. Підходи до розв’язання NP-повних задач.


V. МЕТОДИЧНІ ВКАЗІВКИ


Для кращого засвоєння матеріалу та раціонального розподілення об’єму учбової роботи рекомендується кожний тиждень 3 семестра проводити: лекції – 2 год/ тиждень, комп’ютерні практикуми – 2 год/на два тижня.

Підсумковий контроль з дісципліни проводиться у формі семестрової атестації та іспиту. Положення про рейтингову систему оцінювання з кредитного модуля наведено у Додатку 1.


VI. НАВЧАЛЬНО-МЕТОДИЧНІ МАТЕРІАЛИ


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


1. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Диалог – Сибирь, 2003. – 108 с.

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

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

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

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

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

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

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

Вища шк., 1978.


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

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

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


10. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование.

— 3-е изд., перераб. и доп. — К.: Наук. думка, 1989. 14

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

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

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

1976.

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

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

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

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

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


Робоча навчальна програма складена на основі навчальної програми дисципліни “ТЕОРІЯ АЛГОРИТМІВ”, що затверджена ________2011 р.


Розробник робочої навчальної програми – к.т.н., доцент кафедри АПЕПС Антонов В.М.


________________ / Антонов В.М./