УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІНЖЕНЕРНО-ТЕХНІЧНИЙ ФАКУЛЬТЕТ КАФЕДРА КОМП’ЮТЕРНИХ СИСТЕМ ТА МЕРЕЖ
«Затверджено» на засіданні Вченої ради інженерно-технічного факультету «_____» ______________ 2012 р. Протокол №___ від «___» ______ 2012 р. Декан ІТФ _________ доц. Туряниця І.І. |
«Затверджено» на засіданні кафедри комп’ютерних систем та мереж інженерно-технічного факультету «_____» ______________ 2012 р. Протокол №___ від «___» ______ 2012 р. Зав. кафедри _________ доц. Король І.Ю. |
|
|
«Затверджено» методичною комісією інженерно-технічного факультету «_____» ______________ 2012 р. Протокол №___ від «___» ______ 2012 р. Голова методичної комісії _________ |
|
Робоча навчальна програма Дисципліни
Алгоритми та методи обчислень
(за вимогами ECTS)
для студентів вищих навчальних закладів ІІІ-IV рівнів акредитації
Галузь знань: 0501 – інформатика та обчислювальна техніка
Напрям підготовки: 6.050102 – комп’ютерна інженерія
ОКР: бакалавр
Структура залікових кредитів
Ужгород – 2012
2. Пояснювальна записка
2.1. Мета і завдання дисципліни, її місце у навчальному процесі
Дисципліна "Теорія алгоритмів та методи обчислювань" відіграє важливу роль у підготовці фахівців за спеціальностями 7.091501 - "Комп‘ютерні системи та мережі". Дана дисципліна належить до циклу інженерних математичних дисциплін і має метою розв'язання головної задачі прикладної математики – фактичного знаходження розв’язку деякої модельної задачі з визначеною точністю.
Мета курсу:
Мета читання дисципліни "Алгоритми та методи обчислювань " визначаються головною задачею прикладної математики – фактичного знаходження деякої модельної задачі з визначеною точністю.
В результаті вивчення дисципліни студент повинен:
ЗНАТИ: предмет чисельних методів, його основні поняття, вимоги до чисельних методів;
математичні моделі та чисельні методи (етапи розв’язування задач на ЕОМ );
похибки результатів чисельного розв’язування задачі (джерела, класифікації похибок, подання дійсних чисел, заокруглення чисел, способи зменшення обчислювальних похибок);
розв’язування рівнянь з одним невідомим (задача відокремлення коренів, методи поділу відрізка навпіл, простої ітерації, Ньютона, хорд та оцінки похибок);
розв’язування систем лінійних алгебраїчних рівнянь (знаходження оберненої матриці, метод Жордана-Гаусса);
задача наближення функцій (інтерполяційні многочлени Лагранжа і Ньютона. Задачі інтерполювання та оберненого інтерполювання та оцінки похибок);
задача чисельного диференціювання та інтегрування. Інтерполяційні многочлени. Оцінки похибок. Квадратурні формули Ньютона-Котеса. Формули прямокутників, трапецій і Сімпсона та оцінки їх залишкових членів;
чисельні методи розв’язування задачі Коші для звичайних диференціальних рівнянь (постановка задачі Коші, наближені методи розв’язування, підходи до оцінки точності);
УМІТИ: обґрунтовувати вибір чисельного методу розв’язування математичної задачі, знати особливості його реалізації на ЕОМ,
володіти алгоритмом методу, вміти скласти програму на одній з мов програмування або використовувати готове ПЗ;
проводити необхідні обчислення і аналіз отриманих результатів.
2.2. Перелік дисциплін, розділів, тем, засвоєння яких необхідне для
вивчення даної дисципліни
Курс “Теорія алгоритмів та методи обчислювань” базується на дисципліни “Лінійна алгебра і аналітична геометрія”, “Математичний аналіз” та “Програмування”.
3. Розподіл змісту освітньо-професійної програми та навчального часу
за модулями
№ п/п |
Теми |
Всього годин |
З них |
||||
Лекції |
Практичні |
Лабораторні |
Самостійна робота |
Індивідуальна робота |
|||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Змістовний модуль 1. МЕТОДИ РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ РІВНЯНЬ, СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ ТА СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ |
|||||||
1. |
Вступ. Математичні моделі та чисельні методи. Предмет та методи обчислювальної математики, поняття про обчислювальний експеримент. Методи розв’язування математичних задач. Чисельні методи. Вимоги до чисельних методів. Стійкість. Коректність. Приклади задач, які чутливі до похибок вхідних даних. Приклади нестійких методів (алгоритмів). Елементи теорії похибок. Дії з наближеними числами. Класифікація похибок. Основні теореми про похибки. |
6 |
2
|
|
|
2
|
|
2. |
Розв’язання нелінійних рівнянь з одним невідомим. Відокремлення коренів. Методи уточнення коренів: поділу відрізка навпіл, простої ітерації та його модифікації; їх геометрична інтерпретація, збіжність та оцінка похибки. Методи Ньютона, хорд, комбінований; їх геометрична інтерпретація, збіжність та оцінка похибки. |
14 |
6 |
|
6
|
4 |
|
3. |
Розв’язання систем лінійних алгебраїчних рівнянь. Прямі методи розв’язання систем лінійних алгебраїчних рівнянь. Метод Гауса (схема з вибором головного елемента). Класична та матрична форма реалізації методу Гауса. Розкладання матриці на множники (LU- розкладання, метод квадратних коренів). Ітераційні методи: простої ітерації, Гауса-Зейделя. |
12
6
4 |
4
2
|
|
4
2
2 |
4
2
2 |
|
4. |
Чисельні методи розв’язання системи нелінійних рівнянь. Метод Ньютона та його реалізація засабами пакету Mathcad. Метод скорішого спуску (метод градієнта). |
14 |
4 |
|
4 |
6 |
|
6 |
Модульна контрольна робота № 1 (2 години) |
56 |
18 |
|
18 |
20 |
|
Змістовний модуль 2. ІНТЕРПОЛЮВАННЯ ФУНКЦІЙ. ЧИСЕЛЬНЕ ДИФЕРЕНЦІЮВАННЯ ТА ІНТЕГРУВАННЯ ФУНКЦІЙ. ОБЧИСЛЕННЯ ВЛАСНИХ ЗНАЧЕНЬ ТА ВЛАСНИХ ВЕКТОРІВ МАТРИЦЬ.
|
|||||||
4. |
Інтерполяція і наближення функцій. Постановка задачі наближення функцій. Канонічний многочлен. Інтерполяційний многочлен Лагранжа. Похибка інтерполяційної формули Лагранжа. Мінімізація оцінки похибки інтерполяції. Поліноми Чебишева. Інтерполяційні формули Ньютона. |
18
|
6
|
|
4
|
8
|
|
5. |
Чисельне диференціювання функцій. Чисельне диференціювання функцій. Формули чисельного диференціювання, одержані на основі формули Ньютона. Формули диференціювання для практичних обчислень. Залишковий член формули чисельного диференціювання Н’ютона. |
6 |
1
|
|
2
|
3
|
|
|
Чисельне інтегрування функцій. Чисельне інтегрування функцій. Квадратурні формули Ньютона – Котеса. Квадратурні формули: прямокутників, трапецій, Сімпсона. Практичні способи оцінювання похибки інтегрування. Правило Рунге. Інтерполяція за Річардсоном. |
15 |
5
|
|
6
|
4
|
|
1. |
Обчислення власних значень та власних векторів матриці. Метод характеристичного рівняння матриці. Метод Фадєєва-Лавер’є. Метод Крилова. Обчислення окремих власних значень. |
16 |
6 |
|
6 |
4 |
|
6 |
Модульна контрольна робота № 2 (2 години) |
55 |
18 |
|
18 |
19 |
|
|
Разом за семестр |
111 |
36 |
|
36 |
39 |
|
Змістовний модуль 3. РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЗАДАЧ КОШІ ТА КРАЙОВИХ ЗАДАЧ |
|||||||
1. |
Розв’язання задач лінійного програмування. Формулювання задачі лінійного програмування. Геометричний метод розв’язання задачі лінійного програмування. Симплекс метод розв’язання задачі лінійного програмування |
12 |
4
|
|
4
|
4
|
|
2 |
Чисельні методи розв’язування задачі Коші для звичайних диференціальних рівнянь. Основні поняття. Наближені методи розв’язання задачі Коші: Ейлера, Рунге-Кутта. Інтерполяційні методи:Адамса-Бішфорта, Адамса-Мултона. Метод предиктор-коректор. |
10
10 |
4
4 |
|
2
2 |
4
4 |
|
3. |
Неявні методи розв’язання жорстких диференціальних рівнянь та їх систем. Поняття жорсткості диференціального рівняння. Неявні методи Ейлера. Багатокрокові методи Гіра. |
12 |
4 |
|
4 |
4 |
|
4. |
Крайові задачі для звичайних диференціальних рівнянь та рівнянь з частинними похідними. Постановка задачі. Розв’язування крайової задачі методом прицілювання. Метод скінчених різниць. |
10 |
2 |
|
4 |
4 |
|
|
Модульна контрольна робота № 3 (2 години) |
54 |
18 |
|
16 |
20 |
|
|
Разом за семестр |
54 |
18 |
|
16 |
20 |
|