Програма Фахового вступного випробовування для здобуття освітньо-кваліфікаційного рівня спеціаліста, магістра



Скачати 303.01 Kb.
Дата конвертації23.05.2017
Розмір303.01 Kb.
Міністерство освіти і науки України

Львівський національний університет імені Івана Франка

Затверджено

на засіданні приймальної комісії

Львівського національного університету

імені Івана Франка

24.02.2014 р. (протокол № 4)

Перший проректор

______________В.С. Височанський



програма

Фахового вступного випробовування

для здобуття освітньо-кваліфікаційного рівня

спеціаліста, магістра
Спеціальність:

7.04030201, 8.04030201 «Інформатика»

7.04030202, 8.04030202 «Прикладна інформатика»
Львів-2014

Програма вступних фахових випробувань для вступників на навчання для здобуття ОКР магістра (спеціаліста) факультету прикладної математики та інформатики

Напрям підготовки: інформатика

Математичний аналіз

  1. Теорія множин. Точна верхня та нижня межі множини. Числові послідовності та підпослідовності. Границя числової послідовності. Часткові границі послідовності. Верхня та нижня границі послідовності.

  2. Функція однієї дійсної змінної. Границя функції в точці. Неперервність. Похідна функції (заданої явно, неявно, параметрично, оберненої функції). Похідні вищих порядків.

  3. Екстремум функції однієї дійсної змінної.

  4. Невизначений та визначений інтеграли. Геометричні застосування визначеного інтеграла (площа криволінійної трапеції та криволінійного сектора, довжина дуги кривої). Невластивий інтеграл. Збіжність невластивого інтеграла.

  5. Числовий ряд. Збіжність числового ряду (з невід’ємними членами, знакозмінного). Степеневі ряди. Радіус, інтервал та множина збіжності степеневого ряду.

  6. Функції багатьох змінних. Подвійна границя функції двох дійсних змінних. Екстремум функції багатьох змінних. Умовний екстремум функції багатьох змінних.

  7. Кратні і потрійні інтеграли. Їх застосування (площа плоскої фігури, об’єм тіла обмеженого поверхнями, площа поверхні).

  8. Криволінійні інтеграли 1-го та 2-го роду. Поверхневі інтеграли 1-го роду та 2-го роду.

Функціональний аналіз

  1. Лінійні нормовані простори: означення, приклади та елементи аналізу.

  2. Повні нормовані простори: простори Банаха та Гільберта.

  3. Елементи найкращого наближення в банахових та гільбертових просторах.

  4. Лінійні оператори: неперервність, обмеженість, норма.

  5. Обернені оператори: умови існування, коректність операторних рівнянь.

  6. Спряжені простори: теорема Picea про загальний вигляд лінійних обмежених функціоналів у гільбертовому просторі.

  7. Спряжені та самоспряжені оператори. Оператори ортогонального проектування.



Диференціальні рівняння


  1. Задача Коші для звичайного диференціального рівняння першого порядку.

  2. Теорема існування та єдиності розв'язку.

  3. Методи розв'язування звичайних диференціальних рівнянь першого порядку.

  4. Нормальні системи звичайних диференціальних рівнянь.

  5. Задача Коші, умови існування та єдиності її розв'язку.

  6. Нормальні лінійні системи звичайних диференціальних рівнянь.

  7. Фундаментальна система розв'язків лінійної однорідної системи та її існування.

  8. Структура загального розв'язку однорідної та неоднорідної системи.

  9. Стійкість за Ляпуновим автономних систем звичайних диференціальних рівнянь.

  10. Стійкість за першим наближенням.

  11. Методи розв'язування лінійних систем зі сталими коефіцієнтами.

  12. Лінійні диференціальні рівняння зі сталими коефіцієнтами та методи їх розв’язування.



Рівняння з частинними похідними


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

  2. Формулювання основних задач для лінійних рівнянь з частинними похідними другого порядку.

  3. Коректність задачі Коші для рівнянь коливань струни та мембрани.

  4. Метод Фур'є для рівняння коливань струни, поширення тепла в стержні, рівняння Лапласа в крузі і зовні круга.

  5. Принцип максимуму для розв'язків рівняння теплопровідності.

  6. Існування ролзв'язку задачі Коші для рівняння теплопровідності.

  7. Властивості гармонічних функцій.

Теорія імовірності та математична статистика

  1. Ймовірності випадкових подій

  2. Послідовності незалежних випробувань

  3. 3.Випадкові величини

  4. Числові характеристики випадкових змінних

  5. Закон великих чисел

  6. Характеристичні функції випадкових змінних

  7. Ланцюг Маркова

  8. Стохастичні процеси

  9. Основні поняття математичної статистики

  10. Ймовірностна основа статистичних висновків

  11. 11.Оціювання невідомих параметрів розподілів генеральних сукупностей

  12. Критерії, основані на порівнянні ймовірностей і відносних частот

  13. Критерій погодженості

  14. Варіансний аналіз

  15. Кореляційний і регресійний аналізи

