Мiнiстерство освiти І науки, молоді та спорту України icon

Мiнiстерство освiти І науки, молоді та спорту України




Скачати 276.87 Kb.
НазваМiнiстерство освiти І науки, молоді та спорту України
Дата30.06.2012
Розмір276.87 Kb.
ТипДокументи

Мiнiстерство освiти і науки, молоді та спорту України

Сумський державний університет




ЗАТВЕРДЖУЮ

Ректор Сумського

державного університету


_____________А.В. Васильєв

"___" ___________20__ р.


ПРОГРАМА

ФАХОВИХ ВСТУПНИХ ВИПРОБУВАНЬ

при прийомі на навчвння за освітньо-кваліфікаційним
рівнем "спеціаліст", та "магістр"


за спеціальністю 7(8).04030201 «Інформатика»


СУМИ 2012

  1. ЗАГАЛЬНІ ПОЛОЖЕННЯ


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

Фахові вступні випробування проводяться як комплексний іспит, та складаються з комп'ютерного тестування і письмової частини.

Для тестування використовується прийнята в СумДУ система комп'ютеризованого тестування "Абітурієнт", яка відповідає всім необхідним вимогам вступних іспитів. Наповнення цієї системи тестами виконується кафедрою комп’ютерних наук після їх затвердження на засіданні кафедри.

На тестування виносяться наступні профільні дисципліни.

„Дискретна математика”, „Теорія систем та математичне моделювання” та „Теорія алгоритмів та математична логіка” є фундаментальними дисциплінами природничо-наукової підготовки.

"Програмування", "Аналіз даних", "Чисельні методи", "Системи та методи. прийняття рішень", "Бази даних та інформаційні системи" та "Комп'ютерні мережі" є фундаментальними циклу професійної та практичної підготовки.

"Теорія програмування", "Обчислювальна геометрія та комп'ютерна графіка", "Операційні системи", "Інтелектуальні системи", "Спеціалізовані мови програмування", "Криптологія", "Теорія інформації" та "Алгоритмічні мови" є фундаментальними дисциплінами за вибором ВНЗ.

Всі перелічені дисципліни є профілюючі для рішення наукових та інженерних прикладних проблем, пов'язаних з розрахунками і проектуванням інформаційних систем.

  1. ^

    АНОТАЦІЇ ТА КЛЮЧОВІ ПИТАННЯ З ДИСЦИПЛІНИ,
    ЩО ВИНОСИТЬСЯ НА ІСПИТ

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


Множини, операції над множинами. Відношення, операції над відношеннями. Спеціальні класи бінарних відношень: відношення еквівалентності та порядку. Елементарні булевськi функції, суперпозиція функцій. Табличний спосіб визначення функцій. Канонічні форми булевських функцій, способи побудови канонічних форм. Алгебра Жегалкiна, способи побудови поліномів Жегалкiна. Мiнiмiзацiя булевських функцій. Числення предикатів. Графи, способи визначення. Шляхи у графах, зв’язні графи. Ейлеpовi графи. Дерева, властивості дерев. Планарні графи. Алгебраїчні системи.
^

Теорія систем та математичне моделювання


Математичне та схематичне визначення системи. Математична класифікація систем. Основні проблеми теорії систем – ідентифікація систем, стійкість, спостережуваність, керованість. Перехідні та усталені процеси. Метод найменших квадратів для побудови неперервних та дискретних детермінованих моделей. Побудова моделей вхід-вихід та моделей в просторі станів. Еквівалентні моделі з матрицями Фробеніуса та Жордана. Критерії спостережуваності, керованості, стійкості системи. Специфікація входів та виходів системи. Модальне керування системами. Оцінювання станів системи. Побудова естиматора.Задача середньоквадратичної оптимізації. Оптимальне керування системами. Фільтр Калмана.
^

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


Основні означення та властивості алгоритмів. Принцип жадібного вибору та його реалізація в алгоритмах. Принцип “розподіляй та володарюй” та його реалізація в алгоритмах. Сортування вставками та його реалізація. Сортування злиттям та його реалізація. Сортування купою та його реалізація. Швидке сортування та його реалізація. Бінарні дерева , процедура пошуку. Удосконалені методи сортування. Бінарні дерева , процедура вставки. Бінарні дерева, процедура видалення. Алгоритм Крускала побудови остового дерева графа. Алгоритм Прима побудови остового дерева графа. Задача про максимальний потік в графах та алгоритми її розв’язку. Аналіз алгоритмів, асимптотичні позначення, час роботи. Червоно-чорні дерева та їх властивості. Класи складності алгоритмів, співвідношення між класами. Жадібні алгоритми та їх реалізація. Теорія матроїдів. Алгоритми пошуку найкоротших шляхів в графі. Коди Хаффмена.

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


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

Аналіз даних


