ПРОГРАМА ВСТУПНОГО ФАХОВОГО ВИПРОБУВАННЯ

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

ІМЕНІ ТАРАСА ШЕВЧЕНКО

ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

«ЗАТВЕРДЖЕНО» «РЕКОМЕНДОВАНО»

на засіданні Приймальної комісії Вченою радою факультету інформаційних технологій

КНУ імені Тараса Шевченко

Протокол № ___ від «__»_____2017 р. Протокол № __ від «___» _____ 2017 р.

Голова Приймальної комісії Голова Вченої ради факультету

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

_________________ ________________ Тесля Ю.М.

ПРОГРАМА

вступного фахового випробування

при вступі на навчання на 2-ий курс для здобуття ОР «Бакалавр»

на базі ОКР «Молодший спеціаліст»

галузь знань: 12 Інформаційні технології

спеціальність 122 Комп’ютерні науки та інформаційні технології

за освітньою програмою «Прикладні інформаційні системи»

Київ – 2017

Пояснювальна записка

Програму складено відповідно з кваліфікаційними характеристиками «Молодшого спеціаліста» за спеціальністю 122 «Комп’ютерні науки та інформаційні технології».

Фахове вступне випробування на навчання за освітньою програмою «Прикладні інформаційні системи» за спеціальністю 122 «Комп’ютерні науки та інформаційні технології» приймається екзаменаційною комісією.

МЕТА ФАХОВОГО ВСТУПНОГО ВИПРОБУВАННЯ

Метою проведення фахового вступного випробування на навчання за освітньою програмою «Прикладні інформаційні системи» за спеціальністю 122 Комп’ютерні науки та інформаційні технології є:

визначення рівня фахової підготовки молодших спеціалістів;
перевірити вміння вступників застосовувати ці знання і навички для вирішення практичних фахових задач, що відповідають функціональним обов’язкам посад, зазначених у кваліфікаційній характеристиці.

ПОРЯДОК ПРОВЕДЕННЯ ФАХОВОГО ВСТУПНОГО ВИПРОБУВАННЯ

Форма проведення фахового вступного випробування – письмовий іспит.

Фахове випробування складається з теоретичної та практичної частини. Необхідні для вичерпної відповіді на питання білету записи виконують на папері зі штампом факультету. На кожному листі абітурієнт вказує своє прізвище, ініціали, номер білета. Листи нумерують, заповнюють із обох сторін.

Питання до білетів сформовано на основі цієї програми, яку абітурієнти отримують завчасно. Для програмування дозолено використовувати мови програмування: C, C++, C#, Java.

Основою програми є основні дисципліни навчальних планів за спеціальністю 122 «Комп’ютерні науки та інформаційні технології».

ПРОГРАМА ПИТАНЬ

1. Основи програмування

