М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.
Програму розробили:
К.т.н., доцент кафедри інформатики Ю.К. Чернишев
Ст. викл. кафедри інформатики О.М. Подоляка
Ст. викл. кафедри інформатики О.В. Ярова
|