Дискретна математика

  1. Основи (логіка і методи доведення теорем, множини, функції). Логіка висловлювань. Виконанна, загальнозначуща (тавтологія) та заперечувана формули. Закони логіки висловлювань. Нормальні форми логіки висловлювань (диз’юнктивні та кон’юнктивні). Доведення теорем. Логіка першого ступеня. Закони логіки першого ступеня. Логічне виведення в логіці висловлювань. Застосування правил виведення в логіці висловлювань. Метод резолюцій. Множина. Діаграми Венна. Кортеж. Декартів добуток. Операції над множинами. Закони, яким задовольняють теоретико-множинні операції. Доведення рівностей із множинами. Операції над бітовими рядками. Комп’ютерне подання множин.

  2. Комбінаторний аналіз. Основні правила комбінаторики. Розміщення та сполучення (без повторень і з повтореннями). Перестановки. Біноміальна і поліноміальна теореми. Розбиття n-елементної множини. Числа Стірлінга другого роду і числа Белла. Рекурентні рівняння та їх розв'язування. Принцип коробок Діріхле. Принцип включення-виключення.

  3. Теорія графів. Означення різних типів графів та головні теореми про властивості графів. Спеціальні класи простих графів. Ізоморфізм графів. Матриця інцидентності. Матриця суміжності. Подання графа списком ребер. Подання графа списками суміжності. Шляхи та цикли. Зв’язність. Числові характеристики зв’язності. Критерій дводольності графа (теорема Кеніга). Ейлерів цикл у графі, критерій ейлерового циклу. Гамільтонів цикл, достатня умова гамільтонового циклу (теорема Дірака). Зважені графи. Задача пошуку найкоротших шляхів, алгоритм Дейкстри. Планарні графи. Розфарбування графів. Незалежні множини вершин. Кліки. Паросполучення в дводольних графах, теорема Голла.

  4. Дерева та їх застосування. Основні означення та властивості дерев. Кореневе дерево, m-арне дерево. Рекурсія. Обхід дерев. Польський та зворотний польський записи виразів. Бінарне дерево пошуку. Дерево рішень. Бектрекінг (пошук із поверненнями). Каркаси. Задача про мінімальний каркас, алгоритм Краскала.

  5. Відношення. Відношення та їх властивості. Відношення еквівалентності. Відношення часткового порядку. Топологічне сортування. Операції над відношеннями. Замикання відношень. Алгоритм Уоршалла.

  6. Основи теорії кодів. Алфавітне й рівномірне кодування. Достатні умови однозначності декодування (властивість префікса). Властивості роздільних кодів (нерівність Мак-Міллана). Оптимальне кодування. Алгоритм Фано. Алгоритм Гаффмана. Коди, стійкі до перешкод. Коди Геммінґа.

  7. Булеві функції. Означення булевої функції. Способи подання булевих функцій. Алгебри булевих функцій. Кон’юнктивні й диз’юнктивні нормальні форми. Поліном Жегалкіна. Повнота системи булевих функцій. Основні замкнені класи. Критерій повноти. Мінімізація булевих функцій.

  8. Моделювання обчислень (формальні мови, породжувальні граматики, автомати). Поняття формальної мови. Породжувальні граматики, їх класифікація за Хомські. Дерева виведення. Скінченні автомати з виходом. Скінченні автомати без виходу. Подання мов.

  9. Основи теорії алгоритмів. Основні вимоги до алгоритмів. Машини Тьюрінга. Функції, обчислювані за Тьюрінгом. Теза Тюрінга.

Чисельні методи

  1. Ітераційні методи розв’язування алгебраїчних і трансцендентних рівнянь. Метод простої ітерації. Метод хорд. Метод Ньютона.

  2. Чисельні методи розв’язування систем нелінійних рівнянь. Метод ітерацій. Метод Ньютона. Модифікований метод Ньютона.

  3. Рівномірні наближення. Постановка задачі про рівномірне наближення функцій, функції найкращого рівномірного наближення. Рівномірне наближення функцій класу С. Перша теорема Вейєрштрасса (лема 1, лема 2, теорема Бернштейна).

  4. Теорія інтерполювання. Постановка задачі інтерполювання. Узагальнений інтерполяційний многочлен. Система функцій Чебишева. Ознака, за якою системи функцій є системою Чебишева. Приклади систем Чебишева. Інтерполяційний многочлен Лагранжа і його залишковий член.

Розділені різниці і їх властивості. Інтерполяційні формули Ньютона для інтерполювання вперед і назад для нерівновіддалених вузлів інтерполювання та їх залишкові члени.

Скінченні різниці та їх властивості. Зв’язок скінченних різниць з розділеними. Інтерполяційні формули Ньютона для інтерполювання вперед і назад для рівновіддалених вузлів інтерполювання та їх залишкові члени.



  1. Середньоквадратичні наближення. Характеристика елемента найкращого наближення в просторі зі скалярним добутком (критерій існування елемента найкращого наближення). Поняття визначника Грама системи елементів простору. Критерій лінійної незалежності системи елементів. Побудова елемента найкращого наближення в просторі зі скалярним добутком.

Постановка задачі середньоквадратичного наближення функцій. Побудова найкращого середньоквадратичного наближення в гільбертовому просторі.

Наближення функцій, заданих таблично, за методом найменших квадратів. Ров’язування несумісних систем лінійних алгебраїчних рівнянь за методом найменших квадратів.



  1. Числове інтегрування. Постановка задачі, поняття квадратурної формули, абсцис, коефіцієнтів. Загальна квадратурна формула інтерполяційного типу, обчислення її коефіцієнтів. Квадратурна формула Ньютона-Котеса. Формули прямокутників, трапецій, парабол та їх залишкові члени.

Алгебраїчна міра точності квадратурної формули. Квадратурні формули найвищої алгебраїчної міри точності (формули Гаусса). Критерій, за яким квадратурна формула має найвищу алгебраїчну міру точності.

Наближене обчислення кратних інтегралів.



  1. Чисельні методи розв’язування задачі Коші для звичайних диференціальних рівнянь. Класифікація наближених методів розв’язування задачі Коші для звичайних диференціальних рівнянь.

Чисельні методи розв’язування задачі Коші для звичайних диференціальних рівнянь першого порядку. Метод Ейлера. Метод Рунге-Кутта s-го порядку. Часткові випадки методу при s=1,2,3,4. Екстаполяційний та інтерполяційний методи Адамса.

Чисельні методи розв’язування задачі Коші для систем звичайних диференціальних рівнянь першого порядку. Метод Ейлера. Метод Рунге-Кутта s-го порядку. Часткові випадки методу при s=1,2,3,4. Екстраполяційний та інтерполяційний методи Адамса.



  1. Наближені методи розв’язування крайових задач для звичайних диференціальних рівнянь. Метод сіток (різницевий метод) розв’язування крайових задач для лінійних диференціальних рівнянь. Ідея методу. Метод заміни диференціального рівняння і крайових умов системою алгебраїчних рівнянь. Питання розв’язності системи різницевих рівнянь. Дискретний принцип максимуму.

