Перелік питань, що виносяться на вступний іспит в 2011 р. (магістри та спеціалісти, спеціальності «інформатика», «програмне забезпечення автоматизованих систем»)
| Вид материала | Документы |
- Міністерство освіти І науки України Харківський національний університет радіоелектроніки, 399.18kb.
- Перелік питань, які виносяться на державний іспит зі спеціальності «Гнучкі комп’ютеризовані, 78.64kb.
- 8. перелік питань, що виносяться на іспит, 53.98kb.
- Затверджено на засіданні кафедри психології, соціології та права, 38.63kb.
- Перелік питань, які виносяться на державний іспит з курсу «Теорія держави І права», 50.84kb.
- Міністерство освіти І науки, молоді та спорту україни івано-франківський національний, 85.61kb.
- Міністерство освіти І науки, молоді та спорту україни івано-франківський національний, 58.67kb.
- Питання на залік з дисципліни “Безпека життєдіяльності”, 22kb.
- Перелік питань, які виносяться до фахових вступних випробувань зі спеціальності 7 080403, 72.79kb.
- Перелік питань на державний іспит зі спеціальності “Державне управління”, 399.79kb.
ПЕРЕЛІК ПИТАНЬ, ЩО ВИНОСЯТЬСЯ НА ВСТУПНИЙ ІСПИТ в 2011 р.
(магістри та спеціалісти, спеціальності «інформатика», «програмне забезпечення автоматизованих систем»)
1. Математичний аналiз та диференцiальнi рiвняння
1. Числова послiдовнiсть та її границя.
2. Властивостi неперервної функцiї на компактi.
3. Диференцiйованiсть функцiї. Критерiй диференцiйованостi.
4. Локальний екстремум. Необхiднi та достатнi умови екстремуму.
5. Інтеграл Рiмана. Критерiй iнтегрованостi функцiї за Рiманом.
6. Інтеграл Рiмана на компактi та його застосування (обчислення площ, об'ємiв).
7. Числовi ряди. Ознаки збiжностi.
8. Функцiональнi ряди. Ознаки рiвномiрної збiжностi.
9. Ряди Фур'є. Рiвномiрна збiжнiсть рядiв Фур'є.
10. Формула Тейлора функції однієї змінної .
11. Функцiї багатьох змiнних. Диференцiал та частиннi похiднi.
12. Теорема iснування та єдиностi розв'язку задачi Кошi диференцiального рiвняння першого порядку.
13. Лiнiйнi однорiднi диференцiальнi рiвняння n-го порядку iз сталими коефiцiєнтами. Побудова загального розв'язку.
14. Системи лiнiйних диференцiальних рiвнянь з сталими коефiцiєнтами. Знаходження загального розв'язку однорiдних систем.
15. Подання розв'язку лiнiйних неоднорiдних систем за допомогою формули Кошi.
Література
1. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т.1–Т.3. – М., Наука, 1966.
2. Демидович Б.П. Сборник задач и упражнений по математическому анализу. – М., Наука, 1972.
3. Гаращенко Ф.Г., Матвієнко В.Т. Диференціальні рівняння. – К., ВПЦ Київського ун-ту, 2002.
4. Хусаінов Д.Я., Бичков О.С. Диференціальні рівняння. – К., ВПЦ Київського ун-ту, 2001. –
2. Лінійна алгебра та геометрiя
1. Основнi рiвняння прямої та площини у просторi.
2. Критерiй сумiсностi системи лiнiйних рiвнянь.
3. Лiнiйна залежнiсть та ранг системи векторiв, методи обчислення рангiв.
4. Лiнiйнi оператори скiнченно-вимiрних просторiв та їх матрицi.
5. Власнi вектори та власнi числа лiнiйних операторiв.
6. Лiнiйнi оператори простої структури.
7. Лiнiйнi оператори дiйсних евклiдових просторiв.
8. Зведення квадратичних форм до канонiчного вигляду.
9. Основна теорема про подiльність многочленiв.
10. Жордановi нормальнi форми матриць.
Література
1. Курош А.Г. Курс высшей алгебры. – М., Наука, 1965.
2. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. – М., Наука, 1964.
3. Дискретна математика
1. Множини, операції над множинами. Злiченнi та незлiченнi множини. Теореми Кантора.
2. Вiдношення, їх властивостi. Вiдношення еквiвалентностi та часткового порядку.
3. Основне правило комбінаторики. Сполуки, перестановки, розмiщення. Біном Ньютона, полiномiальна теорема. Метод рекурентних співвідношень.
4. Поняття універсальної алгебри. Напівгрупи, групи, кільця. Булеві алгебри.
5. Канонiчнi (нормальнi) форми булевих функцiй. Алгебра Жегалкiна.
6. Повнота i замкненiсть систем булевих функцiй. Теорема (критерiй) Поста.
7 Графи. Орієнтовані та неорієнтовані графи. Зв'язнiсть графiв. Ейлерові та гамільтонові графи. Планарнi графи, формула Ейлера. Дерева.
8. Скінченні автомати. Теореми про детермінізацію, мінімізацію, синтез та аналіз.
Література
1. Лавров И.А. Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., Физматлит, 2001.
2. Романовский И.В. Дискретный анализ. – С.Петербург, СПб-ВНV, 2003.
3. Капітонова Ю.В., Кривий С.Л. та ін. Основи дискретної математики. – К., Наукова думка, 2002.
4. Кривий С.Л. Курс дискретної математики. – К., Вид. Авіаційного національного університету. – 2007. – 430 с.
5. Кривий С.Л., Ходзінський О.М. Збірник задач з дискретної математики. – К., Вид. «Бізнес поліграф». – 2008. – 434 с.
4. Програмування
1. Мови програмування та їх класифiкацiя.
2. Типи даних. Скалярні та структурованi типи даних.
3. Процедури та функцiї як засоби структуризацiї програм. Виклики процедур та функцiй.
4. Первиннi оператори. Оператор присвоєння. Структурнi оператори. Оператори вводу-виводу.
5. Динамічні лінійні структури даних. Списки, стеки, черги.
6. Динамічні нелінійні структури даних. Дерева. Бінарні дерева. Дерева бінарного пошуку.
7. Поняття про функцiональне програмування.
8. Поняття про структурне програмування.
9. Поняття про об'єктно-орiєнтоване програмування.
10. Cучасні технології програмування та тенденції їх розвитку.
Література
1. Себеста Р. Основные концепции языков программирования. – М., Изд. дом «Вильямс», 2000.
2. Вирт Н. Алгоритмы + Структуры данных = Программы. – М., Мир, 1984.
3. Макконнел Дж. Основы современных алгоритмов. – М.: Техносфера, 2004.
4. Грис Д. Наука программирования. – М.: Мир, 1984.
5. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения. – М.:
Мир, 1982.
6. Йодан Э. Структурное проектирование и конструирование программ. – М.: Мир, 1979.
5. Математична логіка та теорія алгоритмів
1. Поняття предиката, висловлення. Пропозиційна логіка (логіка висловлень). Пропозиційне числення, його несуперечливість та повнота.
2. Логіки 1-го порядку, їх моделі та мови. Мова арифметики. Виразність предикатів, множин, функцій. Істинність та виконуваність, логічний наслідок, логічна еквівалентність.
3. Формально-аксіоматичні системи логік 1-го порядку (теорії 1-го порядку). Несуперечливість, повнота, розв’язність теорій 1-го порядку.
4. Теорема Гьоделя про повноту. Теорема компактності, її наслідки. Категоричність. Теореми Гьоделя про неповноту, їх значення.
5. Методи автоматизації доведень. Метод резолюцій.
6. Секвенційні числення логік 1-го порядку, їх коректність та повнота.
7. Поняття алгоритму. Формальні моделі алгоритмів. Нормальні алгоритми Маркова, машини Тьюрінга. Частково рекурсивні, рекурсивні, примітивно рекурсивні функції. Теза Чорча.
8. Нумерації. s-m-n-теорема. Універсальні функції. Універсальна частково-рекурсивна функція, універсальна машина Тьюрінга.
9. Рекурсивні та рекурсивно перелічні множини, рекурсивні та частково рекурсивні предикати.
10. Алгоритмічна розв’язність, часткова розв’язність та нерозв’язність масових проблем. Нерозв’язність проблем зупинки та самозастосовності, наслідки.
Література
1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., Мир, 1983.
2. Клини С. Математическая логика. – М.: Наука, 1973.
3. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
4. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. К., ВПЦ Київський ун-т, 2008.
5. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.
6. Шкільняк С.С. Математична логіка. Приклади і задачі. – ВПЦ Київський ун-т. – К., 2007.
7. Шкільняк С.С. Tеорія алгоритмів: приклади і задачі. – ВПЦ Київський ун-т. – Київ, 2003.
8. Новиков П.С. Элементы математической логики. М.: Наука.-1970. – 310 с.
6. Теорiя ймовiрностей та математична статистика
1. Аксiоматичне означення ймовiрностей. Формула повної ймовiрностi та формула Байеса.
2. Випадковi величини. Властивостi функцiй розподiлу.
3. Нерiвнiсть Чебишева. Закон великих чисел.
4. Основнi типи дискретних та неперервних розподiлiв.
5. Центральна гранична теорема для однаково розподiлених незалежних випадкових величин.
6. Поняття випадкового процесу. Вiнерiвський та Пуасонiвський процеси.
7. Випадкове середнє та дисперсiя. Емпiрична функцiя розподiлу. Теореми Глiвенка та Колмогорова.
8. Перевiрка статистичних гiпотез. Критерiї Колмогорова та Пiрсона.
Література
- Гнеденко Б.В. Курс теории вероятностей. – М., Наука, 1965.
- Боровиков А.А. Курс теории вероятности. – М., Наука, 1976.
- Гихман И.И., Скороход А.В., Ядренко М.И. Теория вероятности и математическая статистика - К., Вища школа, 1979.
7. Дослідження операцій
1. Задача лiнiйного програмування. Її властивостi.
2. Критерiй оптимальностi базисного розв'язку задачi ЛП.
3. Двоїстi задачi лiнiйного програмування. Теореми двоїстостi.
4. Задача опуклого програмування. Теорема Куна-Такера.
5. Метод найшвидшого спуску.
6. Оптимальнi чистi стратегiї у матричнiй грi. Теорема про мінімакс.
Література
1. Попов Ю.Д., Тюптя В.І., Шевченко В.І., Методи оптимізації. – Київ, Абрис, 1999.
2. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М., Высшая школа, 1986.
8. Бази даних та інформаційні системи
1. ER–модель.
2. Класифікація запитів.
3. Реляційна модель Кодда. Реляційна алгебра.
4. Функціонально повна залежність. 2-нормальна форма.
5. Мінімальна структура функціональних залежностей.
6. Аксіоми Армстронга.
7. Третя нормальна форма та третя нормальна форма Бойса-Кодда.
8. Багатозначні залежності. 4-нормальна форма.
9. Стратегії розподілу даних в розподілених базах даних.
Література
1. Дейт К. Введение в системы баз данных. – М., Издательский дом “Вильямс”, 2000.
2. Ульман Дж. Основы баз данных. – М., Статистика, 1982.
3. Дрибас В.П. Основы теории реляционных баз данных. – Минск, 1982.
9. Системне програмування
1. Поняття мовного процесора. Типи мовних процесорів. Основні фази мовного процесора.
2. Скінченні автомати. Побудова лексичного аналізатора на основі скінченного автомата.
3. Регулярні множини та регулярні вирази, їх зв'язок із скінченними автоматами. Основні тотожності в алгебрі регулярних виразів.
4. Синтаксичний аналіз та породжувальні граматики. Виведення в граматиці. Дерево виведення. Лівостороння та правостороння стратегії виведення.
5. LL(k)-граматики. Перевірка LL(1)-умови. Побудова LL(1)-таблиці для управління синтаксичним LL(1)-аналізатором.
6. Машинно-орієнтовані мови програмування. Асемблери. Структура асемблера, перегляди тексту програми та відповідні бази даних.
7. Операційні системи. Їх призначення, функції, основні концепції. Ядро операційної системи. Сучасні операційні системи.
Література
1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т1. М. Мир. 1978.
2. Грис Д. Построение компиляторов для ЦЭВМ. М. Мир. 1976..
3. Льюис Ф., Стирнз Р., Розенкранц Д. Теоретические основы постр. компиляторов. М. Мир. 1979.
10. Теорія програмування та теорія обчислень
1. Основні аспекти програм. Основні поняття програмування.
2. Методи подання синтаксису мов програмування.
3. Класифікація породжувальних граматик.
4. Автоматна характеристика основних класів мов.
5. Методи формальної семантики мов програмування. Метод нерухомої точки.
6. Формальні методи програмування.
7. Функції складності (сигналізуючі) за часом та за пам’яттю. P-повні та NP-повні проблеми.
8. Функції, елементарні за Кальмаром. Співвідношення між класами примітивно рекурсивних та елементарних функцій.
Література
1. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных. – К., Либідь, 1992.
2. Грис Д. Наука программирования. – М., Мир, 1982.
3. Лавров С. Программирование. Математические основы, средства, теория. – С.Петербург, СПб-БХВ, 2000.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М., Мир, 1979.
5. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. – М., Мир, 1982.
6. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., Мир, 1983.
7. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. К., ВПЦ Київський ун-т, 2008.
ЗРАЗОК 1
ВСТУПНИЙ ІСПИТ
з математики та інформатики
Спеціальність "Інформатика" (магістр)
Екзаменаційний білет № 00
1. Стратегії розподілу даних в розподілених базах даних.
2. Канонiчнi (нормальнi) форми булевих функцiй. Алгебра Жегалкiна.
3. Локальний екстремум. Необхiднi та достатнi умови екстремуму.
4. Задача з курсу програмування.
5. Задача з курсу математичної логіки.
ЗРАЗОК 2
ВСТУПНИЙ ІСПИТ
з математики та інформатики
Спеціальність "Програмне забезпечення автоматизованих систем" (спеціаліст)
Екзаменаційний білет № 00
1. Машинно-орієнтовані мови програмування. Асемблери. Структура асемблера, перегляди тексту програми та відповідні бази даних.
2. Методи автоматизації доведень. Метод резолюцій.
3. Лiнiйна залежнiсть та ранг системи векторiв, методи обчислення рангiв.
4. Задача з курсу бази даних.
5. Задача з курсу дослідження операцій.