1. Вступ. Основні поняття та методологія до історія розвитку та використання методів дослідження операцій (ДО). Наукова суть до

Вид материала

Документы

Содержание II. Об’єктно-орієнтоване програмування III. Програмування IV. Комп'ютери і мікропроцесорні системи V. Основи системного аналізу проектування комп'ютерних інформаційних технологій

Подобный материал:

• Міністерство освіти, науки, молоді та спорту україни мукачівський професійний ліцей, 2673.82kb.
• Бази даних I. Вступ. Основні поняття, 142.32kb.
• План: Вступ Характеристика методів досліждення. Загальна класифікація методів, 122.96kb.
• Вступ Поняття "соціалізація", 532.85kb.
• Вступ Поняття "соціалізація", 661.61kb.
• Теми контрольних робіт для студентів заочної форми навчання усіх спеціальностей з дисципліни, 36.24kb.
• Програма Комплексного вступного іспиту на окр «Спеціаліст», 814.3kb.
• Інститут телекомунікацій, радіоелектроніки І електронної техніки, 345.74kb.
• Програма комплексного вступного іспиту на окр «Спеціаліст» за спеціальністю «Правознавство», 84.74kb.
• Львівський державний університет фізичної культури, 34.02kb.

Напрям: Компютерні науки

Спеціальність: Інформаційні управляючі системи
та технології (0302)


I. Математичні методи дослідження операцій


1. Вступ. Основні поняття та методологія ДО

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


2. Класичні задачі лінійного програмування (ЛП)

Поняття про задачу математичного програмування (МП). Загальна постановка та класифікація задач МП, поняття складності алгоритмів розв’язування задач МП. Побудова математичних моделей задач ДО. Лінійні моделі та зв’язані з ними спрощення дійсності: пропорційність і адитивність. Загальна канонічна форма задачі ЛП. Графічне розв’язування задач ЛП. Поняття про основні задачі аналізу лінійних моделей на чутливість: статус та допустимі межі зміни ресурсів, цінність ресурсів, чутливість функції мети. Базисні розв’язки задачі ЛП. Основні теореми ЛП. Алгоритм симплекс-методу та його таблична форма. Умови оптимальності та допустимості. Особливі випадки симплекс-методу. Методи знаходження початкового базису: двоетапний та метод великих штрафів. Двоїстість у задачах ЛП. Поняття прямої та двоїстої задач ЛП. Основні теореми двоїстості. Економічна інтерпретація двоїстості. Поняття про методи розв’язування задач ЛП великої розмірності та особливої структури. Методи декомпозиції, розріджені матриці, особливості реалізації алгоритмів. Модель транспортної задачі ЛП. Приклади транспортних задач (ТЗ). Методи побудови опорного плану ТЗ: північно-західного кута, мінімального елементу, евристичний метод Фойгеля. Методи знаходження оптимального плану ТЗ (метод потенціалів і розподільчий). Теореми про потенціали. Транспортні задачі з особливостями в формулюванні, їх виродженість.


3. Задачі на мережах

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


4. Задачі цілочисельного програмування

Особливості цілочисельних задач. Цілочисельні моделі практичних задач. Загальна характеристика основних груп методів розв’язування цілочисельних задач: відсічень, комбінаторних, евристичних. Принципи побудови евристичних алгоритмів. Основні ідеї методів відсічень. Метод Гоморі, його недоліки. Метод вектора спаду. Схема методу гілок і границь та її основні структурні елементи: стратегії розгалуження, границі та їх властивості, стратегія відтинання вузлів. Проблеми представлення цілочисельних задач і процесу їх розв’язування в ЕОМ.


5. Теорія ігор

Основні поняття теорії ігор: учасники гри, стратегії, виграші. Класифікація ігор за ознаками: кількість гравців, потужність множини стратегій; характер взаємодії гравців, розмір виграшів, вид функції виграшів, кількість і характер ходів, інформованість. Загальна характеристика методів розв’язування ігор. Матричні ігри двох осіб з нульовою сумою. Означення, приклади. Розв’язки в чистих стратегіях. Нижня й верхня ціна гри. Сідлова точка та чиста ціна гри. Оптимальні чисті стратегії. Теореми про ціну гри і максимін. Оптимальні змішані стратегії та їхні властивості. Ціна гри в змішаних стратегіях. Основна теорема матричних ігор. Геометричне розв’язування ігор розміром 2x2, 2xn, mx2. Поняття про кооперативні ігри. Біматричні ігри та положення рівноваги в біматричних іграх. Позиційні ігри. Нормальна форма позиційної гри. Графічна форма позиційної гри. Позиційні ігри з повною й неповною інформацією та обмеженою пам’яттю. Поняття про антагоністичні ігри, ігри з функцією виграшу, сепарабельні ігри.


