Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Форма № Н - 3.03
Затверджено наказом МОН України
від “___” ___________ 20 __ р. №___
Львівський національний університет імені Івана Франка
(назва вищого навчального закладу)
Кафедра (предметна, циклова комісія)прикладної математики
“ЗАТВЕРДЖУЮ”
Проректор (заступник директора)
з навчальної роботи
___________________________
“______”_______________20___ р.
Алгоритми обчислювальних процесів
(шифр і назва навчальної дисципліни)
напряму підготовки_______6.040301 -прикладна математика
(шифр і назва напряму підготовки)
для спеціальності (тей)_________7.04030101– прикладна математика
(шифр і назва спеціальності (тей)
спеціалізації_____________________________________________________________
(назва спеціалізації)
інституту, факультету, відділення_____прикладної математики та інформатики
(назва інституту, факультету, відділення)
|
Форма навчання |
Курс |
Семестр |
Загальний обсяг (год.) |
Всього аудит. (год.) |
у тому числі (год.): |
Самос- тійна робота (год.) |
Контрольні (модульні) роботи (шт.) |
Розрахунково-графічні роботи (шт) |
Курсові проекти (роботи), (шт.) |
Залік (сем.) |
Екзамен (сем.) |
||
|
Лекції |
Лабораторні |
Прак тичні |
|||||||||||
|
Денна |
1 |
2 |
108 |
54 |
36 |
18 |
54 |
3 |
1 |
||||
|
Вечірня |
|||||||||||||
|
Заочна |
|||||||||||||
|
Екстернат |
Робоча програма складена на основі: освітньо-професійної програми ГСВО ____________ напряму 6.040301 -прикладна математика, варіативної частини освітньо-професійної
(шифр, назва)
програми спеціальності 7.04030101– прикладна математика
(шифр, назва)
Робоча програма складена __ кандидатом фіз.-мат. наук, доц. Кухарським В.М.
(вчена ступінь, вчене звання, ім’я та ініціали автора (ів) прграми)
Робоча програма затверджена на засіданні кафедри (циклової, предметної комісії) ________________________________________________________________________
Протокол № ___ від. “____”________________20__ р.
Завідувач кафедрою (циклової, предметної комісії)________________________
_______________________ /__________________/
(підпис) (прізвище та ініціали)
“_____”___________________ 20___ р
Схвалено методичною комісією напряму (спеціальності)_______________________________________________________________
(шифр, назва)
Протокол № ___ від. “____”________________20___ р.
“_____”________________20__ р. Голова _______________/ _____________________/
(підпис) (прізвище та ініціали)
1.РІВЕНЬ СФОРМОВАНОСТІ ВМІНЬ ТА ЗНАНЬ
|
Шифр умінь та змістових модулів |
Зміст умінь, що забезпечується |
|
Змістовий модуль 1. |
Знати: теоретичні, методичні і алгоритмічні основи сучасних інформаційних технологій, загальні принципи побудови ефективних алгоритмів, сучасні методи дослідження та аналізу алгоритмів. Вміти: реалізовувати основні алгоритми засобами алгоритмічної мови. |
|
Тема 1. |
Знати: предмет курсу, основні поняття алгоритму, блок-схеми, псевдокоду. Вміти: записувати основні оператори у вигляді блок-схем і псевдокодом. |
|
Тема 2. |
Знати: класифікацію алгоритмів, рекурсію. Вміти: записувати рекурсію. |
|
Тема 3. |
Знати: дії алгебри поліномів. Вміти: реалізувати операції додавання, віднімання, множення, ділення і суперпозиції поліномів. |
|
Змістовий модуль 2. |
Знати: основні принципи роботи з матрицями і векторами, алгоритм Штрассена, дії матричної алгебри, поняття теорії графів, алгоритм Дейкстри, Краскалла. Вміти: застосовувати алгоритм Штрассена, запаковувати розріджені матриці, знаходити мінімальний шлях, висоту дерева, обходити графи. |
|
Тема 4. |
Знати: основні визначення теорії матриць, алгоритм Штрассена, дії матричної алгебри. Вміти: використовувати алгоритм Штрассена, запаковувати розріджені матриці. |
|
Тема 5. |
Знати: поняття теорії графів, алгоритм Дейкстри, Краскалла. Вміти: знаходити мінімальний шлях, висоту дерева, обходити графи. |
|
Змістовий модуль 3. |
Знати: класифікацію сортувань, основні алгоритми сортувань, формули обчислювальної геометрії, задачі динамічного програмування, умови перетину відрізків, коди Хаффмена. Вміти: сортувати масиви методами вставки, вибору, обміну квадратичним способом, злиттям, побудувати опуклу оболонку, знаходити найбільшу спільну послідовність, розв’язати задачу про розклад. |
|
Тема 6. |
Знати: класифікацію сортувань, основні алгоритми сортувань, обчислювальну складність простих методів сортування. Вміти: сортувати масиви методами вставки, вибору, обміну квадратичним способом, злиттям. |
|
Тема 7. |
Знати: основні формули обчислювальної геометрії, властивості відрізків Вміти: побудувати опуклу оболонку, пошук пари найближчих точок, обходити вершини опуклого багатокутника. |
|
Тема 8. |
Знати: основні задачі динамічного програмування. Вміти: будувати оптимальну тріангуляцію багатокутника, знаходити найбільшу спільну послідовність. |
|
Тема 9. |
Знати: основні приклади жадних алгоритмів, коди Хаффмена, методи передоплати. Вміти: кодувати, використовуючи коди Хаффмена, розв’язати задачу про розклад. |
|
Шифр змістового модуля |
Назва змістового модуля |
Кількість аудиторних годин |
|
Змістовий модуль 1. |
Вивчення основ алгоритмічного мислення. Поняття алгоритму, блок-схеми, принципів побудови алгоритмів та програм. |
10 |
|
Тема 1. |
Побудова, аналіз, реалізація алгоритму. |
2 |
|
Тема 2. |
Заповнення таблиці прокрутки алгоритму. |
2 |
|
Тема 3. |
Реалізація ітераційних алгоритмів. |
2 |
|
Тема 4. |
Використання рекурсії на прикладах практичних задач |
2 |
|
Тема 5. |
Реалізація дій алгебри поліномів |
1 |
|
Тема 6. |
Схема Горнера. Суперпозиція поліномів |
1 |
|
Змістовий модуль 2. |
Розгляд основ побудови і роботи з базовими структурами даних, що використовуються в обчислювальних процесах. |
8 |
|
Тема 7. |
Пошук та переміщення елементів матриці |
2 |
|
Тема 8. |
Алгоритм Штрассена. Захист 1 завдання |
2 |
|
Тема 9. |
Організація зв’язних списків, стеків і черг. Алгоритми з використання цих структур даних |
2 |
|
Тема 10. |
Організація дерев. Основні дії з бінарними деревами. Захист 2 завдання |
2 |
|
Змістовий модуль 3. |
Методи побудови і аналізу алгоритмів. |
16 |
|
Тема 11. |
Сортування вставками, вибором, обмінами |
2 |
|
Тема 12. |
Швидке сортування, сортування злиттям, пірамідальне сортування |
2 |
|
Тема 13. |
Властивості відрізків та точок, їх спільне розміщення. |
2 |
|
Тема 14. |
Побудова опуклих оболонок. |
2 |
|
Тема 15. |
Найбільша спільна послідовність. |
2 |
|
Тема 16. |
Оптимальна тріангуляція многокутника. |
2 |
|
Тема 17. |
Задача про розклад. Метод передоплати. |
2 |
|
Тема 18. |
Динамічні таблиці. Захист 3 завдання. |
2 |
|
Шифр змістового модуля |
Назва змістового модуля |
Кількість аудиторних годин |
|
Змістовий модуль 1. |
Вивчення основ алгоритмічного мислення. Поняття алгоритму, блок-схеми, принципів побудови алгоритмів та програм. |
6 |
|
Тема1. |
Вступ. Предмет курсу. Поняття алгоритму. Побудова, аналіз, реалізація алгоритму. Псевдокод. Блок-схема. Запис основних операторів у вигляді блок-схем і псевдокодом. Заповнення таблиці прокрутки алгоритму. |
2 |
|
Тема2. |
Лінійні алгоритми. Галужені алгоритми. Циклічні та ітераційні алгоритми. Рекурентні співвідношення. Рекурсія. |
2 |
|
Тема3. |
Робота з поліномами. Реалізація дій алгебри поліномів. Схема Горнера. Суперпозиція поліномів. |
2 |
|
Змістовий модуль 2. |
Розгляд основ побудови і роботи з базовими структурами даних, що використовуються в обчислювальних процесах. |
3 |
|
Тема 5. |
Вектори і матриці. Введення, зберігання, елементи пошуку. Дії матричної алгебри. Порівняння та переміщення елементів матриці. Алгоритм Штрассена. Способи запакування розріджених матриць. |
1 |
|
Тема 6. |
Робота з стуктурами даних. Зв'язні списки. Стеки і черги. Дерева. Хеш-таблиці. |
2 |
|
Змістовий модуль 3. |
Методи побудови і аналізу алгоритмів. |
8 |
|
Тема 7. |
Сортування даних. Сортування вставками, вибором, обмінами, квадратичним вибором. Швидке і розподільне сортування. Сортування злиттям. |
2 |
|
Тема 8. |
Обчислювальна геометрія. Властивості відрізків. Побудова опуклої оболонки. Пошук пари найближчих точок |
2 |
|
Тема 9. |
Динамічне програмування. Найбільша спільна послідовність. Оптимальна тріангуляція многокутника. |
2 |
|
Тема 10. |
Методи побудови і аналізу алгоритмів. Жадні алгоритми. Амортизаційний аналіз. Коди Хаффмена. Задача про розклад. Метод передоплати. Динамічні таблиці. |
2 |
2.5. Самостійна робота студента:
(денна форма навчання)
1. Побудова, аналіз, реалізація алгоритму. -3 год.
2.Заповнення таблиці прокрутки алгоритму. - 3 год.
3.Реалізація ітераційних алгоритмів. - 3 год.
4.Використання рекурсії на прикладах практичних задач. – 3 год.
5.Реалізація дій алгебри поліномів. Схема Горнера. Суперпозиція поліномів. - 4 год.
6. Пошук та переміщення елементів матриці. – 3 год.
7. Алгоритм Штрассена. – 3 год.
8. Організація зв’язних списків, стеків і черг. Алгоритми з використання цих структур даних. – 3 год.
9. Організація дерев. Основні дії з бінарними деревами. - 4 год.
10. Сортування вставками, вибором, обмінами. - 3 год.
11. Швидке сортування, сортування злиттям, пірамідальне сортування. – 3 год.
12. Властивості відрізків та точок, їх спільне розміщення. – 3 год.
13. Побудова опуклих оболонок. - 4 год.
14. Найбільша спільна послідовність. – 3 год.
15. Оптимальна тріангуляція многокутника. - 3 год.
16. Задача про розклад. Метод передоплати. – 5 год.
17. Динамічні таблиці. 4 год.
Базова
Допоміжна
Інформаційні ресурси
|
Оцінка ECTS |
Оцінка в балах |
За національною шкалою |
||
|
Екзаменаційна оцінка, оцінка з диференційованого заліку |
Залік |
|||
|
А |
90 – 100 |
5 |
Відмінно |
Зараховано |
|
В |
81-89 |
4 |
Дуже добре |
|
|
С |
71-80 |
Добре |
||
|
D |
61-70 |
3 |
Задовільно |
|
|
Е |
51-60 |
Достатньо |
Контрольні запитання для самодіагностики
Змістовий модуль 1. Вивчення основ алгоритмічного мислення. Поняття алгоритму, блок-схеми, принципів побудови алгоритмів та програм.
1. Що таке алгоритм?
2. Як оцінити ефективність алгоритму?
3. Що таке складність алгоритму?
4. Чим характеризується будь-який алгоритм?
5. Що таке обчислювальна складність, якою вона буває?
6. Що таке верхня оцінка складності?
7. Як використовується О-нотація для визначення складності алго-ритму?
8. Чому алгоритм з поліноміальною оцінкою обчислювальної складності вважається кращим, ніж з експоненціальною?
9. Що називають рекурсією?
10. Що називають ітерацією?
11. Що таке рекурентне співвідношення?
Змістовий модуль 2. Розгляд основ побудови і роботи з базовими структурами даних, що використовуються в обчислювальних процесах.
1. Що розуміють під ступенем вершини графа?
2. Що розуміють під петлею?
3. У чому полягає матричне подання графів?
4. Що розуміють під матрицею зв’язності графу?
5. Що розуміють під матрицею відстаней на графі?
6. У чому полягає представлення графа у вигляді списку суміжних вершин?
7. Що розуміють під простим шляхом на графі?
8. Що розуміють під Гамільтоновим шляхом на графі?
9. Що розуміють під Ейлеровим шляхом на графі?
10. Які існують способи подання дерев?
11. У чому полягає пошук у ширину на графах та деревах?
12. У чому полягає пошук в глибину на графах та деревах? 1
13. Що таке орієнтований граф?
14. Що розуміють під орієнтованим шляхом?
15. У чому полягає алгоритм Дейкстри?
16. У чому полягає алгоритм Краскала?
Змістовий модуль 3. Методи побудови і аналізу алгоритмів.
1. Що розуміють під обмежуючим прямокутником геометричної фігури?
2. Як визначити довжину відрізку в n-вимірному просторі?
3. Які умови належності точки прямій?
4. Які умови перетину відрізків?
5. Які умови перетину відрізків на прямій?
6. Як визначити відстань від точки до відрізку?
7. Що розуміють під параметричним рівнянням відрізку?
8. Що розуміють під довжиною спільної частини відрізків?
9. У чому полягає алгоритм визначення взаємного розташування точок, прямих та відрізків на площині?
10. У чому полягають алгоритми обробки багатокутників?
11. У чому полягають алгоритми визначення взаємного розташування кіл, прямих та точок?
12. У чому полягає алгоритм побудови опуклої оболонки?
13. Який порядок обходу вершин опуклого багатокутника?
14. Що розуміють під задачами мінімізації в геометричній інтерпретації?
15. У чому полягає метод динамічного програмування?
16. Які задачі розв’язують методом динамічного програмування?
17. Які алгоритми називають евристичними?
18. Коли виникає потреба використовувати евристичні алгоритми?
19. Викласти "жадібний алгоритм" для "задачі про комівояжера".
20. Що розуміють під задачею створення розкладів?
Автор _____________________/_____________________/
(підпис) (прізвище та ініціали)