Нормальний закон розподілу та його властивості. Розподіли Стьюдента, Фішера, ?2. Вибірковий метод. Генеральна сукупність, виборка та вимоги до неї. Статистичне оцінювання параметрів вибіркової послідовності. Основні статистичні характеристики. Довірчи інтервали для математичного сподівання, дисперсії. Перевірна статичних гіпотез. Основні поняття та визначення статистичної теорії прийняття рішень. F- критерій. Перевірка гіпотез про закон розподілу. Точний критерій Фішера. Критерій Студента. Перевірка гіпотезу про рівність середніх. Кореляційний аналіз. Типи залежностей. Основні характеристики парного кореляційного аналізу. Регресійний аналіз. Лінійний регресійний аналіз. Знаходження залежностей, що зводяться до лінійних. Множинний регресивний аналіз. Оцінка адекватності моделі експериментальним даним. Основи дисперсійного аналізу. Загальна ідея дисперсійного аналізу. Однофакторний аналіз.
^

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


Похибки, що виникають при розв’язуванні обчислювальних задач чисельними методами. Обумовленість та коректність обчислювальних задач. Ітераційні методи для розв’язку нелінійних рівнянь в різних просторах. Методи простої ітерації та Ньютона. Точні методи чисельного розв’язку СЛАР . Метод Гаусса та його модифікації – метод Жордана –Гаусса, Краута, Халецького, прогонки.

Ітераційні методи розв’язку СЛАР – простої ітерації та Зейделя. Ітераційні методи та метод градієнтного спуску для розв’язку нелінійних систем алгебраїчних рівнянь. Апроксимація функцій за методом найменших квадратів. Інтерполяція функцій поліномами та сплайнами. Чисельне диференціювання та інтегрування функцій. Методи Рунге-Кутта для розв’язку задачі Коші для звичайних диференціальних рівнянь. Різницеві схеми для розв’язку крайових задач для ЗДР. Метод сіток для чисельного розв’язку задач , пов’язаних з диференціальними рівняннями в частинних похідних. Апроксимація , стійкість та збіжність різницевих схем.
^

Системи та методи прийняття рішень


Види забезпечення систем прийняття рішень (СПР). Проблема синтезу СПР. Структура множини допустимих рішень. Методи багатокритеріальної оптимізації. Метод дерева рішень. Детермінований метод Белмана. Основні положення статистичної теорії прийняття рішень. Детерміновані теоретико-ігрові моделі прийняття рішень. Прийняття рішень за умов ризику. Байесівський підхід. Основні інформаційні характеристики СПР. Ентропійний критерій функціональної ефективності СПР. Основні принципи, концептуальні положення та визначення методу функціонально-статистичних випробувань. Базовий алгоритм навчання. Алгоритм екзамену. Оптимізація контрольних допусків на ознаки розпізнавання.
^

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


Проектування баз даних: моделювання прикладень с застосуванням IDF0- та DFD-методологій. Реляційна модель бази даних: функціональні залежності, алгоритм редукції Кодда, нормальні форми. Цілісність суттєвостей та посилань. Проектування логічної організації даних: зміст, терміни та приклади стандарту IDEF1X. Основи мови SQL: команди маніпулювання даними (DML), команди управління даними (DDL).
^

Комп'ютерні мережі


Типи мереж. Мережні функції Win32 API. Модель взаємодії відкритих систем. Рівні мережної архітектури. Стандарти нижніх рівнів мережної моделі. MAC-адреси. Режими передачі даних по каналу зв’язку. Мережні пристрої: концентратори, комутатори, маршрутизатори. Колізійний і широкомовний домени. Методи доступу до мережного середовища. Колізії в мережі. Метод CSMA/CD. Топології мереж. Мережі з шинною і кільцевою топологією. Мережі Ethernet. Протоколи мережного рівня. Протокол IP. Формат пакета IP. Протокол ARP. Утиліта traceroute. Протоколи транспортного рівня TCP і UDP. Формат пакета TCP. Установка і використання TCP-з’єднання. Класи IP-адрес, служба NAT. DNS-імена. Система Unix. Сокети в Unix. Послідовність викликів системних функцій при організації міжмашинної взаємодії через сокети.
^

Теорія програмування


Мови з точки зору теорії множин. Моделі. Універсальні алгебри. Операції над мовами. Граматики. Ієрархія Хомського. Продукції. Регулярні вирази і регулярні мови. Детерміновані і недетерміновані скінчені автомати. Побудова по регулярному виразу ?-недермінованого автомата і перетворення його в детермінований. Контекстно-вільні мови. Дерева розбору. Неоднозначність в граматиках. Автомати з магазинною пам’яттю. Верифікація програм. Передумови і постумови. Правила верифікації Хоара. Лямбда-вирахування. Редукція лямбда-виразів. Імперативне програмування. Функціональне програмування. Мова Lisp. Логічне програмування. Хорнівські вирази. Мова Prolog. Типи і підтипи. Правила утворення підтипів. Рекурсивні, рекурсивно-перераховні мови і мова діагоналізації.
^

Обчислювальна геометрія та комп'ютерна графіка


Базові визначення та поняття курсу комп’ютерної графіки. Алгоритми растрової графіки. Векторні та растрові графічні файли. Інтерполяція в графіці. Елементи аналітичної геометрії. Світ, колір, кольорові моделі. Мова програмування OpenGL.
^

Операційні системи