Основні поняття про алгоритмізацію. Основні етапи розв`язування прикладної задачі з використанням комп'ютера. Поняття математичної (інформаційної) моделі. Структурний підхід до побудови алгоритмів. Технологія програмування. Метод покрокової деталізації. Методи розроблення алгоритмів. Аналіз та оцінка алгоритмів.

Основні поняття про програмування. Поняття програми. Поняття про мови програмування. Класифікація мов програмування. Системи програмування. Поняття про інтерпретацію та компіляцію. Інтегровані середовища програмування. Поняття редактора, транслятора, налагоджувача. Інструментальне програмне забезпечення.

Мови програмування. Структура програми. Заголовок та розділи програми. Основні елементи даних: константи, змінні, вирази. Типи даних. Призначення та використання типів даних. Класифікація типів даних, оголошення їх в програмі. Прості і складні типи даних.

Оператори мови програмування. Призначення та використання операторів. Оператори надання значень, введення-виведення даних. Алгоритми розгалуженої структури та їх реалізація. Умовні оператори. Алгоритми циклічної структури та їх реалізація. Оператори повторення.

Структуровані типи даних. Масиви. Оголошення та використання структурованих даних типу масив. Розмір і розмірність масиву. Алгоритми роботи з числовими масивами. Пошук, заміна та перестановка елементів, визначення екстремальних значень та упорядкування масивів.

Рядки та символи. Оголошення та використання рядків і символьних масивів. Алгоритми роботи з рядками та символами. Стандартні процедури та функції для роботи з символьними даними.

Функцiї та процедури користувача. Організація підпрограм. Формальні та фактичні параметри. Механізми передачі до підпрограм параметрів-значень, параметрів-змінних та параметрів-констант. Методи: процедури та функції. Рекурсивні підпрограми.

Рекомендована література: [1-4].

2. Алгоритми і структури даних

Теорія складності алгоритмів. Побудова та аналіз алгоритмів. Класифікація алгоритмів. Абстрактні типи даних. Оцінка складності алгоритмів, класифікація алгоритмів за складністю. NP-повнота алгоритмів.

Основні структури даних та алгоритми їх оброблення. Вступ до структур даних. Класифікація структур даних. Прості структури даних. Арифметичні типи даних. Перерахований тип даних. Покажчики. Статичні структури даних. Класифікація алгоритмів сортування. Сортування за лінійний час. Швидке сортування. Сортування бульбашкою, вибіркою, вставками, розподілом, злиттям тощо (масиви, записи, черги, стеки, списки тощо). Динамічний розподіл пам'яті.

Табличні структури даних, графи, дерева та алгоритми їх оброблення. Таблиці. Графи. Алгоритми на графах. Дерева. Двійкові дерева. Пошукові алгоритми. Динамічне програмування, жадібні алгоритми. Метод сходження, рекурсивний, дерев розв’язку, з поверненням назад. Евристичні та ймовірнісні алгоритми на деревах і графах.

Рекомендована література: [5-7].

3. Математичний аналіз

Границя числової послідовності. Збіжна числова послідовність. Властивості границі. Арифметичні операції над збіжними послідовностями. . Монотонні послідовності. Число е, його ірраціональність. Часткові границі. Теорема Больцано-Вейєрштраса. Фундаментальна послідовність, критерій Коші.

Границя функції. Гранична точка множин. Ізольована точка. Часткова границя функції в точці. Операції над функціями, які мають границю в точці. Умова Коші й критерій існування границі функції в точці. Односторонні границі. Основні границі. Відношення еквівалентні функцій.

Неперервні функції та їх властивості. Операції над неперервними функціями. Елементарні функції. . Критерій Бера неперервності функції в точці. Класифікація точок розриву функції. Монотонні функції. . Основні теореми про неперервні функції.

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

Застосування похідної до дослідження функції. Правила Лопіталя розкриття невизначеностей. Формула Тейлора із залишковим членом у формі Пеано. Нелокальна формула Тейлора з залишковими членами у формі Коші й Лагранжа. Дослідження функцій на монотонність. Поняття локальних екстремумів функції. Необхідна та достатні умови екстремуму. Абсолютні екстремуми функції. Опуклі функції. Властивості опуклих функцій. Критерій опуклості функції. Нерівності, пов'язані з опуклими функціями. Точки перегину графіка функції. Асимптоти графіка функції. Побудова графіків функцій з повним дослідженням.

Первісна функції. Методи знаходження первісних. Елементарні методи інтегрування. Інтегрування раціональних функцій. . Інтегрування тригонометричних функцій. Інтегрування ірраціональних функцій методом раціоналізації. Означення інтеграла. Суми та інтеграли Дарбу. Критерій Лебега інтегровності функції за Ріманом. Властивості інтеграла Рімана. Основна теорема та основна формула інтегрального числення. Заміна змінної в інтегралі Рімана та формула інтегрування частинами. . Загальна схема застосувань інтеграла в задачах геометрії й фізики.

Диференціальне числення функцій багатьох змінних. Диференційоване відображення . Достатня умова диференційованості функції в точці. Диференціювання композиції функцій. Частинні похідні та диференціали вищих порядків. Формула Тейлора. Екстремум функції (означення, необхідні й достатні умови). Абсолютний екстремум. Теорема Банаха-Качіополлі про нерухому точку. Диференційованість оберненого відображення. Локальний умовний екстремум. Метод множників Лагранжа.

Рекомендована література: [8-10].

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

Теорія множин, відношення, відображення. Способи подання множин. Геометрична інтерпретація множин. Операції над множинами, алгебра множин. Потужність множин. Поняття відношення, подання відношень. Операції над відношеннями. Властивості бінарних відношень. Відношення еквівалентності, відношення порядку. Замикання відношень. Функціональні відношення. Види відображень.

Теорія графів, дерева. Способи подання графів. Основні терміни (петлі, кратні ребра, маршрут, довжина маршруту, ланцюг, цикл, підграф, зв’язність, степінь вершин). Ізоморфізм графів. Операції над графами (додавання та вилучення ребра, додавання та вилучення вершини, побудова двоїстого графа, об’єднання, з’єднання, (декартовий) добуток, композиція). Планарні графи, критерій планарності. Побудова обходу в глибину. Побудова обходу в ширину. Критерій ейлеровості графа. Побудова ейлерового циклу графа. Побудова гамільтонових циклів графа. Пошук найкоротших відстаней між вершинами за допомогою алгоритмів Форда – Беллмана та Дейкстри. Побудова остових дерев мінімальної ваги.

Комбінаторний аналіз. Правила добутку та суми. Розміщення та сполучення без повторень та їх властивості. Розміщення та сполучення з необмеженими повтореннями. Біном Ньютона. Властивості біноміальних коефіцієнтів. Поліноміальна формула. Формула включень та виключень. Застосування формули включень і виключень до задач про розміщення предметів. Поняття про рекурентні співвідношення. Числа Фібоначчі. Розв’язок лінійних рекурентних співвідношень із постійними коефіцієнтами.

Булева алгебра. Способи подання булевих функцій. Основні операції з булевими функціями. Основні тотожності алгебри булевих функцій. Тотожні перетворення булевих виразів. Нормальні форми зображення булевих функцій. Основні замкнені класи булевих функцій. Побудова поліному Жегалкіна. Теорема Поста про повноту. Мінімізація булевих функцій.

Основи теорії автоматів. Способи подання автоматів. Автомати-розпізнавачі та автомати-перетворювачі. Зв’язок між регулярними виразами та скінченними автоматами.

Рекомендована література: [11-14].

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

Основні поняття логіки. Пропозиційна логіка. Висловлювання та висловлювальні змінні. Побудова складних висловлювань. Операції над висловлюваннями. Класифікація висловлювань. Сумісність (несуперечливість) множини висловлювань. Логічне слідування на основі алгебри висловлювань. Числення висловлювань(алфавіт, формули, аксіоми, правила виведення).

Логіки 1-го порядку. Аксіоматичні системи логік 1-го порядку. Основні поняття. Квантори. Основні рівносильності формул логіки предикатів. Логічне слідування на основі логіки предикатів. Пренексна та сколемівська нормальні форми. Метод резолюцій і секвенційне числення для логік першого порядку.

Основи теорії алгоритмів. Інтуїтивне поняття алгоритму. Поліноміальні та неполіноміальні алгоритми. Уточнення поняття алгоритму. Обчислювальні функції. Частково-рекурсивні функції. Теза Черча. Машина Т’юрінга. Система Поста.

Рекомендована література: [15-18].

6. Алгебра та аналітична геометрія

Лінійна алгебра. Визначники другого та третього порядку, властивості визначників. Дії над матрицями. Обернена матриця. Теорема Кронекера – Капеллі. Розв’язок квадратної системи лінійних рівнянь. Матричний метод. Формули Крамера. Однорідні системи.

Елементи векторної алгебри. Скалярні і векторні величини. Лінійні операції над векторами. Проекція вектора на вісь. Лінійно залежні та лінійно незалежні системи векторів. Базис. Розклад вектора за базисом. Ортонормований базис на площині й у просторі. Вектор у декартовій системі координат. Векторний добуток двох векторів, його властивості, вираз у координатах. Площа трикутника, заданого координатами вершин. Мішаний добуток трьох векторів, його властивості, вираз у координатах. Об’єм тетраедра, заданого координатами вершин.

Елементи аналітичної геометрії. Подання фігур рівняннями та нерівностями. Рівняння лінії у полярних координатах. Параметричні рівняння лінії. Лінії та поверхні першого порядку. Векторні рівняння прямої та площини. Параметричні і канонічні рівняння прямої. Взаємне розташування двох площин і двох прямих у просторі. Кут між ними. Відстань від точки до площини та до прямої на площині. Криві другого порядку. Еліпс, гіпербола, парабола, їх канонічні рівняння та властивості. Приклади зведення рівнянь кривих другого порядку до канонічного вигляду.

Рекомендована література: [19-21].

Перелік питань для проведення вступного випробування з фахових дисциплін для категорій вступників згідно з Правилами прийому до КНУ імені Тараса Шевченка у 2017 році, які вступають до КНУ імені Тараса Шевченка на 2-й курс для здобуття ОР бакалавра на основі ОКР молодшого спеціаліста за спеціальністю 122 «Комп’ютерні науки та інформаційні технології».

Питання до білетів сформовано на основі цієї програми, яку абітурієнти отримують завчасно.

1. Задачі з програмування.

Знайти добуток непарних цифр заданого числа К.
Дано натуральне число N. Якщо воно є степенем числа 3, то вивести TRUE, у противному разі ‒ вивести FALSE.
Знайти кількість і суму шестизначних чисел, де сума першої, третьої, п’ятої цифр дорівнює подвоєнній сумі другої, четвертої, шостої, відповідно, цифр.
До масиву A, що складається з 30 елементів, записати найменші за абсолютною величиною числа, що діляться на 5, у записі яких є хоча б одна трійка.
У масиві А від’ємні елементи з непарними індексами замінити їх подвоєнними абсолютними значеннями. Підрахувати кількість таких замін.
У двовимірному масиві А замінити елементи, значення яких менше, ніж сума їх індексів, на квадрат цього значення. Підрахувати кількість таких замін у кожному рядку масива.
У двовимірному масиві А у парних рядках знайти максимальні елементи, а у непарних – мінімальні.
Дано рядок S. Вивести всі різні слова з рядка S, підрахувати кількість усіх слів та всіх різних слів у S.
Дано рядок S. Замінити у ньому всі подвоєнні букви на одинарні. Підрахувати кількість таких замін.
Дано рядок S
За заданими коефіцієнтами та знайти суму квадратів коренів кожного з рівнянь та
Використовуючи алгоритм Евкліда, знайти найменше спільне кратне заданих чотирьох чисел.

2. Завдання з дисципліни «Алгоритми та структури даних».

Написати програму, яка реалізує алгоритм сортування злиттям.
Написати програму, яка реалізує алгоритм швидкого сортування.
Написати програму, яка реалізує алгоритм сортування Шелла.
Написати програму, яка реалізує алгоритм сортування вставками.
Написати програму, яка реалізує пошуковий алгоритм.

3. Завдання з математичного аналізу.

Знайти границю: .
Знайти границю:.
Знайти границю:
Скласти рівняння дотичної і нормалі до кривої в точці:
Для функції обчислити : ,
Знайти ,де , .
Обчислити границю, застосувавши правило Лопіталя:
Знайти .
Знайти .
Обчислити інтеграл Рімана
Обчислити інтеграл Рімана
Знайти екстремум функції
Обчислити інтеграл Рімана.
Знайти умовні екстремуми функції при заданій умові: ,.

4.Завдання з дискретної математики.

Довести чи спростувати рівність .
На множині цілих чисел задано відношення . Визначити, чи є рефлексивним, антирефлексивним, симетричним, антисиметричним, транзитивним відношенням?
Знайти кількість та суму натуральних чисел від 1 до 1000, що діляться на 6 та не діляться на 5 и 12.
Знайти коефіцієнт при в розкладі бінома .
Знайти коефіцієнт при в розкладі полінома .
Знайти кількість -значних чисел, що діляться на 5, в запису яких є рівно 4 дев’ятки та хоч одна п’ятірка ( ).
Побудувати ейлерів цикл в графі V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; E={(1,4),(1,5),(1,7),(1,9),(2,4),(2,6),

(2,7),(2,8),(2,10),(2,11),(3,5),(3,8),(4,7),(4,9),(4,10),(4,11),(4,13),(4,15),(5,6),

(5,9),(6,8),(6,11),(6,12),(6,14),(7,10),(8,10),(9,11),(11,13),(11,15),(12,14)}.

Побудувати обхід у глибину та ширину в графі V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; E={(1,10),(1,11),(2,14),(2,15),(3,7),

(3,9),(3,14),(3,15),(4,6),(4,11),(4,12),(4,13),(5,7),(5,12),(5,13),(5,15),(6,7),

(6,11),(6,13),(6,14),(7,14),(7,15),(8,12),(8,15),(9,10),(9,14),(10,15),(12,15)}.

Не складаючи таблиці істинності класифікувати функцію
Побудувати поліном Жегалкіна для функції .

5. Завдання з математичної логіки та теорії алгоритмів.

Використовуючи метод резолюцій, з’ясувати, чи є сумісними формули:
Використовуючи метод резолюцій, з’ясувати, чи вірно:

Використовуючи секвенційне числення, з’ясувати, чи вірно:

література

Албахари Дж., Албахари Б. С# 5.0. Карманный справочник: Пер. с англ. — М. : ООО “ИД Вильямс”, 2013. — 288 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
Бичков О.С., Іванов Є.В. Основи програмування мовою C# // посилання на сайті факультету інформаційних технологій.
Гриффитс И. Программирование на C# 5.0- М. : Эксмо, 2014. — 1136 с.
Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: Пер. с англ.: Уч. пос.– М.: Издательский дом "Вильямс", 2000.– 384 с.
Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985. – 544 с.
Браунси К. Основные концепции структур данных и реализация в С++. – М.: Вильямс, 2002. – 320 с.
Ляшко І.І., Ємельянов В.Ф., Боярчук О.К Математичний аналіз. 2 частини – Київ, Вища школа, 1 частина 1992 – 495 с, 2 частина 1993 – 375 с.
Ляшко И.И., Боярчук А.К. и др. Математический анализ. 3 части – Киев, Вища школа, 1 часть 1983 – 495 с, 2 часть 1985 – 551 с.
Ляшко С.И., Боярчук А.К. и др. Сборник задач и упражнений по математическому анализу – Москва-Санкт-Петербург-Киев, Диалектика, 2001 – 432 с.
Ю.М.Бардачов, Н.А.Соколова, В.Є.Ходаков. Дискретна математика. – Київ.: Вища школа, 2002. – 287с.
М.Ф.Бондаренко, Н.В.Білоус, А.Г.Руткас. Комп’ютерна дискретна математика: Підручник. – Харків.: „Компанія СМІТ”, 2004. – 480с.
Ф.А.Новиков. Дискретная математика для программистов. – С.Петербург.: Питер, 2002. – 304с.
Ю.В.Капітонова та ін. Основи дискретної математики. – Київ.: Наукова думка, 2002. – 578 с.
Ф.М. Лиман. Математична логіка і теорія алгоритмів. ‒ Суми: Слобожанщина, 1998. – 152 с.
А.Н. Колмогоров, А.Г. Драгалин. Введение в математическую логику. ‒ М.: Изд-во Моск. ун-та, 1982. – 286 с.
М.С.Нікітченко, С.С.Шкільняк. Математична логіка та теорія алгоритмів. – Київ: ВПЦ Київський університет, 2008. – 528 с.
В.И. Игошин. Задачник-практикум по математической логике и теории алгоритмов. ‒ М.: Просвещение, 1986. – 159 с.
Дубовик В.П., Юрик І.І. Вища математика: Навчальний посібник -– Київ: Вища школа, 1993. – 648с.
Шкіль М.І. та ін. Вища математика: Підручник у 3 кн.: Кн.1 Аналітична геометрія з елементами алгебри. – К.: Либідь, 1994. – 280 с.
Іванова О.Г. та ін. Збірник задач з вищої математики (Лінійна алгебра, векторна алгебра, аналітична геометрія). – Миколаїв; 1989. – 50 с.

Критерії оцінювання

знань вступників з дисциплін фахового вступного випробування для зарахування на навчання на 2-й курс за ОКР «бакалавр» на основі ОКР молодшого спеціаліста за напрямом 6.040302 «Інформатика»

Максимальна сума балів – 100. Теоретична частина випробування – 40 балів, математичне завдання – 30 балів, задача з програмування ‒ 30 балів.

Рейтинг вступника формують як суму балів, набраних на фаховому вступному випробуванні, та середній бал диплому молодшого спеціаліста. Зарахування здійснюють відповідно до Правил прийому до КНУ імені Тараса Шевченка у 2017 році.

Голова фахової атестаційної комісії