Числові методи математичної фізики

1. Абстрактна варіаційна задача, теорема Лакса-Мільграма-Вишика.

2. Крайова задач для рівняння Пуассона та її варіаційне формулювання.

3. Метод Гальоркіна.

4. Простори апроксимацій методу скінченних елементів (МСЕ).

5. Схема МСЕ та їх збіжність.

6. Проекційно-сіткові схеми для початково-крайових задач з параболічним рівнянням

7. Проекційно-сіткові схеми для початково-крайових задач з гіперболічним рівнянням.

Апроксимація на скінченних елементах

Чисельні методи лінійної алгебри


  1. Метод Гауса для розв’язання систем лiнiйних алгебраїчних рiвнянь.

  2. Метод Холецького (LU розклад) для розв’язання систем лiнiйних алгебраїчних рiвнянь.

  3. Метод простої ітерації та метод Зейделя для розв’язування систем лінійних алгебраїчних рівнянь та теореми про збіжність.

  4. Перетворення Хаусхолдера.

  5. Зведення узагальненої повної проблеми на власні значення до класичної повної проблеми з симетричною матрицею.

  6. Застосування перетворення Хаусхолдера для приведення симетричної матриці до тридіагонального вигляду.

  7. Теореми, на яких грунтується метод поділу відрізка навпіл для визначення власних значень тридіагональної матриці. Алгоритм методу.

  8. Метод Якобі для розв"язання повної класичної матричної проблеми на власні значення.

  9. Узагальнена часткова проблема на власні значення. Метод Релея. Метод ітерації підпростору.

Методи оптимізації

1. ОСНОВНІ ПОНЯТТЯ. Типи задач оптимізації. Математичне програмування (основні означення). Існування розв’язку. Геометрична інтерпретація задач оптимізації.

2. ЛІНІЙНЕ ПРОГРАМУВАННЯ. Задача лінійного програмування в загальній, основній і канонічній формах. Властивості розв’язків задач лінійного програмування. Опорні плани. Симплексний метод. Пошук початкового опорного плану. Поняття двоїстості. Двоїста задача до лінійної задачі у канонічній формі. Означення двоїстості у загальному випадку. Теореми двоїстості. Застосування двоїстості.

3. ОДНОВИМІРНА ОПТИМІЗАЦІЯ. Числові методи мінімізації унімодальних функцій (дихотомія, метод Фібоначчі, золотий поділ, поліноміальна інтерполяція).

4. ЕЛЕМЕНТИ ОПУКЛОГО АНАЛІЗУ. Опуклі множини. Опуклі і сильно опуклі функції. Диференціальні критерії опуклості. Екстремальні властивості опуклих функцій, необхідна умова оптимальності диференційовної функції на абстрактно заданій множині. Проекція точки на множину. Віддільність опуклих множин.

5. НЕЛІНІЙНА ОПТИМІЗАЦІЯ БЕЗ ОБМЕЖЕНЬ. Умови оптимальності. Числові методи мінімізації диференційовних функцій (градієнтні методи, метод Ньютона, методи спряжених градієнтів).

6. НЕЛІНІЙНА ОПТИМІЗАЦІЯ З ОБМЕЖЕННЯМИ. Теорема Куна–Таккера у термінах сідлової точки. Випадок диференційовності. Метод проекції градієнту. Метод умовного градієнту. Метод штрафних функцій.

7. ОСНОВИ ВАРІАЦІЙНОГО ЧИСЛЕННЯ. Задачі оптимізації у функціональних просторах. Найпростіша задача. Варіація та її властивості. Рівняння Ейлера. Функціонали, що залежать від декількох функцій. Функціонали, що залежать від похідних вищого порядку.



Дослідження операцій

  1. ПРЕДМЕТ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ. Операція та її математична модель. Основні класи задач дослідження операцій. Головні етапи операційного дослідження. Приклади математичних моделей дослідження операцій.

  2. БАГАТОКРИТЕРІАЛЬНІ ЗАДАЧІ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ. Основні поняття та постановка задач. Головні підходи до розв’язування багатокритеріальних задач.

  3. ЕКСТРЕМАЛЬНІ ЗАДАЧІ НА ГРАФАХ. Задача про мінімальний каркас (алгоритми Краскала і Пріма). Реалізація алгоритмів. Різні формулювання задач про найкоротший шлях. Знаходження найкоротшого шляху від заданої вершини (алгоритми Дейкстри та Форда). Знаходження найкоротших шляхів між будь-якими парами вершин графа (алгоритм Флойда).

  4. ЗАДАЧА ПРО МАКСИМАЛЬНИЙ ПОТІК. Поняття потоку. Загальне формулювання потокових задач. Теорема Форда–Фалкерсона. Алгоритм відшукання максимального потоку. Узагальнення задачі про максимальний потік.

  5. ПЛАНУВАННЯ НА МЕРЕЖАХ. Основні поняття та визначення. Структура та правила побудови. Оптимізація мережі.

  6. ТРАНСПОРТНА ЗАДАЧА. Формулювання транспортної задачі. Властивості транспортної задачі. Опорні плани та їх властивості. Методи побудови початкових опорних планів (метод північно-західного кута, метод мінімального елемента, метод Фогеля). Двоїста задача. Умови оптимальності. Метод потенціалів розв’язування транспортної задачі. Випадок вродженості. Відкрита та закрита модель. Метод диференціальних рент. Приклади задач, що зводяться до транспортної. Задача про призначення. Транспортна задача за критерієм часу.

  7. ЦІЛОЧИСЛОВЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ. Методи гілок і меж. Загальна схема. Метод гілок і меж для задач лінійного цілочислового програмування. Задача комівояжера.

  8. ІГРИ ДВОХ ГРАВЦІВ. Основні поняття теорії ігор. Класифікація ігор. Матрична гра двох гравців із нульовою сумою виграшів. Верхня та нижня ціни гри. Оптимальні мішані стратегії та їх властивості. Спрощення ігор. Ігри порядку 2×2, 2×n, m×2. Розв’язування матричних ігор шляхом зведення до задач лінійного програмування. Поняття біматричної гри. Умови рівноваги для біматричної гри. Розв’язування біматричних ігор.

  9. ІГРИ n ГРАВЦІВ. Поняття позиційної гри та її нормальної форми. Графічне представлення позиційної гри. Позиційні ігри з повною інформацією.

