Мiнiстерство освiти і науки України
Національний аерокосмічний університет ім. М.Є. Жуковського
“Харківський авіаційний інститут”
ЗАТВЕРДЖУЮ
Проректор ХАІ з НПР
______________ В.М. Павленко
“25” лютого 2015 р.
Фахове вступне випробування по спеціальності:
7.04030101, 8.04030101 Прикладна математика
7.04030103, 8.04030103 Комп'ютерне та математичне моделювання
Програму розроблено і затверджено на кафедрі інформатики,
протокол № 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.
Програма з дисципліни "Теорія ймовірностей та математична статистика"
1. Основні поняття.
Алгебра випадкових подій. Ймовірність та її основні властивості. Формули повної ймовірності та Байєса.Повторення випробувань. Формула Бернуллі. Граничні теореми Муавра-Лапласа та Пуассона.
2. Випадкові величини.
Випадкові величини. Закон розподілу ймовірностей дискретної випадкової величини. Неперервні величини. Функція розподілу. Щільність розподілу. Числові характеристики та моменти випадкової величини. Найбільш поширені закони розподілу дискретних та неперервних випадкових величин: біномний, Пуассона, геометричний, показниковий, нормальний,рівномірний, Парето. Їх числові характеристики , властивості та застосування.
3. Багатовимірні випадкові величини.
Закон розподілу ймовірностей двовимірної випадкової величини. Сумісна щільність. Ймовірність влучення випадкової величини у довільну область. Коефіцієнт корреляції.. Незалежні випадкові величини. Загальні властивості числових характеристик випадкових величин.
4. Граничні теореми теорії ймовірностей
Центральна гранична теорема. Теорема Ляпунова . Нерівність Чебишова. Закон великих чисел у різних формах.
Математична статистика.
Вибірковий метод. Варіаційний ряд. Емпірична функція розподілу та гістограма. Точкові оцінки невідомих параметрів розподілу та їх властивості. Інтервальні оцінки, довірчі інтервали. Статистична перевірка гіпотез. Статистика критерію. Критична область. Помилки 1 та 2 роду . Рівень значущості та потужність критерію Перевірка гіпотез щодо параметрів нормального, показникового, пуассонівського та біномного розподілів. Перевірка гіпотези про незалежність. Перевірка гіпотез про вигляд закону розподілу. Критерії Колмогорова та Пірсона. Елементи теорії кореляції та регресії
6. Випадкові процеси.
Означення та приклади випадкових процесів. Класифікація випадкових процесів. Скінченновимінрі розподіли. Теорема Колмогорова. Реалізації. Моменти. Кореляційна функція. Властивості числових характеристик. Означення стаціонарних у вузькому та широкому змісті процесів. Дійсна та комплексна випадкові гармоніки. Гаусовський процес.
7. Процеси Маркова.
Означення , властивості та приклади ланцюгів Маркова. Ергодична теорема та її зміст. Марківський однорідний процес із зчисленною множиною станів. Рівняння Колмогорова-Чепмена. Застосування у теорії масового обслуговування. Системи із очікуванням та системи із втрачанням .
8. Процеси із незалежними приростами. Процес Пуассона та процес броунівського руху.
Процес Пуассона. Одновимірні розподіли. Математичне сподівання, дисперсія, кореляційна функція. Зв'язок між різними означеннями процесу Пуассона. Означення процесу Вінера. Зв'язок між різними означеннями. Основні властивості процесу. Одновимірні та багатовимірні розподіли. Числові характеристики. Приклади застосування процесів Вінера та Пуассона.
Література
Брисіна І.В., Головченко О.В., Кошовий Г.І., Ніколаєв О.Г. та ін. Практичний курс вищої математики в чотирьох книгах: Навч. посібник для Вузів. Харків.: Нац. аерокос. ун-т «Харьк. авіац. ін-т», 2004.
Брисіна І.В., Макарічев В.О. Випадкові процеси, Навчальний посібник. Харків.: Нац. аерокос. ун-т «Харьк. авіац. ін-т», 2009.
Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. М.: Наука ,1991, 384с.
Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука,1991. -384 с.
Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы, М.: Изд.-во МГТУ им. Н.Э.Баумана, 1999, -448 с.
Миллер Б.М., Панков А.Р..- Теория случайных процессов в примерах и задачах.-М.:ФИЗМАТЛИТ, 2002, -320 с.
Сборник задач по математике для ВТУЗов. Под ред. Ефимова А.В.-М.- Наука 1990, 432 с.
Сборник задач по теории вероятностей, математической статистике и теории случайных функций. Под ред. Свешникова А.А., М.: Наука 1970, - 656 с.
Розанов Ю.А. Теория вероятностей, случайные процессы и метематическая статистика. М.: Наука, 1985 - 320 с.
Чистяков В.П. Курс теории вероятностей. СПб.: Лань, 2003.-272 с.
Програма з дисципліни "Методи оптимізації та дослідження операцій "
Задачі лінійного програмування.
Різні постановки задачі лінійного програмування, їх еквівалентність, та зведення до задачі в канонічній постановці. Графічний метод розв’язання задачі. Системи лінійних рівнянь: канонічний вид, загальні та часткові розв’язки, базові часткові розв’язки. Виключення Жордана-Гауса та його використання для розв’язання систем лінійних рівнянь. Опорні розв’язки задачі лінійного програмування. Основи симплекс-методу для покращення опорного розв’язку: приведені оцінки, умови оптимальності, умови необмеженого зменшення функції мети на області припустимих розв’язків, правила обирання опорних строки та стовпця при переході до нового опорного розв’язку. Алгоритм симплекс-методу. Використання симплекс методу для пошуку початкового опорного розв’язку. Пара двоїстих задач лінійного програмування. Правила переходу до двоїстої задачі. Перша та друга теореми двоїстості. Використання розв’язку двоїстої задачі для пошуку розв’язку вихідної задачі. Геометрична інтерпретація симплекс-методу та його обчислювальна складність. Економічна інтерпретація пари симетричних двоїстих задач. Подальший розвиток методів розв’язання задач лінійного програмування. Транспортна задача лінійного програмування. Постановка. Властивості та особливості цієї задачі лінійного програмування. Транспортна таблиця. Методи побудови початкового опорного розв’язку: північно-західного кута, мінімальної вартості, подвійного уподобання, метод Фогеля. Цикли в транспортній таблиці та їхні властивості. Алгоритм переходу від одного опорного розв’язку до іншого. Розподільчій метод і метод потенціалів для покращення опорного розв’язку транспортної задачі.
Одновимірна нелінійна оптимізація.
Постановка задачі. Необхідні та достатні умови оптимальності. Методи розв’язання, що використовують похідні: Ньютона-Рафсона, хорд, дихотомії з використанням похідних. Унімодальні функції. Використання їх властивостей для розв’язання задач оптимізаціїї. Методи оптимізації унімодальних функцій: рівномірного пошуку, дихотомії без використання похідних, Фібоначі, золотого розчину. Метод квадратичної інтерполяції.
3. Елементи опуклого аналізу.
Опуклі множини та їх основні властивості. Проекція точки на множину. Теореми відокремлення. Конуси. Теорема Фаркаша. Геометричний зміст теореми Фаркаша. Опуклі функції. Визначення та властивості. Узагальнення опуклої функції.
4. Нелінійна безумовна оптимізація.
Постановка задачі. Необхідні та достатні умови оптимальності. Методи, що використовують градієнт. Метод найшвидкішого спуску. Покращений метод найшвидкішого спуску. Загальні принципи методів спряжених напрямків. Метод спряженого градиєнту для опуклої квадратичної функції. Метод Флетчера – Рівза. Метод Ньютона. Модифіковані методи Ньютона: із змінним кроком, з корекцією матриці Гессе, з використанням кінцево-різницевої апроксимації матриці Гесе. Загальні принципи квазіньютонівських методів. Квазіньютонівські методи: з поправочною матрицею ранга 1. Методи, що не використовують градієнт: циклічного покоординатного спуску, Хука и Дживса с дискретным кроком, Нелдера – Міда (деформованого багатокутника).
5. Нелінійна умовна оптимізація.
Постановка задачі. Припустимі напрямки. Конус припустимих напрямків. Необхідна умова допустимого напрямку. Теорема Куна –Такера для задачі з обмеженнями – нерівностями та для задачі зі змішаними обмеженнями. Геометричний зміст теореми Куна –Такера. Достатні умови екстремуму для задачі зі змішаними обмеженнями. Умови экстремуму задачі с псевдоувігнутою функцією мети. Пряме використання теореми Куна –Такера для пошуку екстремуму. Метод штрафних функцій. Метод бар’єрів. Метод можливих напрямків. Метод проекції градієнту: обирання напряму руху, обирання довжини кроку, процедури зміни активного набору, модельна схема.
6. Дискретна оптимізація.
Постановка. Метод гілок та меж: загальні принципи, використання для задачі про рюкзак, використання для задачі целочисельного ЛП, використання для задачі комівояжера. Методи відтинів Гоморі.
Література
Ашманов С.А. Линейное программирование. М., Наука, 1981 – 304 с.
Мину М. Математическое программирование. – М., Наука, 1990, - 488 с.
Базара М., Шести К., Нелинейное программирование. – М., Наука, 1988, 524 с.
Яловкин Б.Д. Исследование операций. – Харьков, ХАИ, 1977.
Яловкин Б.Д. Математические методы решения задач оптимизации. – Харьков, ХАИ, 1978.
Програму розробили:
К.т.н., доцент кафедри інформатики Ю.К. Чернишев
Ст. викл. кафедри інформатики О.М. Подоляка
Ст. викл. кафедри інформатики О.В. Ярова
К. ф.-м. н., доцент кафедри вищої математики І.В. Брисіна
К. ф.-м. н., доцент кафедри інформатики О.В. Карташов
|