6. Нелінійне програмування

Задачі нелінійного програмування та основні труднощі їх розв’язування. Класичний метод оптимізації та метод множників Лагранжа. Метод множників Лагранжа та теорія двоїстості. Необхідні й достатні умови існування сідлової точки. Теорема Куна – Такера. Квадратичне програмування. Метод Вольфа. Геометричне програмування. Задачі опуклого програмування. Прямі методи 1-мірного числового пошуку: дихотомії, золотого перетину, Фібоначчі. Непрямі числові методи пошуку безумовного екстремуму функцій: градієнтні, спряжених напрямків, змінної метрики. Числові методи штрафних функцій і бар’єрних поверхонь у задачах умовної оптимізації функцій.


7. Задачі варіаційного числення

Найпростіша задача варіаційного числення. Формалізація, множина допустимих розв’язків, коректність задач оптимізації. Рівняння Ейлера-Пуасона. Багатокритерійні оптимізаційні задачі. Задачі оптимального управління.


8. Динамічне програмування

Основні поняття динамічного програмування. Загальна постановка задачі динамічного програмування та її геометрична інтерпретація. Принципи оптимальності Белмана та “прокляття розмірності”. Найпростіші економічні задачі, які розв’язуються за допомогою методу динамічного програмування. Рекурентні співвідношення в задачах динамічного програмування. Задачі з адитивною та мультиплікативною функцією мети. Метод функціональних рівнянь. Багатовимірні задачі динамічної оптимізації. Поняття про стохастичні задачі динамічного програмування.


9. Моделі управління запасами

Загальна постановка задачі управління запасами. Класифікація моделей управління запасами. Загальна характеристика методів розв’язування задач управління запасами. Детерміновані моделі управління запасами: однопродуктова статична модель; однопродуктова модель з розривами цін; багатопродуктова статична модель з обмеженням на ємність складів. Однопродуктова модель динамічного управління за скінченну кількість періодів; постійні та спадні граничні витрати; календарне планування виробництва на скінченну кількість етапів.


10. Задачі побудови розкладів

Класифікація задач побудови розкладів. Критерій оцінки якості розкладів. Складання розкладів для одного верстату. Перестановочні розклади. Евристичні методи побудови розкладів. Правила впорядкування. Впорядкування при наявності обмежень на можливі варіанти розкладів. Складання розкладів для паралельних верстатів. Розклади для систем конвеєрного типу. Алгоритм Джонсона для конвеєрної системи двох верстатів. Методи розв’язування задач побудови розкладів для складання конвеєрних систем.


II. Об’єктно-орієнтоване програмування


1. Основні поняття та методологія ООП

Основні поняття ООП. Природа класу та об’єкта, взаємозв’язок між ними.


2. Класи та обєкти

Визначення та ідентифікація класів та об’єктів. Конструктор деструктор. Типи методів. Поля методи властивості.


3. Основні принципи ООП

Абстракція. Інкапсуляція. Наслідування. Поліморфізм.


4. Характеристика правил повторного використання коду

Типи ієрархій. Правила наслідування. Перевантаження. Заміщення. Уточнення.


5. Стандартні класи

Ієрархія класів. Бібліотека візуальних компонент.


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


1. Загальна характеристика програмного забезпечення комп’ютерів

Класифікація програмного забезпечення. Системні та прикладні програми. Характеристика мов програмування за рівнями. Системи програмування. Етапи виконання програми. Внутрішні форми збереження числових і символьних даних. Основні риси мови програмування С. Структура С-програми.


2. Базові елементи мови С

Лексеми. Типи даних. Директиви препроцесору. Бібліотечні функції.


3. Вирази та операції

Арифметичні та порозрядні операції. Операції порівняння та логічні операції. Операції присвоєння, комбіновані присвоєння. Умовна операція та операція розміру sizeof. Порядок виконання операцій. Узгодження типів операндів у виразах.


4. Оператори мови С

Оператори-вирази: присвоєння, виклик функції, пустий оператор. Умовні оператори: if, switch. Оператори циклу: for, while, do-while. Оператори переходу: goto, break, continue, return.


5. Вказівники та масиви

