Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



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

Скачати 174.37 Kb.

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




Скачати 174.37 Kb.
Сторінка2/2
Дата конвертації10.06.2017
Розмір174.37 Kb.
ТипПротокол
1   2

IV. 2. ЛЕКЦІЇ


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

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

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

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

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

алгоритму.

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

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

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

Л4. Алгоритмічні мови високого рівня.

Алгоритмі́чна мо́ва 1. формальна мова, призначена для записування алгоритмів. Використання алгоритмічної мови базується на можливості формального визначення правил конструювання алгоритмів. При формальному описанні алгортимів істотна роль належить вибору способу запису (кодування) оброблюваної інформації та задання алгоритмічних приписів - елементарних кроків алгоритму, із яких він конструюється. 2. Довга назва мови програмування АЛГОЛ
Оператор присвоювання. Умовний оператор.

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

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

Л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.

Комп'ютер (від англ. computer; лат. computator - обчислювач, лат. computatrum - рахувати, МФА: [kəmpjuː.Tə(ɹ)]) - програмно-керований пристрій для обробки інформації. Конструктивно це може бути механічний або немеханічний (електронний) пристрій, призначений для проведення обчислень, які можуть відбуватися дискретно або безперервно у часі.
Універсальні обчислювальні моделі: машини Тьюрінга і Поста, алгоритми Маркова, машини з вільним доступом до пам’яті, рекурсивні функції.

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

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

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

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

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

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

Література [3; 5; 6; 8]
IV.3. ПРАКТИЧНІ ЗАНЯТТЯ

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

Генети́чний алгори́тм (англ. genetic algorithm) - це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.
Навча́льний план - основний нормативний документ закладу освіти, за допомогою якого здійснюється організація навчального процесу. Навчальний план містить у собі розподіл залікових кредитів між дисциплінами, графік навчального процесу, а також план навчального процесу за семестрами, який визначає перелік та обсяг вивчення навчальних дисциплін, форми проведення навчальних занять та їх обсяг, форми проведення поточного та підсумкового контролю, державної атестації.


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. Оператор мінімізації. Частково рекурсивні функції. Теза Черча.

Арифметична функція - функція, визначена на множині натуральних чисел N } , що приймає значення в множині комплексних чисел C } .
Теза Черча - твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм.

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

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

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

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

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

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

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

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

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

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

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

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

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

проблеми.

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

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

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

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

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

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

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

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

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

NP-повна задача (англ. NP-complete) - в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. Зміст 1 Формальне визначення 1.

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 р.


Розробник робочої навчальної програми – к.т.н., доцент кафедри АПЕПС Антонов В.М.
Доце́нт (від лат. docere «навчати») - в Україні та інших країнах вчене звання викладачів вищих навчальних закладів, що виконують функцію університетських лекторів; вчене звання співробітників наукових установ; посада у вищих навчальних закладах.

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



1   2


Скачати 174.37 Kb.

  • Алгоритмічні мови
  • Розділ 3.
  • Нормальні алгоритми
  • Алгоритми сортування
  • NP-повних задач
  • Основна література