Програмування

  1. Вказівники і посилання в С++. Масиви.

  2. Функція – основна програмна одиниця мови С++.

  3. Класи – основний засіб визначення типів. Конструювання об’єктів.

  4. Перевизначення операторів в С++.

  5. Наслідування як механізм повторного використання коду.

  6. Поліморфізм.

  7. Механізм контролю назв

  8. Множинне наслідування.

  9. Винятки як системний підхід до обробки помилок.

  10. Параметризовані функції та класи.

  11. Узагальнене програмування на основі STL. Контейнери і алгоритми.

  12. Об’єкти-функції та їх використання з алгоритмами для обробки контейнерів.

  13. Програмування з використанням послідовних контейнерів

  14. Програмування з використанням асоціативних контейнерів.

  15. Ієрархія потокових шаблонів.

  16. Призначення та особливості реалізації мовою С++ патернів створення об'єктів Singleton і Factory Method.

  17. Призначення та особливості реалізації мовою С++ структурних патернів Adapter і Bridge.

  18. Призначення та особливості реалізації мовою С++ патернів поведінки Сommand, Iterator і Strategy.

  19. Загальна структура Windows-програми та її виконання.

  20. Повідомлення як дані для керування виконанням Windows-програмою.

  21. Вікно – основний елемент візуального інтерфейсу програми.

  22. Особливості визначення типів в С#.

  23. Розробка графічного інтерфейсу користувача засобами класів System.Windows.Forms.

  24. Графічні об’єкти System.Drawing.

  25. Зв’язування даних. Табличне представлення даних за допомогою DataGridView.

  26. Серіалізація за допомогою XmlSerializer.

  27. Робота з базою даних засобами Data.Command.

  28. Робота з базою даних засобами DataSet і DataAdapter.

  29. LINQ як модель доступу до даних. Оператори стандартних запитів.

  30. Об'єктна модель LINQ to SQL. DataContext як джерело даних.

  31. LINQ to DataSet. Розширення методами інтерфейсу IEnumerable.

  32. Архітектура 16-ти і 32-розрядних процесорів. Асемблерні команди, адресування операндів.

  33. Використання бібліотек DLL: виклик функцій, явне зв’язування з бібліотекою.

  34. Використання макровизначень.

  35. Алгоритми функціонування та створення редактора тексту, табличного процесора, компілятора з мови асемблера