Оголошення вказівників, звертання до даних через вказівники. Адресна арифметика. Оголошення та ініціалізація масивів. Звертання до елементів масиву через індекси і через вказівники. Багатовимірні масиви


6. Символьні рядки

Оголошення та ініціалізація символьних рядків. Звертання до елементів символьних рядків. Введення-виведення символів і символьних рядків. Бібліотечні функції для роботи із символами та символьними рядками: функції функції класифікації і перетворення символів, функції операцій над символьними рядками, функції перетворення рядків символів у числа та зворотніх перетворень. Масиви символьних рядків і масиви вказівників на символи.


7. Структури та об’єднання

Структури: оголошення, ініціалізація, присвоєння. Звертання до полів структури. Об’єднання. Декларація перейменування типів typedef.


8. Введення-виведення, обмін даними з файлами

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


9. Функції

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


10. Робота з даними в динамічній пам’яті

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


IV. Комп'ютери і мікропроцесорні системи


1. Архітектурні принципи побудови обчислювальних засобів

Типи обчислювальних засобів і комп’ютерів. Базові архітектури комп’ютерів і мікропроцесорних систем. Експлуатаційні характеристики комп’ютерних засобів. Шляхи підвищення продуктивності обчислювальних засобів.


2. Системи числення

Властивості систем числення. Непозиційні системи числення. Арифметичні операції в системі остач.


3. Архітектура пам’яті комп’ютерів

Типи запам’ятовувальних пристроїв. Постійні запам’ятовувальні пристрої. Запам’ятовувальні пристрої з довільним звертанням. Запам’ятовувальні пристрої для оперативної роботи з основною пам’яттю та архівного збереження даних.


4. Паралельна обробка даних

Принципи розпаралелювання. Конвеєризація обчислень. Паралельні архітектури комп’ютерів.


5. Принципи побудови мікропроцесорних систем

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


6. Основи програмування мікропроцесорних систем

Системи команд однокристальних мікропроцесорів. Способи адресації. Програмування спеціалізованих ВІС. Мова Асемблера.


7. Архітектура нейрокомп’ютерів

Загальні засади, що лежать в основі нейрокомп’ютерів. Базові нейропарадигми. Основи застосування нейрокомп’ютерів.


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


1. Принципи системного аналізу

Класифікація і аналіз. Принципи об’єднання в класи. Ознаки та властивості систем. Параметри системи та елементів. Мета створення системи. Поняття структури системи. Функції елементів системи.


2. Системи та об’єкти

Процес функціонування. Режим функціонування. Поняття стану системи. Алгоритм функціонування. Алгоритм управління. Критерії управління системою. Структурна схема системи.


3. Системна філософія

Мета функціонування. Ефективність функціонування систем. Типи систем. Інформаційні потоки. Події в системах. Класифікація подій. Взаємодія між подіями. Системи без зворотного зв’язку.


4. Елементи систем

Перехід від безперервних параметрів до дискретних. Система як об’єднання та композиція підсистем. Класифікація підсистем. Взаємодія підсистем. Критичні елементи системи.


5. Класифікація систем

Централізовані системи. Децентралізовані системи. Розподілені системи. Змішані системи.


6. Складність системи

Структурні одиниці. Функціональні елементи. Функціональні схеми. Методи дослідження систем. Стійкість систем в прямуванні до мети. Критерії повноти системи.


7. Властивості систем

Алгебраїчні системи. Мови опису систем. Принципи та стратегії управління. Критичні і нормальні стани. Поняття еквівалентності систем. Подібність систем.


8. Функції елементів і системи

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


9. Взаємодія елементів і управління

Розвиток систем шляхом вводу нових зв’язків. Розвиток систем за рахунок зміни їх структури. Успадкування властивостей системи з прототипу. Розподілене і централізоване управління.


10. Суперечки в системах

Методи виявлення помилок в системах. Виявлення вузьких місць. Мінімально несумісна підмножина. Максимально сумісна підмножина. Перехід від мінімально несумісних підмножин до максимально сумісних. Використання модальної логіки для опису систем.

11. Взаємодія систем

Тенденції розвитку. Закономірності в системах. Поняття причинності в складних системах. Зв’язок моделей функціонування з теорією ігор. Методи розв’язку ігрових ситуацій.


12. Паралельне управління

Поняття “порочного кола”. Поняття “чорного ящика”. Циклічні процеси в системах. Запізнення регулюючих сигналів. Автоколивання в системах.


13. Ситуаційне управління

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


14. Моделі систем

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


15. Недетермінізм в системних процесах

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