міністерство освіти і науки, молоді та спорту УкраЇНИ

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ТЕХНОЛОГІЙ ТА ДИЗАЙНУ

Затверджую

Ректор КНУТД

________________І.М.Грищенко

“______”______________ 2012 р.

ПРОГРАМА ФАХОВИХ

вступних випробувань

на здобуття освітньо-кваліфікаційного рівня бакалавр

на базі здобутого ОКР молодшого спеціаліста

з напряму

6.050101 – «Комп’ютерні науки»

рекомендовано Розглянуто та схвалено

вченою радою факультету на засіданні кафедри

технологій легкої інформаційних технологій

промисловості проектування

від «____»________ 2012р від «___»_____ 2012 р.

Протокол № ____ Протокол № ___

Декан факультету__________ Зав. кафедрою ____________

(підпис) (підпис)

Київ – 2012

1. Загальні відомості

Прийом абітурієнтів для здобуття освітньо-кваліфікаційного рівня бакалавр з напрямку 6.050101 – “Комп’ютерні науки ” проводиться за результатами фахових вступних випробувань. Вони відбуватимуться у формі усного екзамену, який містить питання з дисциплін циклу професійної підготовки.

2. Перелік фахових навчальних дисциплін з яких будуть проведені вступні випробування

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

Теорія множин та відношень. Алгебри. Комбінаторний аналіз. Математична логіка. Логіка висловлювань. Теорія графів. Дерева. Теорія скінченних автоматів.

2. Теорія алгоритмів.

Математичні основи аналізу алгоритмів. Алгоритмічні стратегії. Класи складності. Алгоритми сортування, злиття та пошуку. Комбінаторні алгоритми. Рекурсивні алгоритми. Фундаментальні алгоритми на графах і деревах. Машина Тьюринга.

3. Алгоритмізація та програмування.

Поняття алгоритму та типові алгоритмічні структури програмування. Елементи алгоритмічних мов: концепція типів даних, імена, значення,покажчики, змінні, константи, операції, вирази. Структурне програмування: послідовність, розгалуження та цикли. Рекурсія. Організація даних (масиви, рядки, структури) та алгоритми їх оброблення. Файлові структури даних. Динамічні структури даних (списки, стеки, черги).000000000000000000000000000000000000000000000000000000000000000000и на графах 00000000000000000000000000000000000000000000000000000000000000000000000

4. Об’єктно-орієнтоване програмування.

Поняття об’єктно-орієнтованого аналізу, проектування і програмування. Поняття об’єктів і класів та їх взаємовідносин. Основи об’єктна-орієнтованої мови програмування. Абстрагування даних та інкапсуляція. Конструктори, деструктори класів. Просте та множинне успадкування. Реалізація поліформізму.

3. Орієнтовний перелік питань

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

Множини та відношення. Способи задання множин. Операції над множинами. Декартів добуток множин. Бінарне відношення на множині. Визначення взаємно однозначного відображення множини А в множину В. Елементи математичної логіки. Поняття висловлювання. Таблиця істинності. Операції над висловлюваннями. Елементарні булеві функції. Способи представлення булевих функцій в програмах. Комбінаторика: розміщення, перестановка. Формула для визначення комбінацій. Правила суми та добутку. Біном Ньютона. Властивості біноміальних коефіцієнтів. Графи. Способи задання графів. Операції на графах. Дерева. Бінарні дерева. Способи представлення дерев у програмах.

3.2. Теорія алгоритмів.

Поняття алгоритму, властивості. Алгоритмічні системи. Нормальні алгоритми Маркова. Примітивно рекурсивні функції, частково рекурсивні функції. Машина Тьюринга. Прості стандартні типи даних. Масиви, записи, множини та їх представлення. Файли, операції над файлами, буферізація. Складність алгоритмів по пам’яті. Алгоритми типу «розділяй та володарюй». Рекурентні співвідношення, їх складність. Послідовний пошук, двійковий пошук, пошук в таблиці. Прямий пошук в рядку. Алгоритми сортування масивів. Покращені методи сортування. Сортування послідовностей. Алгоритми обчислення значень многочленів. Алгоритми множення матриць. Порівняння рядків, наближене порівняння рядків. Кінцеві автомати. Обхід в глибину і за рівнями. Алгоритми пошуку мінімального остовного дерева. Алгоритми пошуку найкоротшого шляху. Динамічне програмування.