Концепція процесу: можливі стани процесу; перехід процесу із одного стану в другий; операції над процесами. Управління ресурсами: критичні сегменти програм; примітиви взаємо виключення; Алгоритм Деккера; семафори, двійкові семафори. Р- та V–операції Дейкстри; тупіки. Мультипрограмна операційна система. Переривання та їх обробка. Організація пам’яті в архітектурах ЕОМ. Адресний простір пам’яті. Ієрархія пам’яті. Стратегії управління оперативною пам’яттю. Поняття віртуальної пам’яті. Апаратні засоби підтримки віртуальної пам’яті. Сегментна стратегія організації оперативної пам’яті. Сегментно–сторінкова стратегія організації оперативної пам’яті. Управління файлами. Методи доступу. Виділення та утилізація зовнішньої пам’яті. Операційна система MS DOS: структура операційної системи MS DOS. Файлова система MS DOS. Операційні системі Windows на основі технології NT: Концепції Windows NT. Архітектура NT. Процеси та нитки. Алгоритм планування процесів та ниток.
^

Інтелектуальні системи


Поняття інтелект та інтелектуальна система. Відмінності між природним та штучним інтелектом. Штучний інтелект. Основні напрямки робіт та тенденції розвитку. Когнітивні процеси. Структура та функціонування смислового простору. Класифікація знань. Продукційне подання знань. Мережні моделі подання знань. Подання знань у вигляді фреймів. Нечітка модель подання знань. Подання знань у штучних нейронних мережах. Виведення у продукційних системах. Нечітке виведення. Процес навчання штучних нейронних мереж за алгоритмом Хебба. Процес навчання штучних нейронних мереж за алгоритмом Кохонена. Особливості реалізації та застосування генетичних алгоритмів. Кодування і декодування параметрів. ІЕІТ. Алгоритми оптимізації системи контрольних допусків. ІЕІТ. Алгоритми оцінки інформативності ознак розпізнавання.
^

Спеціалізовані мови програмування


Типи даних мови програмування Perl: скалярний, масиви скалярів, асоціативні масиви. Операції і вирази мови програмування Perl: арифметичні операції, операції відношення, логічні операції, операції конкатенації та повторення, операції складного присвоювання, посилання і операція розіменування, операція вибору, операція введення даних, операція here-document, Вбудовані змінні. Оператори: модифікатори простих операторів; модифікатори if, unless; Модифікатори while, until; модифікатор foreach; блоки і складені оператори; оператори розгалуження; оператори циклу while, until; Цикл for, foreach; команди управління циклами: last, next, команда redo. Регулярні вирази: мета символи; мета послідовності; операції з регулярними виразами; операція пошуку; операція заміни; операція транслітерації. Підпрограми і функції: визначення підпрограми і виклик підпрограми; локальні змінні у підпрограмах. CGI- програмування: HyperText Transfer Protocol; методи доступу: GET, HEAD, POST, PUT; поняття CGI-скрипта; типи запитів; змінні оточення; механізм генерації відгуку скриптом; HTML-форми.

Криптологія


Традиційні симетричні криптосистеми. Шифри перестановки: таблиці для шифрування (одинарна та подвійна перестановки); застосування магічних квадратів. Шифри простої заміни: полібіанський квадрат, система шифрування Цезаря (афінна система підстановок Цезаря, система Цезаря с ключовим словом); таблиці Трісемуса, біграмний шифр Плейфейра, криптосистема Хілла, система омофонів. Шифри складної заміни: шифр Гронсфельда; система шифрування Віжинера; шифр "подвійний квадрат" Уітстона; одноразова система шифрування; шифрування методом Вернама; роторні машини. Шифрування методом гаммірування.

Асиметричні криптосистеми. Концепція криптосистеми з відкритим ключем. Односпрямовані направлені функції. Криптосистема шифрування даних RSA; процедури шифрування та розшифрування в криптосистемі RSA; безпека та швидкодія криптосистеми RSA. Схема шифрування Поліга–Хеллмана. Схема шифрування Ель Гамаля. Комбінований метод шифрування.

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

Електронний цифровий підпис. Проблема аутентифікації даних. Односпрямовані хеш-функції. Односпрямовані хеш-функції на основі симетричних блочних алгоритмів. Алгоритми електронного цифрового підпису. Алгоритми цифрового підпису RSA, DSA.
^

Теорія інформації


Основні положення теорії інформації: Види інформації. Теорема дискретизації. Базові поняття теорії інформації. Кількість інформації. Ентропія джерела дискретних повідомлень. Властивості кількості інформації та ентропії. Умовна ентропія. Часткова та загальна умовні ентропії. Ентропія об’єднання двох джерел. Характеристики дискретних джерел повідомлень: продуктивність, швидкість передачі інформації, інформаційні втрати при передачі інформації по каналу зв’язку, пропускна здатність дискретного каналу. Теорема Шеннона про кодування дискретного джерела. Стиснення інформації: Оптимальні методи стиснення інформації: статистичні алгоритми Шеннона-Фано та Хаффмена. Метод блокування повідомлень. Блоковий код Хаффмена. Арифметичне кодування. Адаптивний (динамічний) алгоритм Хаффмена з упорядкованим деревом. Словарні алгоритми стиснення Зіва-Лемпела (LZ77, LZSS, LZ78, LZW). Завадостійке кодування інформації: Лінійні блокові коди. Код з перевіркою на парність. Ітеративний код. Способи завдання лінійних блокових кодів. Твірна та перевірна матриці лінійного блокового коду. Кодовий синдром. Синдромне декодування лінійних блокових кодів. Вага та відстань Хеммінга. Здатність кодів виявляти та виправляти помилки. Код Хеммінга. Поліноміальні коди: основні принципи. Циклічні коди: властивості циклічних кодів, твірний та перевірний поліноми, кодування циклічним кодом, поліном синдрому та виправлення помилок циклічним кодом, твірна та перевірна матриці циклічного коду, способи декодування циклічних кодів.
^

