Користувач:Bunyk/Зміст вікіпедії

ПЕРЕЛІК ПИТАНЬ, ЩО ВИНОСЯТЬСЯ НА ВСТУПНИЙ ІСПИТ в 2011 р.

(магістри та спеціалісти, спеціальності «інформатика», «програмне забезпечення автоматизованих систем»)

Математичний аналіз та диференціальні рівняння

1. Числова послідовність та її границя.
2. Властивості неперервної функції на компакті.
3. Диференційованість функції. Критерій диференційованості.
4. Локальний екстремум. Необхідні та достатні умови екстремуму.
5. Інтеграл Рімана. Критерій інтегрованості функції за Ріманом.
6. Інтеграл Рімана на компакті та його застосування (обчислення площ, об'ємів).
7. Числові ряди. Ознаки збіжності.
8. Функціональні ряди. Ознаки рівномірної збіжності.
9. Ряди Фур'є. Рівномірна збіжність рядів Фур'є.
10. Формула Тейлора функції однієї змінної.
11. Функції багатьох змінних. Диференціал та частинні похідні.
12. Теорема існування та єдиності розв'язку задачі Коші диференціального рівняння першого порядку.
13. Лінійні однорідні диференціальні рівняння n-го порядку із сталими коефіцієнтами. Побудова загального розв'язку.
14. Системи лінійних диференціальних рівнянь з сталими коефіцієнтами. Знаходження загального розв'язку однорідних систем.
15. Подання розв'язку лінійних неоднорідних систем за допомогою формули Коші.

Література

1. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т.1–Т.3. – М., Наука, 1966.
2. Демидович Б.П. Сборник задач и упражнений по математическому анализу. – М., Наука, 1972.
3. Гаращенко Ф.Г., Матвієнко В.Т. Диференціальні рівняння. – К., ВПЦ Київського ун-ту, 2002.
4. Хусаінов Д.Я., Бичков О.С. Диференціальні рівняння. – К., ВПЦ Київського ун-ту, 2001. –

Чисельні методи

1. Методи розв'язування нелінійних рівнянь та систем
2. Чисельні методи розв'язування систем лінійних рівнянь
3. Методи інтерполювання. Множники Лагранжа та Ерміта. Сплайни
4. Методи чисельного інтегрування
5. Чисельні методи розв'язування задачі Коші.

Лінійна алгебра та геометрія

1. Основні рівняння прямої та площини у просторі.
2. Критерій сумісності системи лінійних рівнянь.
3. Лінійна залежність та ранг системи векторів, методи обчислення рангів.
4. Лінійні оператори скінченно-вимірних просторів та їх матриці.
5. Власні вектори та власні числа лінійних операторів.
6. Лінійні оператори простої структури.
7. Лінійні оператори дійсних евклідових просторів.
8. Зведення квадратичних форм до канонічного вигляду.
9. Основна теорема про подільність многочленів.
10. Жорданові нормальні форми матриць.

Література

1. http://www.unicyb.kiev.ua/Library/Algebra/
2. Курош А.Г. Курс высшей алгебры. – М., Наука, 1965.
3. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. – М., Наука, 1964.

Дискретна математика

1. Множини, операції над множинами. Зліченні та незліченні множини. Теореми Кантора.
2. Відношення, їх властивості. Відношення еквівалентності та часткового порядку.
3. Основне правило комбінаторики. сполуки , перестановки, розміщення. Біном Ньютона, поліноміальна теорема. Метод рекурентних співвідношень.
4. Поняття універсальної алгебри. Напівгрупи, групи, кільця. Булеві алгебри.
5. Канонічні (нормальні) форми булевих функцій. Алгебра Жегалкіна.
6. Повнота і замкненість систем булевих функцій. Теорема (критерій) Поста.
7. Графи. Орієнтовані та неорієнтовані графи. Зв'язність графів. Ейлерові та гамільтонові графи. Планарні графи, формула Ейлера. Дерева.
8. Скінченні автомати. Теореми про детермінізацію, мінімізацію, синтез та аналіз.

Література

1. Лавров И.А. Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., Физматлит, 2001.
2. Романовский И.В. Дискретный анализ. – С.Петербург, СПб-ВНV, 2003.
3. Капітонова Ю.В., Кривий С.Л. та ін. Основи дискретної математики. – К., Наукова думка, 2002.
4. Кривий С.Л. Курс дискретної математики. – К., Вид. Авіаційного національного університету. – 2007. – 430 с.
5. Кривий С.Л., Ходзінський О.М. Збірник задач з дискретної математики. – К., Вид. «Бізнес поліграф». – 2008. – 434 с.

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

1. Мови програмування та їх класифікація.
2. Типи даних. Скалярні та структуровані типи даних.
3. Процедури та функції як засоби структуризації програм. Виклики процедур та функцій.
4. Первинні оператори. Оператор присвоєння. Структурні оператори. Оператори вводу-виводу.
5. Динамічні лінійні структури даних. Списки, стеки, черги.
6. Динамічні нелінійні структури даних. Дерева. Бінарні дерева. Дерева бінарного пошуку.
7. Поняття про функціональне програмування.
8. Поняття про структурне програмування.
9. Поняття про об'єктно-орієнтоване програмування.
10. Cучасні технології програмування та тенденції їх розвитку.

Література

1. Себеста Р. Основные концепции языков программирования. – М., Изд. дом «Вильямс», 2000.
2. Вирт Н. Алгоритмы + Структуры данных = Программы. – М., Мир, 1984.
3. Макконнел Дж. Основы современных алгоритмов. – М.: Техносфера, 2004.
4. Грис Д. Наука программирования. – М.: Мир, 1984.
5. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения. – М.:Мир, 1982.
6. Йодан Э. Структурное проектирование и конструирование программ. – М.: Мир, 1979.

Математична логіка та теорія алгоритмів

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 с.

Теорія ймовірностей та математична статистика

1. Аксіоматичне означення ймовірностей. Формула повної ймовірності та формула Байеса.
2. Випадкові величини. Властивості функцій розподілу.
3. Нерівність Чебишева. Закон великих чисел.
4. Основні типи дискретних та неперервних розподілів.
5. Центральна гранична теорема для однаково розподілених незалежних випадкових величин.
6. Поняття випадкового процесу. Вінерівський та Пуасонівський процеси.
7. Випадкове середнє та дисперсія. Емпірична функція розподілу. Теореми Глівенка та Колмогорова.
8. Перевірка статистичних гіпотез. Критерії Колмогорова та Пірсона.

Література

1. Гнеденко Б.В. Курс теории вероятностей. – М., Наука, 1965.
2. Боровиков А.А. Курс теории вероятности. – М., Наука, 1976.
3. Гихман И.И., Скороход А.В., Ядренко М.И. Теория вероятности и математическая статистика - К., Вища школа, 1979.

Дослідження операцій

1. Задача лінійного програмування. Її властивості.
2. Критерій оптимальності базисного розв'язку задачі ЛП.
3. Двоїсті задачі лінійного програмування. Теореми двоїстості.
4. Задача опуклого програмування. Теорема Куна-Такера.
5. Метод найшвидшого спуску.
6. Оптимальні чисті стратегії у матричній грі. Теорема про мінімакс.

Література

1. Попов Ю.Д., Тюптя В.І., Шевченко В.І., Методи оптимізації. – Київ, Абрис, 1999.
2. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М., Высшая школа, 1986.

Бази даних та інформаційні системи

1. ER–модель.
2. Класифікація запитів до БД.
3. Реляційна модель Кодда. Реляційна алгебра.
4. Функціонально повна залежність. Друга нормальна форма.
5. Мінімальна структура функціональних залежностей.
6. Аксіоми Армстронга.
7. Третя нормальна форма та нормальна форма Бойса-Кодда.
8. Багатозначні залежності. Четверта нормальна форма.
9. Стратегії розподілу даних в розподілених базах даних.

Література

1. Дейт К. Введение в системы баз данных. – М., Издательский дом “Вильямс”, 2000.
2. Ульман Дж. Основы баз данных. – М., Статистика, 1982.
3. Дрибас В.П. Основы теории реляционных баз данных. – Минск, 1982.

Системне програмування

1. Поняття мовного процесора. Типи мовних процесорів. Основні фази мовного процесора. (Примітка. Дивіться "Транслятор". [1])
2. Скінченні автомати. Побудова лексичного аналізатора на основі скінченного автомата.
3. Регулярні множини та регулярні вирази, їх зв'язок із скінченними автоматами. Основні тотожності в алгебрі регулярних виразів.
4. Синтаксичний аналіз та породжувальні граматики. Виведення в граматиці. Дерево виведення. Лівостороння та правостороння стратегії виведення.
5. LL(k)-граматики. Перевірка LL(1)-умови. Побудова LL(1)-таблиці для управління синтаксичним LL(1)-аналізатором.
6. Машинно-орієнтовані мови програмування. Асемблери. Структура асемблера, перегляди тексту програми та відповідні бази даних.
7. Операційні системи. Їх призначення, функції, основні концепції. Ядро операційної системи. Сучасні операційні системи.

Література

1. Волохов. Системне програмування.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т1. М. Мир. 1978.
3. Грис Д. Построение компиляторов для ЦЭВМ. М. Мир. 1976..
4. Льюис Ф., Стирнз Р., Розенкранц Д. Теоретические основы постр. компиляторов. М. Мир. 1979.

Теорія програмування та теорія обчислень

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. Розподіл оперативної пам’яті, поняття сегменту та зсуву. Сторінкова організація пам’яті.
2. Канали та порти вводу-виводу.
3. Поняття про переривання та їх класифікація.
4. Організація буферу клавіатури.
5. Поняття про відеосистему. Режими роботи відеосистеми.
6. Структура таблиці розміщення файлів на магнітних дисках. Фізичний та логічний формати магнітних дисків. Коренева директорія.
7. Системи телеобробки даних. Функціональне середовище для взаємодії систем телеобробки. Етапи у взаємодії систем телеобробки.
8. Модель відкритої системи, стек протоколів. Концепція еталонної моделі OSI.
9. Стек протоколів TCP/IP: топологічні особливості, функції рівнів.
10. Архітектура мережевої телеобробки: однорангова, клієнт/сервер, трирівнева.
11. Надійність систем телеобробки та комп’ютерних мереж. Класи безпеки. Міжмережеві екрани. Proxy-сервери, брандмауери.
12. Мультиплексування цифрових каналів з розділенням у часі (TDM). Плезіохронні та синхронні цифрові ієрархії. Широкосмугові канали зв’язку.
13. Повторювачі, мости, маршрутизатори, шлюзи та їх місце в профілі OSI.
14. Поняття мереж комутації: пакетів, каналів, повідомлень. Контроль перевантажень в мережах комутації пакетів.

Література

1. Мюллер С. Модернизация и ремонт ПК.
2. Скляров В.А. Программное и лингвистическое обеспечение. Системы общего назначения.
3. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – С.-П., 2000.
4. Вернер Ф. Энциклопедия современных сетевых технологий. – К., Комиздат, 1998.
5. Мартин Дж. Вычислительные сети и распределенная обработка данных. – М., Финансы и статистика, Т.1-2, 1986.
6. Марк А. Спортак, Франк Ч. Паппас и др. Высокопроизводительные сети. Энциклопедия пользователя. – К., Диа-Софт, 1997.
7. Зайцев С.С., Кравцунов М.И., Ротанов С.В. Сервис открытых информационно-вычислитель-ных сетей. Справочник. – М., Радио и связь, 1990.

ЗРАЗОК 1

ВСТУПНИЙ ІСПИТ з математики та інформатики Спеціальність "Інформатика" (магістр) Екзаменаційний білет № 00

1. Стратегії розподілу даних в розподілених базах даних.
2. Канонічні (нормальні) форми булевих функцій. Алгебра Жегалкіна.
3. Локальний екстремум. Необхідні та достатні умови екстремуму.
4. Задача з курсу програмування.
5. Задача з курсу математичної логіки.

Посилання

• GOS2010