Методи побудови і аналізу алгоритмів.

 

Тема 6. Сортування даних. Сортування вставками, вибором, обмінами, квадратичним вибором. Швидке і розподільне сортування. Сортування злиттям. (6 год.)

Тема 7. Обчислювальна геометрія. Властивості відрізків. Побудова опуклої оболонки. Пошук пари найближчих точок. (6 год.)

 

Тема 8. Методи побудови і аналізу алгоритмів. Динамічне програмування. Найбільша спільна послідовність. Оптимальна тріангуляція многокутника. (6 год.)

 

Тема 9. Методи побудови і аналізу алгоритмів. Жадні алгоритми. Амортизаційний аналіз. Коди Хаффмена. Задача про розклад. Метод передоплати. Динамічні таблиці. (6 год.)

Структура навчальної дисципліни

Назва змістових модулів і тем	Кількість годин
Денна форма
Усього	у тому числі
л	п	лаб	інд	ср
Модуль 1
Змістовий модуль 1. Вивчення основ алгоритмічного мислення. Поняття алгоритму, блок-схеми, принципів побудови алгоритмів та програм.
Тема1. Вступ. Предмет курсу. Поняття алгоритму. Побудова, аналіз, реалізація алгоритму. Псевдокод. Блок-схема. Запис основних операторів у вигляді блок-схем і псевдокодом. Заповнення таблиці прокрутки алгоритму.
Тема2.Лінійні алгоритми. Галужені алгоритми. Циклічні та ітераційні алгоритми. Рекурентні співвідношення. Рекурсія.
Тема3.Робота з поліномами. Реалізація дій алгебри поліномів. Схема Горнера. Суперпозиція поліномів.
Разом –за модуль 1
Змістовий модуль 2. Розгляд основ побудови і роботи з базовими структурами даних, що використовуються в обчислювальних процесах.
Тема 5.Вектори і матриці. Введення, зберігання, елементи пошуку. Дії матричної алгебри. Порівняння та переміщення елементів матриці. Алгоритм Штрассена. Порівняння та переміщення елементів матриці. Способи запакування розріджених матриць.
Тема 6.Робота з стуктурами даних. Зв'язні списки. Стеки і черги. Дерева. Хеш-таблиці.
Разом –за модуль 2
Змістовий модуль 3. Методи побудови і аналізу алгоритмів.
Тема 7.Сортування даних. Сортування вставками, вибором, обмінами, квадратичним вибором. Швидке і розподільне сортування. Сортування злиттям.
Тема 8.Обчислювальна геометрія. Властивості відрізків. Побудова опуклої оболонки. Пошук пари найближчих точок
Тема 9.Динамічне програмування. Найбільша спільна послідовність. Оптимальна тріангуляція многокутника.
Тема 10.Методи побудови і аналізу алгоритмів. Жадні алгоритми. Амортизаційний аналіз. Коди Хаффмена. Задача про розклад. Метод передоплати. Динамічні таблиці.
Разом –за модуль 3
Усього годин

Теми лабораторних занять

	Лабораторні роботи
Тижні	Номер, назва і зміст теми	Год.
1.	Побудова, аналіз, реалізація алгоритму.
2.	Заповнення таблиці прокрутки алгоритму.
3.	Реалізація ітераційних алгоритмів.
4.	Використання рекурсії на прикладах практичних задач
5.	Реалізація дій алгебри поліномів
	Схема Горнера. Суперпозиція поліномів
6.	Пошук та переміщення елементів матриці
7.	Алгоритм Штрассена. Захист 1 завдання
8.	Організація зв’язних списків, стеків і черг. Алгоритми з використання цих структур даних
9.	Організація дерев. Основні дії з бінарними деревами. Захист 2 завдання
10.	Сортування вставками, вибором, обмінами
11.	Швидке сортування, сортування злиттям, пірамідальне сортування
12.	Властивості відрізків та точок, їх спільне розміщення.
13.	Побудова опуклих оболонок.
14.	Найбільша спільна послідовність.
15.	Оптимальна тріангуляція многокутника.
16.	Задача про розклад. Метод передоплати.
17.	Динамічні таблиці. Захист 3 завдання.

Самостійна робота

	Самостійна робота
	Номер, назва і зміст теми	Год.
1.	Побудова, аналіз, реалізація алгоритму.
2.	Заповнення таблиці прокрутки алгоритму.
3.	Реалізація ітераційних алгоритмів.
4.	Використання рекурсії на прикладах практичних задач
5.	Реалізація дій алгебри поліномів. Схема Горнера. Суперпозиція поліномів
6.	Пошук та переміщення елементів матриці
7.	Алгоритм Штрассена.
8.	Організація зв’язних списків, стеків і черг. Алгоритми з використання цих структур даних
9.	Організація дерев. Основні дії з бінарними деревами.
10.	Сортування вставками, вибором, обмінами
11.	Швидке сортування, сортування злиттям, пірамідальне сортування
12.	Властивості відрізків та точок, їх спільне розміщення.
13.	Побудова опуклих оболонок.
	Найбільша спільна послідовність.
	Оптимальна тріангуляція многокутника.
	Задача про розклад. Метод передоплати.
	Динамічні таблиці.

7. Розподіл балів, що присвоюється студентам

Поточне тестування та самостійна робота	зал	Сума
Змістовний модуль 1	Змістовний модуль 2	Змістовний модуль 3

Методичне забезпечення

Тексти лекцій та нижчеперелічена література наявна на кафедрі в друкованому чи електронному форматах.

Підручник, підготований викладачами кафедри програмування.

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

Базова

1. Костів О.В., Ярошко С.А. Методи розробки алгоритмів: Тексти лекцій. - Львів: Видавничий центр ЛНУ імені Івана Франка, 2002.- 101 с.

2. Костів О. Структури даних. Частина 1: Тексти лекцій. - Львів: Видавничий центр ЛНУ імені Івана Франка, 2000. - 56 с.

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

4. Кнут Д. Искусство программирования для ЗВМ. Т. 1: Основные алгоритми. - М.: Издательский дом «Вильямс», 2000. - с.

5. Кнут Д. Искусство программирования для ЗВМ. Т. 3: Сортировка и поиск. - М.: Издательский дом «Вильямс», 2000. - 822 с.

Допоміжна

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структури данных и алгоритми. - М.: Издательский дом «Вильямс», 2003. - 384 с.

2. Кормен Т., Лейзерсон Ч., Pueecm Р. Алгоритми: построение и анализ. - М.: МЦНМО, 2001. - 960 с.

1. Інформаційні ресурси

1. Матеріали сайту http://intuit.ru.