Алгоритмічні мови


Мова С: константи, змінні, масиви, вирази, арифметичні операції. Оператори присвоєння. Функції форматного введення/виведення. Стандартні математичні функції. Операції відношення та порівняння. Логічні операції. Операції зсуву, автозбільшення, автозменшення. Умовна операція. Оператори керування. Оператор перемикання switch. Оператори циклу while, do while, for. Складені оператори. Макровизначення. Функції: призначення, формат запису, прототипи, передача даних в функцію за допомогою фактичних параметрів. Зовнішні змінні. Передача даних в функцію за допомогою зовнішніх змінних. Передача в функцію імен інших функцій в якості фактичних параметрів. Покажчики. Покажчики та масиви. Адресна арифметика. Покажчики на функції. Структури: визначення, описання, призначення, ініціалізація. Вкладені структури, масиви структур. Обєднання. Стандартні бібліотеки мови С. Функції динамічного розподілу памяті malloc(), calloc(). Стандартні бібліотеки введення/виведення. Операції з файлами. Обробка матриць. Стандартні функції перетворення символьних рядків. Консольні функції. Макроси обробки символів та рядків. Робота з вікнами в текстовому режимі. Робота з графічним вікном.

  1. ^

    СТРУКТУРА ЕКЗАМЕНАЦІЙНИХ БІЛЕТІВ


Схема побудови тестів представлена на рис. 1.



Рисунок 1 — Схема побудови тестів

Матеріалом для тестів на "задовільно" є базові поняття циклів природничо-наукової підготовки, професійної та практичної підготовки зі спеціальності 7.04030201 "Інформатика". Тест організований, як вибір вірних відповідей з пропонованого списку.

Тести на "добре" будуються як вирішення типових завдань профільних курсів спеціальності 7.04030201 "Інформатика".

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

Приклад протоколу комп'ютерного тестування наведений в Додатку.
^

Приклади тестових запитань на "задовільно"

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


1. Яка операція над множинами називається одномісною:

  • об’єднання;

  • перетин;

  • доповнення.



^ 2. Які операції булеві:









^ 3. Які змінні називаються фіктивними для функції f():

  • Якщо вони набувають нульове значення.

  • Якщо від них не залежить значення функції.

  • Якщо f(0, 0,…,0)=0?
^

Теорія систем та математичне моделювання


1. Для дослідження системи на стійкість необхідно дослідити:

  • спектр матриці лінійного оператора математичної моделі з простором станів;

  • ранг матриці лінійного оператора;

  • перехідний та усталений режими роботи системи.



^ 2. Визначення спостережуваності для системи:

  • система, що дозволяє оцінити її параметри;

  • за відомими значеннями входів та виходів системи можна оцінити її стани;

  • спосіб оцінки параметрів системи.



^ 3. Призначення фільтра Калмана:

  • метод оцінювання станів та керування для стохастичних систем;

  • метод побудови математичної моделі системи;

  • метод визначення спектру матриці лінійного оператора.
^

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


1. Які принципи дозволяють розпізнати, чи визначає «жадібний» алгоритм оптимальне розв'язання стосовно даної задачі?

  • Принципи «розподіляй і пануй».

  • Принципи можливості розв'язання.

  • Принцип жадібного вибору і властивість оптимальності для підзадач.

  • Принципи достатності і необхідності.


^ 2. Що мають на увазі в теорії алгоритмів, коли говорять, що час виконання програми T(n) має порядок О(n2 ) ?

  •  c>0  n0> 0 : n  n0  T(n)  cn2

  •  c>0  n0> 0 : n  n0  T(n)  cn2

  •  c>0  n0> 0 : n  n0  T(n)  cn2

  •  c>0  n0> 0 : n  n0  T(n)  cn2


^ 3. Нехай заданий двомісний предикат P(x,y): «x любить y». Як за допомогою логіки предикатів подати фразу: «Кожну людини хтось любить»?

  • xyP(x,y).

  • xyP(x,y).

  • yxP(x,y).

  • xy(x,y).

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


^ 1. Чи відбудеться зациклювання у програмі:

    i:=2;

    repeat

    i:=i+1;

    until i=2



2. Які з наведених прикладів опису двовимірних масивів є некоректними:

  • var w: array[5,7] of Integer;

  • var mass: array[1..5],[1..7] of Real;

  • var a: array[1..5,1..7] of Real;



^ 3. Визначити, яке було значення змінної a до виконання фрагменту програми

