Мiнiстерство освiти і науки України
Національний аерокосмічний університет ім. М.Є. Жуковського
“Харківський авіаційний інститут”
ЗАТВЕРДЖУЮ
Проректор ХАІ з НПР
______________ В.М. Павленко
“25” лютого 2015 р.
Фахове вступне випробування по спеціальності:
7.04030203, 8.04030203 Соціальна інформатика
Програму розроблено і затверджено на кафедрі інформатики,
протокол № 6 від “ 22 ” 01 2015 р.
Завідувач кафедрою, к. ф.-м. н., доцент О.В. Карташов
Програму погоджено НМК факультету систем управління літальних апаратів
Голова НМК факультету, к.т.н., доцент А. Савельєв
Харків 2015
Вступ
Фахове вступне випробування по спеціальностям 7.04030101, 8.04030101 Прикладна математика, 7.04030103, 8.04030103 Комп'ютерне та математичне моделювання складається з п’яти дисциплін:
-
«Дискретна математика»,
-
«Алгоритми і структури даних»,
-
«Методи обчислень»,
-
«Методи оптимізації та дослідження операцій»,
-
«Бази даних та інформаційні системи».
Згідно п. 5.2 Правил прийому до Національного аерокосмічного університету ім.. М.Є. Жуковського «Харківський авіаційний інститут» у 2015 р. результат фахового випробування визначається за 100-бальною шкалою.
Програма з дисципліни «Дискретна математика»
1. Множини, відношення, функції.
Предмет курсу. Основні поняття дискретної математики; її місце в загальному курсі математики. Елементи і множини. Способи завдання множин в ЭОМ в вигляді булевих масивів. Дискретні множини. Об’єднання, перетин, доповнення множин. Використання включення-виключення для рішения теоретико-числових задач. Завдання множин списками. Операції над множиними. Завдання множин в ЕОМ у вигляді масиву величин булевого типу. Перелік елементів множин. Перелік підмножин з допомогою алгоритму Грея. Відношення порядку. Доповнення часткового порядку на множині до лінійного. Уявлення множин списками.
2. Алгоритми сортування одновимірних масивів.
Класифікація алгоритмів сортування. Алгоритми злиття. Алгоритм Heap-sort. Аналіз, структура програми. Швидке (двоїчне) сортування. Аналіз, застосування. Способи сортування за лінійний час. Реалізація на ЕОМ алгоритмів впорядкування множин злиттям списків множин. Сортування бази даних швидкими методами. Швидке (двоїчне) сортування. Сортування за лінійний час.
3. Елементи комбінаторики.
Група підстановок. Транспозиції, інверсії; парність, непарність. Спеціальні засоби генерування підстановок. Перестановки. Реалізація на ЕОМ. Розміщення, сполуки. Рлзв’язання найпростіших оптимізаційних задач . Біноміальні коефіцієти. Їхні вляастивості; дослідження з застосуванням методів математичного аналізу. Числа Стірлінга, Белла. Призводящі функції. Біноміальні коефіцієнти. Їхні властивості; дослідження з використанням методів математичного анализу. Біном Ньютона. Пошук призводящих функцій. Застосування призводящих функцій для розв’язання комбінаторних задач. Методи програмування для генерування комбінаторних конфігурацій. Генерувания розміщень. Задача комівояжера. Генерувания сполук, сполук з повтореннями
4. Алгебраїчні структури.
Операції і алгебри. Класифікація властивостей операцій. Морфізми. Алгебри з однією операцією. Полугрупи, моноїди, групи. Пошук циклів в підстановках. Побудова фактор-груп за циклічними підгрупами. Цикли. Програмна реалізація пошуку циклів. Елементи „довгої арифметики”. Дії «довгої арифметики».
5. Дерева.
Дерева, як вид графів. Основні властивості дерев. Ориєнтовані, впорядковані і бінарні дерева. Дерева. Основні властивості дерев. Ориєтировані, упорядкованні і бінарні дерева. Уявлення графів в ЕОМ. Уявлення вільних, орієнтованих і упорядкованих дерев. Обхід бінарних дерев. Уявлення графів в ЕОМ. Уявлення вільних, ориєнтованих і упорядкованих дерев. Програмування обходу бінарних дерев. Дерева сортування. Записи, ключі. Способи реалізації асоціативної пам’яті. Алгоритм двоїчного пошуку. Алгоритм пошуку в дереві сортування. Алгоритми вилучення і вставки в дерево сортування. Алгоритм симетричного обходу бінарного дерева з використанням стеку. Вирівненні дерева. Збалансовані дерева.
6. Кодування і криптографія
Загальна постановка задачі кодування і декодування. Алфавитне кодування. Алгоритми вилучення і вставки в дерево сортування. Префікс і постфікс слова. Розділимі схеми. Префіксні схемию. Вирівнені дерева. Збалансовані дерева. Кодування з мінімальною надлишковістю. Мінімізація довжини коду повідомлення. Ціна кодування. Алгоритм Фано. Найпростіші методи кодування. Алфавітне кодування. Оптимальне кодування. Побудова двоїчного дерева декодування. Ціна кодування. Алгоритм Фано. Програмна реалізація алгоритму Фано і рекурсивного алгоритму Хафмена. Ціна кодування. Алгоритм Фано. Поміхостійке кодування. Класіфікація помилок. Кодова відстань. Код Хемінга. Програмна реалізація алгоритму Фано. Стиск даних. Стиск тексту. Побудова словника. Адаптивний стиск. Поміхостійке кодування. Код Хемінга; програмування. Структура дерева для побудови словника. Приклад. Шифрування з допомогою випадкових чисел. Постановка задачі шифрування. Шифрування з допомогою випадкових чисел. Криптостійкість. Програмна реалізація шифрування Модулярна арифметика. Теорема Ейлера; мала теорема Ферма. Теорема про залишки. Модулярна арифметика. Теорема про залишки. Шифрування з відкритим ключем. Криптосистема RSA (Рівест, Шамір, Адлеман). Цифровий підпис.
Література
1. А.Ю.Соколов, М.Л.Угрюмов, В.А.Халтурин, Ю.К.Чернышев. Применение ЭВМ для решения задач дискретной математики, Харьков, «ХАИ», 2003 – 78 с.
2. Ю.К.Чернышев, М.А.Слепичева . Вычислительные задачи дискретной математики, Харьков, «ХАИ», 2003 – 72 с.
3. Ф.А.Новиков. Дискретная математика для программистов. С-Пб.: Питер, 2000. – 304 с.
4. В.Липский. Комбинаторика для программистов. М.: Мир, 1988.- 212 с.
Програма з дисципліни "Алгоритми і структури даних"
1. Сложность алгоритмов.
Разработка алгоритмов. Тестирование, аналитическое доказательство правильности алгоритмов, эффективность. Оценка сложности алгоритмов в среднем, лучшем и худшем случаях. Нотации О, Тета и Омега.
2. Алгоритмы и рекурсия.
Основные методы построения рекурсивных алгоритмов. Оценка сложности рекурсивных алгоритмов. Решение рекуррентных отношений. Метод подстановки. Метод итераций. Теорема о рекуррентных оценках.
3. Структуры представления данных в ЭВМ
Концепция АТД (абстрактных типов данных). Представление структуры данных в виде АТД. Классификация структур данных. Линейные структуры данных: их последовательное и связанное представление, операции с ними. Нелинейные структуры данных: графы, деревья. Основные понятия и определения.
4.Графы и их представление в ЭВМ
Представление с помощью матрицы смежности, матрицы инцидентности, списков смежности, списков дуг. Алгоритмы, оперирующие со структурами типа граф: алгоритм выявления всех маршрутов заданной длины и цепей, алгоритм нахождения кратчайших цепей между заданными вершинами, алгоритм выявления всех простых цепей и циклов.
5. Деревья. Основные понятия и определения
Ориентированные. Упорядоченные. Бинарные. Сбалансированные. Представление деревьев в памяти ЭВМ. Последовательное и связанное размещение элементов. Конструирование оптимальных деревьев. Операции над деревьями. Обход дерева, упорядочивание, поиск, включение/ удаление вершины.
6. Алгоритмы поиска
Исчерпывающий поиск: поиск в глубину, поиск в ширину, перебор с возвратом. Быстрый поиск: бинарный и последовательный поиски в массивах, хеширование. Выбор в линейных списках. Использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска.
7. Хеширование.
Хеш-таблицы и хеш-функции. Основные методы вычисления хеш-функций (деление с остатком, умножение, комбинированный метод). Разрешение коллизий. Хеширование с цепочками. Хеширование открытой адресацией. Анализ эффективности алгоритмов хеширования, выбор хеш-функций.
8. Алгоритмы и их классификация.
Жадные алгоритмы и теория матроидов. Основные характеристики и свойства (принцип жадного выбора, оптимальность подзадач). Задача о выборе процессов. Задача о расписании для заказов с равной длительности с единственным исполнителем сроками и штрафами. Динамическое программирование. Оптимальная триангуляция. NP-сложные и труднорешаемые задачи. Алгоритмы для NP-сложных задач.
Література
Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. М.:МЦНМО, 2000 - 956 с.
Андерсон, Джеймс А. Дискретная математика и комбинаторика. М.: Вильямс, 2004. – 960 с.
Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. М.: изд. дом "Вильямс". – 2000. – 384 с.
Уильям Топп, Уильям Форд. Структуры данных в С++. М.: Бином. – 2000. – 861 с.
Райли Д. Абстракция и структуры данных: Вводный курс: Пер.с англ. М.: Мир, 1993. - 752 с.
-
Каррано Ф.М., Причард Дж.Дж. Абстракция данных и решение задач на С++. М.: Издательский дом «Вильямс», 2001. – 848 с.
Програма з дисципліни "Методи обчислень"
1.Математичне моделювання. Основи теорії похибок .
Предмет курсу. Особливості побудови математичних моделей. Способи опису: детермінантні моделі, стохастичні моделі.. Кількість реалізацій і точність обчислень. Похибки обчислень, алгоритмів, математичних моделей. Абсолютна і відносна похибки. Поширення похибок.
2. Чисельні методи рішення нелінійних рівнянь.
Методи відділення коренів. Метод дихотомії. Метод хорд. Метод дотичних. Комбінований метод. Збіжність методів. Визначення похибки обчислень. Наближене рішення рівнянь методом ітерацій (послідовних наближень). Теорема про збіжність методу.
3. Чисельні методи лінійної алгебри.
Рішення системи лінійних алгебраїчних рівнянь (СЛАР) методом Гаусса. Схема єдиного розподілу. Прямій і зворотний хід. Обчислення визначника матриці методом Гаусса. Знаходження зворотної матриці. Рішення СЛАР методом прогону. Ітераційні методи рішення СЛАР. Визначення і види норм матриці. Зведення системи до виду, зручному для ітерацій. Метод простої ітерації (Якобі). Теорема про збіжність методу. Метод Гаусса-Зейделя. Теорема про збіжність. Порівняння методів. Рішення систем рівнянь і нерівностей у середі пакета MathCAD
4. Наближення функції.
Постановка задачі інтерполяції та екстраполяції. Побудова інтерполяційного поліному Лагранжа. Приклади використання. Похибка інтерполяційної формули Лагранжа. Кінцеві різниці та їх властивості. Вивід першої та другої інтерполяційної формули Ньютона. Залишкові члени інтерполяційних формул. Центральні різниці.Перша та друга інтерполяційні формули Гаусса. Наближене диференціювання функцій ,заданих як таблиця. Оцінка похибки. Зворотна інтерполяція. Метод найменших квадратів. Постановка задачі. Загальний випадок. Степеной базис. Випадок лінійних функцій. Апроксимація табличних даних за допомогою прямої та параболи. Постановка задачі. Загальний вигляд кубічного сплайну. Побудова кубічного сплайну.Вди сплайнів. Вирішення задачі знаходження коефіцієнтів кубічного сплайну за допомогою метода прогону.
5. Наближене обчислення інтегралів.
Постановка задачі обчислення інтегралу. Найпростіші квадратурні формули – формули лівих та правих прямокутників . Геометрична інтерпретація. Погрішність формул. Формула середніх прямокутників. Геометрична інтерпретація. Похибка формули середніх прямокутників. Загальна ідея квадратурних формул. Вивід загального виду квадратурної формули - формула Ньютона-Котеса. Формули прямокутників. Формула трапецій. Формула Сімпсона(формула парабол). Геометричний зміст. Залишковий член формули Симпсона Похибки квадратурних формул. Квадратурна формула Чебишева. Недоліки квадратурної формули Чебишева. Особливості використання. Квадратурна формула Гаусса. Вид поліномів Лежандра. Геометрична інтерпрітація. Властивості поліномів Лежандра. Вивід формули Гаусса. Особливості використання. Приклади.
6. Чисельне рішення лінійних інтегральних рівнянь. Інтегральні рівняння Фредгольма, Вольтерра. Постановка задачі обчислення інтегральних рівнянь. Види інтегральних рівнянь. Рівняння Фредгольма першого та другого роду. Рівняння Вольтера. Теорія Фредгольма основні положення. Заміна інтегрального рівняння системою лінійних алгебраїчних рівнянь – метод кінцевих сум. Приклади. Визначення виродженого ядра. Загальна ідея вирішення інтегральних рівнянь Фредгольма II роду з виродженим ядром. Основні положення теорії Фредгольма. Методи заміни ядра на вироджене. Приклади. Метод послідовних наближень рішення інтегральних рівнянь Фредгольма II роду (метод малого параметра).
7. Задача Коши, методи рішення диференціальних рівнянь, систем диференціальних рівнянь
Постановка задачі Коши. Однокрокові методи. Метод Ейлера. Уточнений метод Ейлера. Метод Рунге-Кутта. Методика з'ясування порядку похибки наближеного методу рішення задачі Коши. Геометрична інтерпретація однокрокових методів. Багатокрокові методи рішення диференціальних рівнянь. Метод Мілна. Загальна похибка методу Мілна.Метод Адамса. Загальна похибка методу Адамса. Застосування методу Мілна й Адамса. Рішення систем звичайних диференціальних рівнянь I порядку Метод Ейлера. Рішення задачі Коши для звичайних диференціальних рівнянь порядку вище першого. Заміна похідних функцій за допомогою кінцевих різностей. Метод прогонки. Оцінка похибки. Стійкість та сходимість різностних схем.
Література
Демидович Б.П., Марон И.А. Основи обчислювальної математики. М., 1963.
Турчак Л.І. Основи чисельних методів: Нав. посібник. М.: Наука, Гол.ред.фіз.-мат.літ., 1987.- 320c.
Михайленко С.В. Чисельні методи: Навчальна допомога з курсу "Прикладна та обчислювальна математика". Харків : ХАІ ім. М.Є.Жуковського, 1978.-126c.
Михайленко С.В. Прикладна математика: Лабораторний практикум з чисельних методів. Харків: ХАІ ім. М. Є. Жуковського,1992.-102c.
Програма з дисципліни "Методи оптимізації та дослідження операцій "
Задачі лінійного програмування.
Різні постановки задачі лінійного програмування, їх еквівалентність, та зведення до задачі в канонічній постановці. Графічний метод розв’язання задачі. Системи лінійних рівнянь: канонічний вид, загальні та часткові розв’язки, базові часткові розв’язки. Виключення Жордана-Гауса та його використання для розв’язання систем лінійних рівнянь. Опорні розв’язки задачі лінійного програмування. Основи симплекс-методу для покращення опорного розв’язку: приведені оцінки, умови оптимальності, умови необмеженого зменшення функції мети на області припустимих розв’язків, правила обирання опорних строки та стовпця при переході до нового опорного розв’язку. Алгоритм симплекс-методу. Використання симплекс методу для пошуку початкового опорного розв’язку. Пара двоїстих задач лінійного програмування. Правила переходу до двоїстої задачі. Перша та друга теореми двоїстості. Використання розв’язку двоїстої задачі для пошуку розв’язку вихідної задачі. Геометрична інтерпретація симплекс-методу та його обчислювальна складність. Економічна інтерпретація пари симетричних двоїстих задач. Подальший розвиток методів розв’язання задач лінійного програмування. Транспортна задача лінійного програмування. Постановка. Властивості та особливості цієї задачі лінійного програмування. Транспортна таблиця. Методи побудови початкового опорного розв’язку: північно-західного кута, мінімальної вартості, подвійного уподобання, метод Фогеля. Цикли в транспортній таблиці та їхні властивості. Алгоритм переходу від одного опорного розв’язку до іншого. Розподільчій метод і метод потенціалів для покращення опорного розв’язку транспортної задачі.
Одновимірна нелінійна оптимізація.
Постановка задачі. Необхідні та достатні умови оптимальності. Методи розв’язання, що використовують похідні: Ньютона-Рафсона, хорд, дихотомії з використанням похідних. Унімодальні функції. Використання їх властивостей для розв’язання задач оптимізаціїї. Методи оптимізації унімодальних функцій: рівномірного пошуку, дихотомії без використання похідних, Фібоначі, золотого розчину. Метод квадратичної інтерполяції.
3. Елементи опуклого аналізу.
Опуклі множини та їх основні властивості. Проекція точки на множину. Теореми відокремлення. Конуси. Теорема Фаркаша. Геометричний зміст теореми Фаркаша. Опуклі функції. Визначення та властивості. Узагальнення опуклої функції.
4. Нелінійна безумовна оптимізація.
Постановка задачі. Необхідні та достатні умови оптимальності. Методи, що використовують градієнт. Метод найшвидкішого спуску. Покращений метод найшвидкішого спуску. Загальні принципи методів спряжених напрямків. Метод спряженого градиєнту для опуклої квадратичної функції. Метод Флетчера – Рівза. Метод Ньютона. Модифіковані методи Ньютона: із змінним кроком, з корекцією матриці Гессе, з використанням кінцево-різницевої апроксимації матриці Гесе. Загальні принципи квазіньютонівських методів. Квазіньютонівські методи: з поправочною матрицею ранга 1. Методи, що не використовують градієнт: циклічного покоординатного спуску, Хука и Дживса с дискретным кроком, Нелдера – Міда (деформованого багатокутника).
5. Нелінійна умовна оптимізація.
Постановка задачі. Припустимі напрямки. Конус припустимих напрямків. Необхідна умова допустимого напрямку. Теорема Куна –Такера для задачі з обмеженнями – нерівностями та для задачі зі змішаними обмеженнями. Геометричний зміст теореми Куна –Такера. Достатні умови екстремуму для задачі зі змішаними обмеженнями. Умови экстремуму задачі с псевдоувігнутою функцією мети. Пряме використання теореми Куна –Такера для пошуку екстремуму. Метод штрафних функцій. Метод бар’єрів. Метод можливих напрямків. Метод проекції градієнту: обирання напряму руху, обирання довжини кроку, процедури зміни активного набору, модельна схема.
6. Дискретна оптимізація.
Постановка. Метод гілок та меж: загальні принципи, використання для задачі про рюкзак, використання для задачі целочисельного ЛП, використання для задачі комівояжера. Методи відтинів Гоморі.
Література
Ашманов С.А. Линейное программирование. М., Наука, 1981 – 304 с.
Мину М. Математическое программирование. – М., Наука, 1990, - 488 с.
Базара М., Шести К., Нелинейное программирование. – М., Наука, 1988, 524 с.
Яловкин Б.Д. Исследование операций. – Харьков, ХАИ, 1977.
Яловкин Б.Д. Математические методы решения задач оптимизации. – Харьков, ХАИ, 1978.
Програма з дисципліни "Бази даних та інформаційні системи"
1. Моделювання бізнес-процесів.
Принципи побудови моделей IDEF0. Робота. Стрілка. Нумерація робот та діаграм. Діаграми дерева вузлів та FEO. Злиття та розщеплення діаграм. Метод опису процесів IDF3. Організаційні діаграми. Імітаційне моделювання. Принципи побудови звітів на підставі інформації функціональної моделі. Засоби AllFusion Modeler (RT Win) та Crystal Reports. Інструментальне середовище RT Win. Групування та сортування даних звіту. Файл даних звіту. Властивості звіту. Методи організації колективної розробки функціональних моделей за допомогою сховищ моделей AllFusion Model Manager. Принципи роботи AllFusion Model Manager (Model Mart). Бібліотеки Model Mart. Сховища Model Mart. Синхронізація моделей процесів та даних.
2. Введення до реляційної алгебри.
Історія створення реляційної алгебри. Основні операції. Спеціальні операції. Замкненість. Нормалізація та денормалізація.
3. Логічне моделювання даних.
Етапи проектування БД. Фізична та логічна моделі даних. Підрівні логічного рівня моделі даних. Ключі. Сутності та атрибути. Зв’язки. Моделювання даних в середовищі ERWin. Ідентифікація сутностей і атрибутів. Відношення: сутності і зв'язку. Типи сутностей і зв'язків. Ієрархія спадкоємства. Домени. Стандарти імен об’єктів моделі. Обмеження даних. Обмеження цілісності, обмеження для доменів і атрибутів. Обмеження типу 1:1, 1:M, M:N. Визначення унiкальних і неунiкальних сутностей. Ідентифікація зв'язків для сутностей і атрибутів.
4. .Фізичний рівень моделі даних.
Створення фізичного рівня моделі даних. Вибір сервера. Правила валідації, значення за умовчанням. Таблиці, колонки, уявлення. Індекси. Тригери та процедури, що зберігаються. Генерація коду. Зв’язування моделі процесів з моделлю даних. Відповідність моделі даних моделі процесів. Експорт даних . Створення сутностей та атрибутів та їх експорт.
5. Архітектура бази даних та екземпляра MS SQL.
Структура БД MS SQL. Табличні простори, схеми і об'єкти схеми. Блоки даних, сегменти, екстенти. Елементи фізичної структури бази даних. Файли даних, файли журналу повторного виконання, керуючі файли. Екземпляр серверу бази даних. Призначені для користувача процеси, процеси MS SQL, серверні процеси, фонові процеси.
6. Забезпечення безопасності та контролю доступу.
Структурні елементи організації доступу: користувачі, системні привілеї, квоти та параметри табличного простору, про файли та ліміти на ресурси. Аудит дій користувача.
7. Основи конфігурування MS SQL.
Порядок запуску та останову серверу. Конфігураційний файл екземпляру. Конфігурація клієнта для використання локального методу дозволу імен.
8. Мова визначення даних DDL SQL.
Управління даними DCL SQL. Об’єкти схеми MS SQL. Системні привілеї і ролі. Таблиці, уявлення, послідовності. Основні типи даних. Перевірки умов.
9. Мова маніпулювання даними DML.
Команда вибірки даних SELECT. Шаблони в умовах пошуку. Операції IN, BETWEEN, LIKE. Пропозиція ORDER. Операція IS NULL. Стандартні функції SQL в MS SQL. Угрупування даних та агрегуючі функції. Внутрішні і зовнішні з'єднання таблиць. Підзапити. Кореляційні підзапити, ієрархічні підзапити, підзапити, що змінюють дані. Поняття транзакції Старт і завершення транзакцій, проміжні крапки.
10. Мова PL/SQL.
Базові елементи синтаксису PL/SQL. Програмні блоки, коментарі. Скалярні та складові типи (записи і таблиці). Зв'язані атрибути. Присвоювання значень. Управляючі структури мови PL/SQL. Умовний оператор, цикли. SQL в PL/SQL. Вбудовані функції PL/SQL. Робота з курсорами. Оголошення, відкриття, закриття курсору. Атрибути курсору. Оператор FETCH. Підпрограми в PL/SQL: процедури і функції. Модулі. Параметри в процедурах і функціях. Пакети та модулі в PL/SQL. Виклик процедур та функцій пакету. Обробка виняткових ситуацій. Оголошення виняткових ситуацій. Тригери БД в PL/SQL. Створення тригерів. Типи тригерів.
Література
Дейт, К. Дж. Введение в системы баз данных, 8-е издание.: Пер. с англ., М.: Издательский дом "Вильяме", 2005. — 1328 с.
Маклаков С.В. Создание информационных систем с AllFusion Modeling Suit М.: Диалог-МИФИ, 2005. — 428 с.
Дж. Грофф, П. Вайнберг SQL; Полное руководство: Пер. с англ. - 2-е изд., перераб. и доп., К.: Издательская группа BHV, 2001. - 816 с.
Програму розробили:
К.т.н., доцент кафедри інформатики Ю.К. Чернишев
Ст. викл. кафедри інформатики О.М. Подоляка
Ст. викл. кафедри інформатики О.В. Ярова
К. ф.-м. н., доцент кафедри інформатики О.В. Карташов
Ст. викл. кафедри інформатики К.П. Коробчинський
|