БАЗИ ДАНИХ

  1. Історія розвитку БД. Основи побудови банків даних. Бази знань. Трьохрівневе зображення даних.

  2. Моделі даних. Ієрархічна сіткова та реляційна модель даних. Об’єктно-орієнтована модель.

  3. Структури даних реляційної моделі. Ключі відношень. Основи реляційної алгебри. Основні та додаткові операції.

  4. Нормалізація схем баз даних. Аномалії. Функціональні залежності. Аксіоми Армстронга. Несуперечливість та повнота аксіом.

  5. Розклади реляційних схем баз даних (без втрати даних, без втрати залежностей, та на незалежні складові. Перша, друга, третя нормальні форми. Нормальна форма Бойса-Кодда.

  6. Багатозначні залежності. Аксіоми багатозначних залежностей. Четверта та п’ята нормальні форми. Нормальні форми вищих порядків.

  7. Еквівалентність та критерій якості схем баз даних. Проектування схем реляційних БД. Метод декомпозиції Kodda-Fagina, алгоритми синтезу Barnsteina, алгоритм Rissanena.

  8. Використання ER підходу до проектування БД. Правила виводу відношень із ER - діаграм.

  9. Поняття про розподілені БД.

  10. Об’єктно-орієнтовані бази даних.

  11. Гіпермедіальні системи. Географічні інформаційні системи.

  12. Системи програмування БД. СКБД реляційного типу (Foxpro, Access, Paradox). Початкове створення БД. Приклад.

  13. Додавання записів у файл БД. Приклад. Перегляд записів БД. Функції.

  14. Сортування та індексування записів БД. Команди. Приклади. Керування індексами.

  15. Пошук даних в базі.

  16. Редагування даних. Команди редагування. Приклади.

  17. Робочі області. Зв’язки один до одного та один до багатьох. Об’єднання баз даних. Приклади.

  18. Командні файли. Приклади.

  19. Введення-виведення даних. Приклади.

  20. Команди галуження та організації циклів.

  21. Організація меню. Створення інформаційної системи. Приклади.

  22. Мова запитів SQL.

  23. Створення та друкування звітів. Приклади.

  24. Використання об’ктно-орієнтованого підходу.

Архітектура комп’ютерних систем та мереж

1. БАЗОВІ ПРИНЦИПИ ОРГАНІЗАЦІЇ І елементна база СУЧАСНИХ цифрових обчислювальних систем

1.1. Історія розвитку обчислювальних систем. Архітектура фон Неймана - основа цифрових обчислювальних машин. Поняття алгоритму і його вплив на організацію ЕОМ. Базові принципи архітектури фон Неймана: принцип програмного управління, концепція зберігання програми в пам'яті. Основні функціональні пристрої ЕОМ архітектури фон Неймана: арифметико-логічний пристрій, пристрій пам'яті, пристрої для уведення і виведення інформації, пристрій управління.

1.2. Багаторівнева організація ЕОМ Фізичний рівень. Рівень аналогової схемотехніки. Рівень цифрової схемотехніки. Рівень системотехніки. Мікроархітектурний рівень. Рівень машинних команд. Рівень операційної системи. Рівень мови асемблера. Мови високого рівня.

1.3. СТАН І ПЕРСПЕКТИВИ РОЗВИТКУ елементної бази сучасних обчислювальних систем Поняття мікроелектронного пристрою, інтегральної схеми (ІС). Особливості мікроелектронної технології, її переваги. Обмеження на шляху збільшення продуктивності ЕОМ.

2. ТЕОРЕТИЧНІ ОСНОВИ ФУНКЦІОНУВАННЯ ЦИФРОВОЇ ЕОМ

2.1. Інформаційна та елементна база ЕОМ. Поняття про інформацію. Системи числення. Форми представлення чисел в ЕОМ. Основи алгебри логіки. Логічний елемент
Класифікація логічних елементів за способом кодування двійкових змінних. Базова схема як схемотехнічна основа логічного елемента. Базові схеми найпростіших логічних елементів (І, АБО, НЕ).

2.2. ФУНКЦІОНАЛЬНІ ВУЗЛИ ЕОМ Поняття про елементну базу ЕОМ (тригер, суматор, регістр, зсувач, шифратор, дешифратор, лічильник, арифметико-логічний пристрій). Реалізація типових комбінаційних схем. Запам'ятовувальні елементи: конденсатор з ключовим транзистором, асинхронна RS-защіпка, синхронна RS-защіпка, синхронна D-защіпка, RS-тригер, D-тригер. Типові послідовні вузли: регістри, лічильники, суматори.

2.3. Вступ до проблематики синтезу логічних схем . Таблиці істинності , логічні блоки на основі елементів певного логічного базису та їх схемна реалізація.

3. Класифікація архітектур обчислювальних систем

3.1. Характеристики продуктивності обчислювальних систем. Характеристики продуктивності на рівні апаратного забезпечення. Оцінка продуктивності на рівні програмного забезпечення.

3.2 Класифікація архітектур обчислювальних систем за інтегральними ознаками: взаємодія ЦП, ОЗУ, ПП (однопроцесорні, потужний процесор + периферійні процесори, багатопроцесорні, з магістральною шиною, мережна, функціонально-переналагоджувальна, масс-процесорна);

3.3. КЛАСИФІКАЦІЯ ФЛІННА (взаємодія потоку команд і потоку даних). Архітектури ОКОД (SISD), БКОД (MISD), БКБД (MIMD), Архітектури SIMD: масивно-паралельні процесори, векторні процесори. Приклад архітектури SIMD. Архітектури MIMD.

3.4 Класифікація за функціональним призначенням. Аналогові, цифрові та гібридні ЕОМ.

3.5. Класифікація за способом організації команд: CISC, RISC, MISC.

3.6. Симетричні мультипроцесори, моделі спільного використання пам'яті: сувора погодженість, узгодженість за послідовністю, процесорна узгодженість, слабка узгодженість, вільна узгодженість. Мультипроцесори UMA з шинної організацією, з координатним комутатором, з багатоступінчатими мережами. Мультипроцесори NUMA: NC-NUMA, CC-NUMA. Мультипроцесори COMA.

4. АРХІТЕКТУРА СУЧАСНИХ МІКРОПРОЦЕСОРІВ

4.1. БАЗОВІ ПРИНЦИПИ ОРГАНІЗАЦІЇ МІКРОПРОЦЕСОРА Канонічна схема мікропроцесора. Системи, види і формати команд універсальних мікропроцесорів. CISC-і RISC-архітектури. Вибірка, дешифрування та виконання команд. Подання роботи обчислювального тракту процесора на мікроархітектурному рівні.Режими адресації пам'яті та пристроїв вводу-виводу. Система переривань. Механізми звернення до підпрограм. Мікропроцесор Intel 8086(88). Машинна мова. Архітектура процесора. Регістри загального призначення. Індексні регістри та регістри-вказівники. Регістри сегменту. Шини мікропроцесора. Зв’язок з магістраллю. Переривання (внутрішні та зовнішні, масковані та немасковані).

4.2. НАПРЯМКИ РОЗВИТКУ АРХІТЕКТУРИ сучасних універсальних мікропроцесорів.
Конвейеризація виконання команд. Суперскалярна архітектура. Конвеєри процесорів Pentium, Pentium Pro, Pentium II, Pentium IY. Технологія перейменування регістрів. Технологія просування даних. Трирівнева кеш-пам'ять команд та кеш-пам'ять даних. Динамічне передбачення розгалужень. Розширення і конвейеризації циклів шини даних. Засоби забезпечення надійності даних. Підтримка мультипроцесора.

4.3 64-розрядні мікропроцесори. ПЕОМ на базі багатоядерних процесорів. Особливості архітектури.



Основи Веб-технологій

Телекомунікаційні та інформаційні системи, структура мережі Інтернет

1. Розвиток телекомунікаційних та інформаційних систем

Історія розвитку телекомунікаційних мереж. Технології, середовища та методи передавання інформації. Історія появи Інтернет. Перші мережні сервіси.

2. Структура мережі Інтернет

Статичні та динамічні ресурси. Основні технології реалізації клієнтської та серверної активності. Домени та адресація ресурсів Інтернету: IP-адреси, служба імен DNS, URI - уніфікований ідентифікатор ресурсу.

Мова розмітки HTML

3. Поняття гіпертексту

Лінійне та не лінійне читання документів. Літературні спроби модифікації лінійного читання (Милорад Павич). Структурні елементи документа. Наукова та технічна документація. Історична довідка (хронологія стандартів).

4. Структура документа

Визначення тега. Структура HTML-документа: голова та тіло. Теги заголовної частини HTML-документа. Мета-інформація. Атрибути дескриптора .

5. Форматування тексту

Заголовки, абзаци, впорядковані та невпорядковані списки, списки визначень, розділи та виділення, додаткові елементи (
,


,
, , ). Таблиці.

6. Гіпервказівники, зображення та інші вбудовані об’єкти

Вказівники та якорі. Формати графічних файлів. Дескриптор . Карти зображень. Мультимедіа у Веб. Дескриптор .

7. Фреймові документи

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

8. Форми та їх елементи

Дескриптори форм.

Каскадні таблиці стилів

9. Визначення та синтаксис

Поняття стилю. Три рівні стилів: рядка, документа та зовнішні. Селектори. Множинні, контекстні та атрибутивні селектори. Класи. Звичайні, загальні та псевдокласи. Наслідування.

10. Властивості стилів

Одиниці вимірювання в CSS. Властивості текстових елементів. Блочна модель та властивості блочних елементів. Позиціонування та видимість. Нові властивості в CSS3.

Сучасні тенденції розвитку мов розмітки

11. Мова розмітки XML

Основні поняття: коректність, валідність та синтаксичний аналізатор. Основні вимоги синтаксису XML. Логічна структура XML-документа.

12. Рекомендації XHTML. Визначення DOCTYPE

Правила переформулювання HTML в XML. Оголошення типу документа та його відповідність DTD.

Реалізація клієнтської активності

13. Модель документа DOM

Об’єкти на стороні клієнта. Об’єктна модель документа DOM.

14. Синтаксис мови JavaScript

Ідентифікатори, ключові слова, змінні, типи даних. Вирази та операції. Функції.

15. Події та їх обробка

Модель подій. Основні події, об’єкти та обробітники.
Моделювання складних систем
Принципи та етапи побудови моделей складних систем.

Поняття системи. Характеристики складних систем. Задача аналізу. Задача синтезу. Види моделей та рівні моделювання складних систем. Принципи та етапи побудови моделей складних систем. Класифікація моделей.

Постановка задач моделювання та аналізу чутливості.

Диференціальна модель поведінки динамічної системи з розподіленими параметрами. Постановка прямих та обернених задач. Задачі ідентифікації параметрів. Задачі оптимізації. Задачі аналізу чутливості. Методи обчислення коефіцієнтів чутливості.

Моделювання динаміки процесів задачами Коші для систем звичайних диференціальних рівнянь (СЗДР).

Моделі росту та взаємодії популяцій. Моделі суперництва в соціальних системах (моделювання гонки озброєнь між двома країнами, моделювання бойових дій двох армій). Моделі поширення епідемій в біологічних та комп’ютерних системах. Побудова моделей еколого-економічних процесів. Врахування ефекту запізнення в моделях динамічних систем. Якісний аналіз моделей у вигляді СЗДР (особливі точки, фазові криві). Постановка прямих та обернених задач для моделей у вигляді СЗДР. Аналіз чутливості в СЗДР.

Моделювання динаміки процесів рівняннями в частинних похідних.

Моделювання динаміки процесів із врахуванням дифузії. Побудова моделей ресурс-споживач. Постановка прямих та обернених задач для динамічних моделей у вигляді рівнянь в частинних похідних. Аналіз чутливості в системах параболічного типу.


Основи екології


Розділ1. Про екологічні системи. Основні поняття та терміни. Стійкість екологічних систем. Умови існування і приклади екологічних систем. Біосфера. Біоценоз. Біогеоценоз.

Розділ 2. Математичні моделі в екології та методи їх дослідження. Динаміка еволюції популяцій (модель „хижак-жертва”). Математичні моделі хімічного забруднення довкілля. Математичні моделі формування стоку мілкої води з поверхні водозбору. Рівняння процесів фільтрації рідини в грунті. Варіаційні формулювання задач. Напівдискретизація задачі в часі. Проекційні рівняння.Рекурентна схема. Дискретизація Гальоркіна за просторовими змінними

Розділ 3. Геоінформаційні технології для розробки системи екологічної безпеки регіону.

Розробка типової ГІС для моніторингу екологічної ситуації в регіоні. Структура даних. Програмне забезпечення. Збір даних. Умови використання, ведення та підтримка.



Моделювання динамічних систем.

Горизонт прогнозу. Детермінізм Лапласа. Русла та джокери. Проблеми моделювання динамічних систем, види моделей.

Консервативні системи. Принцип Даламбера. Гамільтонові системи. Інтегровні (оборотні системи). Неінтегровні еволюційні системи. Механіка суцільного середовища, модель матеріальної точки. Аксіоми суцільного середовища. Інтегральна модель, диференціальні закони збереження.

Термодинаміка. Внутрішня енергія. Ентропія, термодинамічна стріла часу. Лінійна нерівноважна термодинаміка, принцип Онзагера. Нелінійна нерівноважна термодинаміка.

Дискретні відображення, логістичне відображення. Діаграма Ламерея. Зв’язок між неперервними та дискретними моделями, січення Пуанкаре. Фрактали, фрактальні розмірності. Системи ітерованих функцій.

Генетичні алгоритми. Нейромережі. Клітинкові автомати, гра «життя», модель Вінера-Розенблюта.

Осцилятор Ван-дер-Поля. Автоколивні хімічні реакції. Реакція Білоусова-Жаботинського. Автокаталітичні реакції на поверхнях.

Фазовий простір. Особливі точки. Сепаратриси, гомоклінічні структури. Граничний цикл, автоколивні системи. Фазові переходи. Регулярні атрактори. Дивні атрактори як математична модель хаосу. Фрактальна природа дивних атракторів;

Пороговий характер якісних змін у природі. Статична та динамічна нестійкості. Моделі стійкості: Лагранжа, Пуассона, Ляпунова. Аналіз стійкості, показники Ляпунова, теорема Ляпунова, функції Ляпунова. Вихід системи на нестійкість. Режими із загостреннями. S, LS та HS режими.

Біфуркаційні діаграми. Типи біфуркацій, локальні та глобальні біфуркації. Біфуркація Андронова-Хопфа. «М’який» та «жорсткий» біфуркаційні режими, катастрофи. Біфуркації в нелінійних системах. Біфуркації у дискретних моделях (на прикладі логістичного відображення);

Активні середовища. Обмін ентропією. Роль віддаленості від рівноваги для процесів самоорганізації у системах. Біологічні об’єкти як дисипативні структури. Земля як дисипативна система;

Порядок і хаос. Перехід до хаосу. Сценарії Фейгенбаума, Помо-Манневілля, Рюеля-Таккенса. Керування хаосом. Практичні застосування синергетики: біологія, соціологія, медицина.

Динамічна теорія інформації. Вплив інформації на систему. Рецепція та генерація інформації. Рівні моделювання ДС: мікроскопічний, мезоскопічний, інформаційний.

Комп’ютерна графіка


Основні поняття та терміни. Етапи основного алгоритму обробки зображень.

Типи графічних пристроїв для вводу зображення. Сканери. Дігітайзери. Клавіатура. Аеро- та фотознімки. Космічні знімки.

Типи графічних пристроїв для візуалізації зображення. Растрові та векторні монітори. Принцип їх роботи.

Однорідні координати на площині та в просторі. Базові перетворення координат.

Афінна та перспективна геометрії. Аксонометричне та перспективне проектування.

Задання плоских та просторових кривих. Кубічні сплайни; параболічна інтерполяція; криві Без'є.

Апроксимація поверхонь в просторі. Білінійні поверхні. Лінійчаті поверхні. Лінійні поверхні Кунса. Бікубічна поверхня. Поверхні Без'є.

Алгоритми креслення відрізків. Цифровий диференційний аналізатор. Алгоритм Брезенхема.

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

Двовимірна відсіч. Алгоритм Сазерленда-Коена, що використовує розбиття відрізка. Узагальнення: відсіч двовимірного відрізка випуклим вікном. Алгоритм Кируса-Бека. Внутрішня та зовнішня відсіч. Вилучення невидимих ліній.


Про растеризацію і векторизацію. Принципи збереження зображень у растрових і векторних форматах. Опис найпоширеніших форматів графічних файлів. Їх переваги, недоліки та сфери застосування. Перетворення файлів з одного формату в інший. Імпорт та експорт зображень.



Основи інформаційнимх технологій та систем
Задачі аналізу даних. Архітектура сховища даних. OLAP та OLTP системи. Особливості. Критерії. Різновиди реалізацій сховищ даних. Потоки даних у сховищах. Мета дані.

Оперативне джерело даних. Очистка даних. Рівні очистки даних.

Багатовимірні дані. Міра. Вимір. Гіперкуб. Ієрархії вимірів. Операції над гіперкубом

Методи збереження даних у OLAP системах.



Класифікація задач аналізу даних. 1R-алгоритм. Метод Байєса. Алгоритм ID3. Алгоритм покриття. Метод опорних векторів. Алгоритм Apriory.Алгоритм k-means.
Основна література

  1. Paul Beynon-Davies, Systemy baz danych: Wydannie drugie. Wydawnictwo Naukowo-Techniczne. Warszawa. 2000.

  1. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1971.

  1. Акулич И. Л. Математическое программирование в примерах и задачах. - М.: ВШ, 1986.

  1. Б.В.Гнеденко. Курс теории вероятностей. М., 1969.

  1. Баженова И. Ю. . Visual FoxPro 6 - М.: Диалог-МИФИ, 1999. - 416 с.: ил.

  1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы М.: Мир, 1982.

  1. Бартіш М. Я., Дудзяний І. М. Дослідження операцій. Львів, 2007-2009, т. 1-3.

  1. Бартіш М.Я. Методи оптимізації. Теорія і алгоритми. Львів, Видавничий центр ЛНУ, 2006.

  1. В.Феллер. Введение в теорию вероятностей и ее приложения. т. т.1-2, М., 1984

  1. Вагнер Г. . Основы исследования операций. - М.: Мир, 1972, т. 1-3.

  1. Васильев Ф. П. Численные методы решения экстремальных задач. - М.: Наука, 1988.

  1. Воеводин В.В. Вычислительные основы линейной алгебры.-М:Наука,1977.

  1. Г.Крамер. Математические методы статистики. М., 1975.

  1. Гери Хансен, Джеймс Хансен. Базы даних: разработка и приложение: Пер. с англ. - М.: ЗАО "Издательство БИНОМ", 1999. - 704 с.: ил.

  1. Дейт К. Введение в системы баз даных, 6-е издание: Пер. с англ. - К.; М.; СПб.; Издательский дом "Вильямс", 2000. - 848с.: ил.

  1. Джексон Г. Проекторивание реляциoнных баз даных для использования с микро ЭВМ: : Пер. с англ. - М.: - Мир, 1991. - 252 с., ил.

  1. Е.С.Вентцель. Теория вероятностей. М., 1964.

  1. Єрьоміна Н. В. Проектування баз даних: Навч. Посібник.- К.: КНЕУ,1998. - 208с.

  1. Жук М. В., Щербина Ю. М. Збірник задач з методів оптимізації. - Львів: ЛДУ, 1997.

  1. Икрамов Х.Д. Вычислительные методы линейной алгебры (решение больших разреженных систем уравнений прямыми методами). - М:Знание, 1989.

  1. І.Д.Квіт. Випадкова змінна та випадковий процес. Львів, 1968.

  1. І.Муха, Л.Дяконюк Чисельні методи лінійної алгебри. - Львів:Вид.центр ЛНУ,2006. - 111с.

  1. Каратигин С. А., Тихонов А. Ф., Тихонова Л. Н. Visual FoxPro 6 - М.: ЗАО "Издательство БИНОМ", 1999. - 784 с.: ил.

  1. Карманов В. Г. Математическое программирование. - М.: Наука, 1986.

  1. Катренко А. В. Дослідження операцій. Львів: "Магнолія-2006", 2009.

  1. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

  1. Крушевский А. В. Теория игр. К.: Вища школа 1977.

  1. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. -Москва: Наука, 1981. -416 с.

  1. Мейер Д. Теория реляционных баз данных: Пер. с англ. - М.: - Мир, 1987. - 608 с., ил.

  1. Моудер Дж., Элмаграби (ред.). Исследование операций. - М.: Мир, 1981, т.1, 2.

  1. Нагао М., Катаяма Т., Уемура С., Структуры и базы даных: Пер. с япон. - М.: Мир, 1986.- 197с., ил.

  1. Озкарахан Э. Машины баз даных иуправление базами даных: Пер. с англ. - М.: Мир. 1989. - 696 с., ил.

  1. П.С.Сеньо. Теорія ймовірностей та математична статистика. К., 2007, 556 с.

  1. Пшеничный Б. Н., Данилин Ю. М. Численные методы в экстремальных задачах. - М.: Наука, 1975.

  1. Пшеничный Б.Н. Метод линеаризации. - М.: Наука, 1983.

  1. Пэддок Р., Петерсен Дж., Тэлмейдж Р., Ренфт Э. Visual FoxPro 6 . Разработка корпоративных приложений: Пер. с англ .- М.: ДМК, 1999. - 592 с.: ил.

  1. Р.Тьюарсон Разреженные матрицы. - М:Мир,1977. -185с.

  1. Савула Я.Г. Числовий аналіз задач математичної фізики варіаційними методами. - Львів: ЛНУ ім.І.Франка, 2004. -221с.

  1. Савула Я.Г., Шинкаренко Г.А., Вовк В.Н. Некоторые приложения метода конечных элементов. -Львiв: Вища школа, 1981. - 86 с.

  1. Сосински Бари. Разработка приложений в среде Visual FoxPro 5 .: Пер. с англ .- К.: Диалектика, 1997. - 448 с.: ил.

  1. Таха Х. Введение в исследование операций - М.: "Вильямс", 2001.

  1. Уилкинсон Дж. Алгебраическая проблема собственных значений.-М:Наука,1970. - 564с.

  1. Уилкинсон Дж., Райнш Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра.-М.:Машиностроение, 1976. -381с.

  1. Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1974.

  1. Цегелик Г. Г. Лінійне програмування. - Львів: Світ, 1995.

  1. Цегелик Г. Г. Лінійне програмування. - Львів: Світ, 1995.

  1. Цегелик Г.Г. Наближені методи розв'язування крайцових задач для диференціальних рівнянь з частинними похідними та інтегральних рівнянь. - Львів: Вид. ЛНУ імені Івана Франка, 2008. - 140 с.

  1. Цегелик Г.Г. Чисельні методи. - Львів: Вид. ЛНУ імені Івана Франка, 2004. - 408 с.

  1. Шинкаренко Г.А. Проекцiйно-сiтковi схеми розв'язування початково-крайових задач. - Київ: НМКВО, 1991. -88 с.

  1. Эльсгольц Л. Э. Дифференциальные уравнения и вариационное исчисление. - М.: Наука, 1969.

  1. Ю.В. Капітонова, С.Л. Кривий, О.А. Летичевський, М.К. Печурін. Основи дискретної математики. К., Наукова думка, 2002.

  1. Ю.В.Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика (у серії "Інформатика"). Київ, Видавнича група BHV, 2006, 2007.

  1. Ю.В.Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика (у серії "Комп'ютинґ"). Львів, Магнолія-2006, 2009 (1-е видання), 2010 (2-е видання).

  1. Ю.В.Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика. Львів, Магнолія Плюс, 2005, 2006 (1-е видання), 2007 (2-е видання, виправлене й доповнене), 2008 (3-є видання, виправлене й доповнене).

  2. XHTML 1.0: Розширювана мова гіпертексової розмітки. Переформулювання HTML 4 в XML 1.0. – Рекомендації W3C REC-xhtml1-20000126

  3. Горлач В. Основи комп’ютерних мереж. Електронний підручник.

  4. Баженов В.А., Венгерський П.С., Горлач В.М. та ін. Інформатика. Комп'ютерна техніка. Комп'ютерні технології: Підручник. 3-тє вид.-К.: Каравела, 2011.- 592 c.

  5. Каскадні таблиці стилів другого рівня. Специфікація CSS2 – Рекомендації W3C REC-CSS2-19980512

  6. Розширювана мова розмітки XML 1.0. – Рекомендації W3C REC-xml-20001006

  7. Специфікація HTML 4.01. – Рекомендації W3C REC-html401-19991224

  8. Стоян В.А. Моделювання та ідентифікація динаміки систем з розподіленими параметрами. – К.: Київський у-т, 2008. – 201с.

  9. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. – М.: Физматиздат, 2005. – 320с.

  10. Іванків К.С., Щербатий М.В. Математичне моделювання біологічних та еколого-економічних процесів. – Львів: ЛНУ ім. І.Франка, 2005. – 154 с.

  11. Ляшенко І.М., Мукоєд А.П. Моделювання біологічних та екологічних процесів. - К.: Київський у-т, 2002. – 340 с.

  12. Сергиенко И.В., Скопецкий В.В., Дейнека В.С. Математическое моделирование и исследование процессов в неоднородных средах. – Киев: Наук. Думка, 1991. – 432 с.

  13. Марчук Г.И. Математические моделирование в проблеме охраны окружающей среды. – Москва: Наука, 1980. – 320 с.

  14. Лаврик В.І. Методи математичного моделювання в екології. – Київ: Вид. дім «КМ Академія», 2002. – 134 с.

  15. Мокін В.Б., Горячев Г.В. Оптимальний вибір СУБД та геоінформаційних пакетів для систем екологічного моніторингу // Інформаційні технології та комп’ютерна інженерія. – 2005. – № 2. – С. 61 – 67. 

  16. Роджерc Д., Адамс Дж. Математические основы машинной графики.- М.: Машиностроение; 1980.

  17. Роджерc Д. Алгоритмические основы машинной графики.- М.:Мир; 1989.

  18. 3. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение.- М.: Мир; 1989.

  19. 4.Шишкин Е.В., Боресков А.В. Компьтерная графика. Динамика, реалистические изображения.-М.: «Диалог-МИФИ». 1995.- 288с.

  20. 5.Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC. –М.: УНИТЕХ, 1992. – 156 с.

Затверджено Вченою радою факультету прикладної математики та інформатики (протокол № 27 від 12 лютого 2014 року)


Декан факультету

прикладної математики проф. Я. Г. Савула

та інформатики









База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

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