if a<5 then a:=1 else if a>5 then a:=2 else a:=3 якщо після виконання a=3.

  • а=1

  • а=5

  • а=3

  • а=7
^

Аналіз даних


1. Виберіть правильні твердження, якщо випадкова величина має нормальний закон розподілу:

  • асиметрія =1, ексцесс=1;

  • асиметрія =0, ексцесс=0;

  • значення асиметрії та ексцессу залежать від параметрів розподілу.



^ 2. При випробуванні 2 верстатів вимірювали розмір отриманих деталей.

1-й верстат

Х1

Х2

Х3

Х4

Х5

2-й верстат

У1

У2

У3

У4




Щоб визначити, який верстат має більшу точність, необхідно:

  • порівняти Хср та Уср за допомогою t- тесту;

  • порівняти х та у за допомогою F- тесту;

  • використати тест Пірсона (2-тест).


^ 3. За інших рівних умов, якщо ми збільшуємо кількість незалежних змінних у регресії:

  • R2 збільшується;

  • R2 зменшується;

  • R2 може або збільшуватися, або зменшуватися;

  • немає ніякого впливу на R2.
^

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


1. Методи чисельного розв’язання нелінійних рівнянь:

  • метод прогону;

  • метод простої ітерації;

  • метод Зейделя.



^ 2. Методи чисельної апроксимації функції :

  • метод половинного поділу;

  • метод найменших квадратів;

  • метод градієнтного спуску.



^ 3. Апостеріорні методи дослідження похибки квадратурних формул:

  • метод Ньютона-Рафсона;

  • правило Рунге;

  • метод золотого перетину.
^

Системи та методи прийняття рішень


1. Назвіть переваги використання в системах прий­няття рішень байєсівського класифікатора:

  • дозволяє розпізнавати класи, що перетинаються;

  • дозволяє використовувати навчальні вибірки малого обсягу (40

  • пояснює механізм прийняття рішень;

  • відносна простота реалізації класифікатора.



^ 2. Який вид умовиводу реалізує метод резолюцій:

  • індуктивний;

  • дедуктивний;

  • доведення від супротивного;

  • за аналогією?



^ 3. Яка штучна нейромережа реалізує ітераційний процес навчання:

  • нейромережа Копфільда;

  • нейромережа Кохонена;

  • нейромережа Хеммінга;

  • нейромережа ADALINA.
^

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


1. Виберіть правильне продовження фрази "Інформаційні системи поділяються на 2 типи ...

  • OLTP та OLAP";

  • IDEF0 та DFD";

  • UML та SADT".



^ 2. Виберіть термін, не пов'язаний з нотацією DFD:

  • зовнішня сутність;

  • потік даних;

  • внутрішня сутність;

  • процес.


3. Назвіть базову структуру реляційної моделі даних:

  • функція;

  • залежність;

  • відношення;

  • ребро графа.
^

Комп'ютерні мережі


1. Які функції виконуються на транспортному рівні моделі OSI:

  • маршрутизація пакетів;

  • контроль черговості проходження компонент повідомлення;

  • шифрування повідомлень.



^ 2. Конфлікт (collision) у мережі Ethernet виникає:

  • за наявності в мережі адаптерів з однаковим номером;

  • при розриві в мережі;

  • одночасному початку передачі інформації двома станціями.


3. Протокол RIP використовує:

  • алгоритм пошуку Бойєра-Мура;

  • дистанційно-векторний алгоритм (DVA);

  • алгоритм стану зв’язків (LSA).
^

Операційні системи


1. До класу яких систем відносять Windows NT:

  • багатокористувацькі;

  • багатозадачні;

  • персональні?



^ 2. Укажіть задачі, які вирішує файлова система:

  • запуск програм;

  • зберігання карти розподілу файлів на диску;

  • зчитування файлів.



3. Який тип багатозадачності використовується у Windows XP:

  • що витісняє;

  • кооперативна?
^

Приклади тестових запитань на "добре"

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


1. Дайте визначення операції на множині S:

  • операцією на множині S називається будь-яка математична дія на цій множині;

  • операцією на множині S називається функція f, яка є відображенням виду - декартів добуток в який S входить n разів;

  • операцією на множині S називається відношення R, яке будується на множині S;

  • операцією на множині S називається підмножина декартового добутку.



^ 2. Нехай заданий двомісний предикат P(x,y) : «x любить y». Як за допомогою логіки предикатів подати фразу: «Кожну людини хтось любить» :

  • xyP(x,y);

  • xyP(x,y);

  • yxP(x,y).



^ 3. Що складає сигнатуру алгебраїчної системи:

  • множини й операції над ними;

  • відносини та їх властивості;

  • символьна мат логіка;

  • символи алгебраїчних операцій і відносин.
^

Теорія систем та математичне моделювання


1. Проблема представлення або ідентифікації системи:

  • виявлення і представлення в тих або інших формах законів динаміки систем;

  • наявність параметрів для побудови моделі;

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



^ 2. Стан системи:

  • однозначно визначає значення виходу в момент t;

  • виявляє причинні на слідки входу в момент t;

  • є визначальним при виході.



^ 3. За критерієм Калмана достатньою умовою повної керованості є:

  • rg(B, АВ,..., Аn-1B) = n;

  • rgV(k0, k1) = n-1;

  • rg(B, АВ,..., АnB) = n.
^

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


1. Що мають на увазі в теорії алгоритмів, коли говорять, що час виконання алгоритму Т(n) має порядок О(n2):

  •  c>0  n0> 0 : n  n0  T(n)  cn2;

  •  c>0  n0> 0 : n  n0  T(n)  cn2;

  •  c>0  n0> 0 : n  n0  T(n)  cn2;

  •  c>0  n0> 0 : n  n0  T(n)  cn2.



2. Яке співвідношення прийняте між класами задач P, NP і NPC у теорії алгоритмів:

  • ^ (P?NPC) NP;

  • (P=NP)  NPC;

  • (NP=NPC)  P;

  • (P=NPC)  NP;

  • (P?NP)  NPC.



3. Нехай заданий двомісний предикат P(x,y) : «x є дільником y». Оціните істинність виразу на множині натуральних чисел:

  • вираз хибний;

  • істинність установити не вдається;

  • вираз істиний.

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


1. Для запропонованого фрагмента програми, де a[i] – елемент масиву розмірності , визначити значення змінної D, якщо N=5, А=(-2, 3, 4, 6, -5):

d:=1;

for i:=1 to n do

if a[i]>0

then if a[i]/3=trunc(a[i]/3)

then d:=d*a[i];


2. Для запропонованого фрагмента програми, де a[i] – елемент масиву розмірності , визначити значення змінних max і S, якщо N=5, А=(-2, 8, 0, 8, -3):

s:=1; max:=a[1];

for i:=n downto 2 do

if max
then begin max:=a[i]; s:=1 end

else if max=a[i] then s:=s+1.


3. Для запропонованого фрагмента програми визначити значення S, якщо N=125:

while n>0 do begin

k:=n mod 10 ;

s:=s+k;

n:=n div 10;

end;
^

Аналіз даних


1. Для даної вибірки (файл 04_AD_1.xls) обчислити за допомогою можливостей Excel:

  • середнє значення;

  • виправлену дисперсію;

  • виправлене середнє квадратичне відхилення.



^ 2. Для даної вибірки (файл 04_AD_1.xls) обчислити за допомогою можливостей Excel:

  • моду;

  • медіану;

  • ассиметрію

  • ексцесс



^ 3. У таблиці (файл 04_AD_3.xls) наведена динаміка зростання прибутку фірми за останні n років у відсотках до базового року

Розрахувати а0 та а1 для регресії y = а0 + а1x, використовуючи функцію ЛГРФПРИБЛ. Записати отримане рівняння (з точністю до сотих).
^

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


1. Розв’язати нелінійне рівняння 2x+5x-3=0 з точністю =0,0001.


2. Розв’язати систему лінійних рівнянь




3. Обчислити інтеграл з точністю .
^

Системи та методи прийняття рішень


1. Знайдіть оптимальну стратегію за максимінним критерієм для матриці виграшів, заданої таблицею.












1

11

7



10

6

8



0

15

6

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










0,40

0,60



10

8



2

12



0

15

3. Для гіперсферичного класифікатора визначте належність класу розпізнавання , для якого відомі еталонний вектор-реалізація xm = <111111111111­111> і оптимальний радіус , таких векторів-реалізацій:


^

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


1. Виберіть правильне продовження фрази "Складений ключ - це ...

  • атрибут або комбінація атрибутів, чиї значення одно­значно ідентифікують кожний екземпляр";

  • мінімальна комбінація атрибутів, чиї значення однозначно ідентифікують кожний екземпляр";

  • ключ-кандидат, який обраний як унікальний ідентифікатор".



^ 2. Яка підмножина даних повертається SQL-командою

SELECT Tn, AdT

FROM Tenant

WHERE Tn NOT IN (SELECT Ow FROM Owner):

  • дані Owner, яких немає в Tenant;

  • однакові дані таблиць;

  • порожня;

  • дані Tenant, яких немає в Owner.



^ 3. Виберіть правильне продовження фрази "Цілісність — це ...

  • механізм запобігання руйнації даних";

  • достовірність інформації в базі даних";

  • коректний зв'язок вторинних ключів".
^

Комп'ютерні мережі


1. Який біт встановлений у першому повідомленні будь-якого TCP-з'єднання:

  • ACK;

  • SYN;

  • FIN;

  • PSH.


^ 2. Які з наведених мереж використовують кільцеву топологію:

  • Ethernet;

  • Fast Ethernet;

  • Token Ring;

  • Token Bus;

  • FDDI.



3. Сокетом називається комбінація:

  • IP-адреси і номера порту;

  • IP-адреси і маски підмережі;

  • MAC-адреси і IP-адреси;

  • DNS-імені і IP-адреси.
^

Операційні системи


1. Зазначте, в якому із станів операційній системі доступний контекст процесу:

  • блокування;

  • виконання;

  • готовність.



^ 2. Для виконання чого Windows кожного разу створює нову VM:

  • Windows-прикладення;

  • DOS-прикладення;

  • Windows-потоку.



3. Виправить помилку в описі алгоритму обробки натиснення кнопки миші:

    1. контролер миші змінює рівень напруги на JRQ;

    2. це зміна напруги поступає на схему контролера переривання;

    3. контролер переривання повідомляє процесор про необхідність обслужити мишу;

    4. ЦП перериває роботу і завантажує необхідну програму обробки переривання.
^

Приклади білетів на "відмінно"


1. Зростаюча послідовність

Нехай є послідовність чисел . Відомо, що числа цілі, та за модулем не перебільшують 30000. Необхідно з цієї послідовності викреслити таку мінімальну кількість чисел , щоб числа які залишились, утворювали зростаючу послідовність. Змінювати порядок розміщення елементів послідовності забороняється.

^ Вхідні дані зчитуються з файлу seq.in, в якому числа записані в одному рядку через пропуск.

У результаті необхідно вивести на екран кількість закреслених чисел відповідно до умов задачі.

^ Приклад:

5 1 2 –1 3

Відповідь: 2

Приклад:

1 3 2 4 5 2 3

Відповідь: 3


2. Трикутники

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

^ Вхідні дані зчитуються з файлу seq.in, який складається з двох рядків. У першому рядку через пропуск записано 6 чисел: три вершини трикутника заданих та координатою відповідно. У другому рядку задано інший трикутник.

Приклад:

1 3 4 5 6 1

2 –1 9 5 13 2

Відповідь: 2


3. Клітинки

У файлі maze.in задано поле розміру , який складається з символів “.” (крапка) та символу “#” (решітка) за умов, що .

Стіною будемо називати клітинку, помічену символом “#”, стіни можуть з'єднуватись одним з боків. Необхідно визначити, скільки вільних клітин оточено стіною. Вільною клітиною вважається клітинка, що помічена символом крапка ".".

^ Вхідні дані. У першому ряду вхідного файлу записано числа M та N через пропуск, які визначають розмір поля. Далі йде M рядків по N символів, записаних підряд.

^ Вихідні дані. На екран необхідно вивести кількість вільних клітин, які оточені стіною.

Приклад:

6 10

..........

...######.

...#....#.

...#....#.

...######.

..........

Відповідь: 8

Приклад:

6 10

..........

......####

......#.#.

......#...

......####

..........

Відповідь: 5
  1. ^

    КРИТЕРІЇ ОЦІНЮВАННЯ ВІДПОВІДЕЙ


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

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

Бали

Оцінка "відмінно" виставляється абітурієнту, який показав творчі уміння та високу теоретичну підготовку, вміє використовувати отримані знання для розв’язку практичних задач та вміє користуватися довідковою літературою.

Кількість балів за правильні відповіді > 24 але  27

Оцінка "добре" виставляється абітурієнту, який виявив високий рівень теоретичних знань, які він набув при вивченні профільних курсів, а також може використовувати ці знання на практиці.

Кількість балів за правильні відповіді > 12 але  24

Оцінка «задовільно» виставляється абітурієнту, який упевнено відтворює базові поняття профільних курсів.

Кількість балів за правильні відповіді >10 але  12

Оцінка «достатньо» виставляється абітурієнту, який упевнено відтворює базові поняття профільних курсів і при цьому робить певну кількість помилок.

Кількість балів за правильні відповіді >5 але  10



  1. ^

    СПИСОК ЛІТЕРАТУРИ


  1. Гаращенко Ф.Г., Матвієнко В.Т. Диференціальні рівняння. – К.: ВПЦ Київського університету, 2002. – 176 с.

  2. Ковалюк Т.В. Основи програмування — К.: БХВ, 2006.

  3. Глушков В.М. и др. Алгебра. Языки. Программирование. – К.: Наукова думка, 1989.

  4. Кабальський В.С., Токунова Т.В. Теорія ймовірностей і математична статистика у прикладах і задачах: Навчальний посібник. - Алчевськ : ДГМІ, 2002.

  5. Айвазян С.А., Енюков И.С., Мешалкин Л.Д., Прикладная статистика: исследование зависимостей. — М: Финансы и статистика, 1985.

  6. Фельдман Л. П., Петренко А. І., Дмитрієва О. А. Чисельні методи в інформатиці. — К.: БХВ, 2006.

  7. Бахвалов Н.С., Жидков Н.П., Кобельков Г.Н. Численные методы. – М.: Наука, 1987.

  8. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: Учеб. пособие. - С-Пб : Питер, 2001.

  9. Вычислительные сети и сетевые протоколы/ Д. Дэвис, Д. Барбер, У. Прайс, С. Соломонидес. — М.: Мир, 1982.

  10. Бєлов В.В., Воробйов Е.М., Шаталов В.Е. Теорія графів — М.: Вища школа, 1978.

  11. Григоренко Я.М. Обчислювальні методи в задачах прикладної математики. –К.: Либідь, 1995.

  12. Боровиков А.А. Курс теории вероятности. – М.: Наука, 1976. – 352 с.

  13. Дороговцев А.Я. Математичний аналіз: Підручник. — К.: Либідь, 1993.

  14. Кудрявцев В.А., Демидович Б.П. Краткий курс высшей математики. - 6-е изд. - М.: Наука, 1986.

  15. Гихман И.И., Скороход А.В., Ядренко М.И. Теория вероятности и математическая статистика - К.: Вища школа, 1979.

  16. Гмурман В.Е.Теория вероятностей и математическая статистика. — М.: Высшая школа, 1977.

  17. Капітонова Ю.В., Кривий С.Л. та ін. Основи дискретної математики. – К.: Наукова думка, 2002.

  18. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика — К.: БХВ, 2006.

  19. Курош А.Г. Курс высшей алгебры. – М.: Наука, 1968.

  20. Шеховцов В.А. Операційні системи. — К.: БХВ, 2006.

  21. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Физматлит, 2001.

  22. Краснопоясовський А.С. Класифікаційний аналіз даних. — Суми: Вид-во СумДУ, 2002.

  23. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів: Навчальний посібник. – К.: ВПЦ Київського університету, 2003.

  24. Ляшко И.И., Макаров В.Л., Скоробогатько А.А. Методы вычислений. – К.: Наукова думка, 1976.

  25. Назаренко Л.Д.Елементи обчислювальної математики: Конспект лекцій з курсу “Обчислювальна математика”. – Суми: СумДУ. –2001.

  26. Нікітченко М.С., Шкільняк С.С. Математична логіка: Навчальний посібник. – К.: ВПЦ Київського університету, 2003. – 120 с.

  27. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. – К.: Абрис, 1999.

  28. Сироджа И.Б. Принятие решений: Конспект лекций. —Харьков: Изд-во ХАИ,1992.

  29. Системи підтримки прийняття рішень/ Microsoft. — К.: — БХВ, 2007.

  30. Черноруцкий И.Г. Методы принятия решений. – СПб.: БХВ-Петербург, 2005.

  31. Хусаінов Д.Я., Бичков О.С. Диференціальні рівняння. – К.: ВПЦ Київського університету, 2001.

  32. Чекалов А.П. Базы данных: от проектирования до разработки приложений.   СПб.: БХВ-Петербург, 2003.

  33. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. – М.: Наука, 1966.

  34. Пасічник В. В., Резніченко В. А. Організація баз даних та знань. — К.: БХВ, 2006.

  35. Шкільняк С.С. Математична логіка. Приклади і задачі: Навчальний посібник. – К.: ВПЦ Київського університету, 2002.

  36. Шкільняк С.С. Теорія алгоритмів. Приклади і задачі: Навчальний посібник. – К.: ВПЦ Київського університету, 2003.



Голова атестаційної комісії Проценко С.I.


Затверджено на засіданні приймальної комісії протокол № ___ від _____


Відповідальний секретар приймальної комісії Колесник М.М.

Додаток

Приклад протоколу комп'ютерного тестування





Схожі:

Мiнiстерство освiти І науки, молоді та спорту України iconОбразец мiнiстерство освiти І науки, молоді та спорту україни сумський державний університет центр заочної, дистанційної та вечірньої форм навчання

Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни чернiвецький нацiональний унiверситет iменi Юрiя Федьковича Географiчний факультет
Робоча програма складена на основі освітньо професійної програми вищої освіти за професійним спрямуванням „Географія”
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни сумський державний університет центр заочної, дистанційної та вечірньої форм навчання кафедра комп’ютерних наук
«Комп’ютерне багатофакторне регресійне моделювання залежності між доходами, заощадженнями та цінами»
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни державний вищий навчальний заклад «донецький національний технiчний унiверситет» державний вищий навчальний заклад
Державне управлiння охорони навколишнього природного середовища в донецькiй областi
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти I науки україни
України від 23. 08. 06 р. N 631 ( v0631290-06 ) Про вжиття вичерпних заходів, спрямованих на дотримання законодавства щодо
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни східноукраїнський національний університет імені володимира даля
Бюл. Вак №5 2010 р.), (Бюл. Вак №3 2010 р.), (Бюл. Вак №11 2010 р.), (Бюл. Вак №7 2011 р.) в яких можуть публікуватися результати...
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни східноукраїнський національний університет імені володимира даля
Бюл. Вак №5 2010 р.), (Бюл. Вак №3 2010 р.), (Бюл. Вак №11 2010 р.), (Бюл. Вак №7 2011 р.) в яких можуть публікуватися результати...
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни східноукраїнський національний університет імені володимира даля
Бюл. Вак №5 2010 р.), (Бюл. Вак №3 2010 р.), (Бюл. Вак №11 2010 р.), (Бюл. Вак №7 2011 р.) в яких можуть публікуватися результати...
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство освiти І науки, молоді та спорту україни східноукраїнський національний університет імені володимира даля
Бюл. Вак №5 2010 р.), (Бюл. Вак №3 2010 р.), (Бюл. Вак №11 2010 р.), (Бюл. Вак №7 2011 р.) в яких можуть публікуватися результати...
Мiнiстерство освiти І науки, молоді та спорту України iconМiнiстерство охорони здоров'я україни буковинський державний медичний університет кафедра педіатрії та дитячих інфекційних хвороб
Програми з пропедевтичної, факультетської I госпiтальної педiатрiї для студентiв вищих медичних навчальних закладiв III-IV рiвнiв...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи