Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Перелік питань, що виносяться на вступний іспит

Скачати 103.57 Kb.

Перелік питань, що виносяться на вступний іспит




Скачати 103.57 Kb.
Дата конвертації28.05.2017
Розмір103.57 Kb.
ТипПротокол

Затверджено на засіданні

Вченої ради факультету кібернетики



Протокол № 8 від 29 лютого 2016 р.

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

з математики та інформатики

Спеціальність “ Інженерія програмного забезпечення ” (магістр)

Освітня програма “Програмне забезпечення систем”

Вища математика

  1. Числова послідовність та її границя. Монотонні послідовності, теорема Вейєрштрасса

  2. Неперервність функції в точці у розумінні Гейне й Коші. Класифікація точок розриву функції.

  3. Означення похідної функції. Односторонні похідні. Критерій диференційовності функції.

  4. Основні теореми диференціального числення (Ролля, Дарбу, Лагранжа, Коші)

  5. Поняття локальних екстремумів функції.

    Похідна́ - основне поняття диференціального числення, що характеризує швидкість зміни функції. Визначається як границя відношення приросту функції до приросту її аргументу коли приріст аргументу прямує до нуля (якщо така границя існує).

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

    Необхідні та достатні умови екстремуму. Абсолютні екстремуми функції.

  6. Поняття первісної та первісної в широкому розумінні.

  7. Означення інтеграла Рімана як границі інтегральних сум.

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

    Суми та інтеграли Дарбу.

  8. Похідна у напрямі, частинні похідні, градієнт функції, їх властивості.

    Градіє́нт, Ґрадіє́нт - міра зростання або спадання в просторі якоїсь фізичної величини на одиницю довжини.

    В математиці, часткова похідна (частинна похідна) функції кількох змінних - це похідна по одній із змінних, причому інші змінні приймаються як константи. Часткові похідні використовуються у векторному численні та диференційній геометрії.

    Повний диференціал. Функції декількох змінних. Диференціал, частинні похідні.

  9. Числові ряди. Збіжність і сума ряду. Ознаки збіжності додатних числових рядів.

  10. Функціональні ряди. Область збіжності. Рівномірна збіжність.

  11. Тригонометричні ряди Фур’є. Розвинення функцій в ряд Фур’є.

  12. Диференціальні рівняння першого порядку. Задача Коші.

  13. Диференціальні рівняння вищих порядків. Задача Коші.

  14. Лінійні диференціальні рівняння зі сталими коефіцієнтами.

    Задача Коші - одна з основних задач теорії диференціальних рівнянь - полягає в пошуку розв'язку (інтеграла) диференціального рівняння, що задовольняє початковим умовам (початковим даним).

    Ознаки збіжності рядів - ознаки, що доводять або спростовують збіжність числового ряду. Нехай дано ряд

    Рівномірна збіжність послідовності функцій - властивість послідовності f n : X → Y :X\to Y} , де X - довільна множина, Y = ( Y , d ) - метричний простір, n = 1 , 2 , … збігається до функції (відображення) f : X → Y , що означає, що для будь-якого ε > 0 існує такий номер N ε } , що для всіх номерів n > N ε } і всіх точок x ∈ X виконується нерівність

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



Література

  1. Ляшко І.І., Ємельянов В.Ф., Боярчук О.К Математичний аналіз. 2 частини – Київ, Вища школа, 1 частина 1992 – 495 с, 2 частина 1993 – 375 с.

  2. Ляшко С.И., Боярчук А.К. и др. Сборник задач и упражнений по математическому анализу – Москва-Санкт-Петербург-Киев, Диалектика, 2001 – 432 с.

  3. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. – М., Наука, Т.1, 1966. – 607 с., Т.2, 1966. – 800 с., Т.3, 1966. – 656 с.

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


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

  1. Основні рівняння прямої та площини у просторi.

  2. Критерій сумісності системи лінійних рiвнянь.

  3. Лінійна залежність та ранг системи векторів, методи обчислення рангів.

    Пряма́ - одне з основних понять геометрії. При систематичному викладі геометрії пряма лінія зазвичай приймається за одне з вихідних понять, яке лише опосередковано визначається аксіомами геометрії. Якщо основою побудови геометрії служить поняття відстані між двома точками простору, то пряму лінію можна визначити як лінію, шлях уздовж якої дорівнює відстані між двома точками.

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

    Ранг матриці - порядок найбільших відмінних від нуля мінорів цієї матриці (такі мінори називаються базисними).



  4. Лінійні оператори скінченно-вимірних просторів та їх матриці.

  5. Власні вектори та власні числа лінійних операторів.

  6. Лінійні оператори простої структури.

  7. Лінійні оператори дійсних евклідових просторiв.

  8. Зведення квадратичних форм до канонічного вигляду.

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

    Лінійним відображенням (лінійним оператором, лінійним перетворенням) - називається відображення векторного простору V над полем K в векторний простір W (над тим же полем K )

    Квадрати́чна фо́рма - однорідний многочлен другого степеня від однієї чи декількох змінних.



  9. Основна теорема про подiльність многочленів.

  10. Жорданові нормальні форми матриць.

Література

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

  2. Мальцев А.И. Основы линейной алгебры. – М.: Наука, 1970.

  3. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. – М.: Наука, 1964.


Дискретна математика та системи штучного інтелекту

  1. Множини, операції на множинах, алгебра множин, основні закони.

    Конститу́ція (лат. constitutio - установлення, устрій, порядок) - основний державний документ (закон), який визначає державний устрій, порядок і принципи функціонування представницьких, виконавчих та судових органів влади, виборчу систему, права й обов'язки держави, суспільства та громадян.

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

    Шту́чний інтеле́кт (англ. Artificial intelligence, AI) - розділ комп'ютерної лінгвістики та інформатики, що займається формалізацією проблем та завдань, які нагадують завдання, виконувані людиною.



  2. Зліченні та незліченні множини.

    Зліченна множина - в теорії множин така нескінченна множина, елементи якої можна занумерувати натуральними числами. Множина, яка не є зліченною, називається незліченною. Таким чином, будь-яка множина є або скінченною, або зліченною, або незліченною.

    Теореми Кантора.

  3. Вiдношення та їх властивості. Відношення еквівалентності, часткового та лінійного порядку, функціональні відношення. Відображення, основні різновиди відображень та їх властивості.

  4. Графи, їх різновиди. Операції на графах та їх властивості. Ейлерові та гамільтонові графи.

  5. Зв’язність та компоненти зв’язності графів. Методи перевірки зв’язності графів. Планарність графів та критерії планарності.

  6. Сполуки, перестановки i розміщення. Поліноміальна теорема.

  7. Канонічні (нормальні) форми булевих функцій.

    Бу́лева фу́нкція (функція алгебри логіки, логічна функція) - в дискретній математиці відображення Bn → B, де B = - булева множина.

    Алгебра Жегалкiна.

  8. Повнота i замкненість систем булевих функцій. Теорема Поста.

    Критерій Поста - одна з центральних теорем математичної логіки, описує необхідні та достатні умови функціональної повноти множини булевих функцій. Був сформульований американським математиком Емілем Постом в 1921.



  9. Подання знань за допомогою логіки предикатів.

  10. Використання методу резолюцій в системах штучного інтелекту.

  11. Семантичні мережі.

  12. Фрейми.

Література

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

  2. Романовский И.В. Дискретный анализ. – С.Петербург, СПб-ВНV, 2003.

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

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

    Дискре́тна матема́тика - галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру.

    , Наукова думка, 2002.

  4. Кривий С.Л. Дискретна математика. – Чернівці:Букрек, 2014.

  5. Чень Ч., Ли Р. Математическая логика и автоматизация доказательств. – М., Наука, 1983.

  6. Верещагин Н.К., Шень А. Языки исчисления. – М.: МЦНМО, 2002.


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

  1. Основні поняття логіки. Поняття предиката, висловлювання. Пропозиційна логіка (логіка висловлювань).

    Теорія алгоритмів (англ. Theory of computation) - окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття.

    Чи́слення висло́влень (логіка висловлень, пропозиційна логіка, англ. propositional logic) - формальна система в математичній логіці, в якій формули, що відповідають висловленням, можуть утворюватись шляхом з'єднання простих висловлень із допомогою логічних операцій, та система правил виводу, які дозволяють визначати певні формули як «теореми» формальної системи.

    Пропозиційне числення, його несуперечність та повнота.

  2. Логіки 1-го порядку, їх мови та семантичні моделі. Мова арифметики. Виразність предикатів, множин, функцій. Істинність та виконуваність, логічний наслідок, логічна еквівалентність.

  3. Аксіоматичні системи логік 1-го порядку (теорії 1-го порядку). Несуперечність, повнота, розв’язуваність теорій 1-го порядку.

  4. Теорема Гьоделя про повноту. Теорема компактності, її наслідки. Категоричність. Теореми Гьоделя про неповноту, їх значення.

  5. Методи автоматизації доведень. Метод резолюцій для логіки висловлювань.

  6. Теорема Ербрана. Підстановка та уніфікація. Метод резолюцій для логік 1-го порядку.

  7. Секвенційні числення логік 1-го порядку, їх коректність та повнота.

  8. Поняття алгоритму. Формальні моделі алгоритмів (машини Тьюрінга, машини Поста, нормальні алгорифми Маркова). Частково рекурсивні, рекурсивні, примітивно рекурсивні функції.

    Правило резолюцій - це правило висновку, що сходить до методу доказу теорем через пошук протиріч; використовується в логіці висловлювань і логіці предикатів першого порядку. Правило резолюцій, що застосовується послідовно для списку резольвент, дозволяє відповісти на питання, чи існує у вхідній множині логічих виразів протиріччя.

    Нормальні алгоритми (нормальні алгоритми) - вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритму введене радянським математиком А. А.

    Машина Поста (див.Еміль Пост) - це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, хоча зовнішньо проста, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення.

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

    Теза Чорча.

  9. Нумерації. s-m-n-теорема. Універсальні функції. Універсальна частково-рекурсивна функція, універсальна машина Тьюрінга.

    Маши́на Тю́рінга - математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост.



  10. Рекурсивні та рекурсивно перелічимі множини, рекурсивні та частково рекурсивні предикати.

  11. Алгоритмічна розв’язуваність, часткова розв’язуваність та нерозв’язуваність масових проблем. Нерозв’язуваність проблем зупинки та самозастосовності, наслідки. Теорема Райса.

  12. Оцінка ефективності алгоритмів. Функції складності за часом та за пам’яттю. Асимптотична складність.

  13. Поняття звідності. Класи складності задач. P-повні та NP-повні проблеми.

Література

  1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.

  2. Клини С. Математическая логика. – М.: Наука, 1973.

  3. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.

  4. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. К.

    Математи́чна ло́гіка - розділ математики, що вивчає мислення за допомогою числень, застосовуючи математичні методи та спеціальний апарат символів. Предметом математичної логіки є математичні теорії в цілому, які вивчаються за допомогою логіко-математичних мов.

    : ВПЦ – Київський ун-т, 2008.

  5. Кривий С.Л., Провотар О.І. Вступ до некласичної математичної логіки. К.ВПЦ. Київський ун-т, 2010.

  6. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.

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

  8. Шкільняк С.С. Tеорія алгоритмів. Приклади й задачі. – К.: ВПЦ Київський ун-т, 2012.

  9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

  10. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. – М.: Мир, 1982.


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

  1. Задача лiнiйного програмування. Її властивостi.

  2. Критерiй оптимальностi базисного розв’язку задачі лінійного програмування.

    Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) - метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі чиї вимоги представлені через лінійні відношення.



  3. Двоїсті задачі лінійного програмування. Теореми двоїстостi.

  4. Задача опуклого програмування. Теорема Куна-Такера.

  5. Метод найшвидшого спуску.

  6. Оптимальнi чистi стратегії у матричній грi. Теорема про мінімакс.

Література

  1. Попов Ю.Д., Тюптя В.І., Шевченко В.І., Методи оптимізації. – К.

    Оптиміза́ція (англ. optimization, optimisation) - процес надання будь-чому найвигідніших характеристик, співвідношень (наприклад, оптимізація виробничих процесів і виробництва). Задача оптимізації сформульована, якщо задані: критерій оптимальності (економічний - тощо; технологічні вимоги - вихід продукту, вміст домішок в ньому та ін.)

    : Абрис, 1999.

  2. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986.


Організація баз даних та знань

  1. ER – модель.

  2. Класифікація запитів.

  3. Реляційна модель Кодда. Реляційна алгебра.

  4. Функціонально повна залежність. 2-нормальна форма (2НФ).

  5. Мінімальна структура функціональних залежностей.

  6. Аксіоми Армстронга.

  7. Третя нормальна форма та третя нормальна форма Бойса-Кодда.

    Реляці́йна алгебра - відгалуження логіки першого порядку, множина відношень замкнених операторами. Оператори застосовуються до відношень, в результаті застосування отримується нове відношення.

    Нормальна форма Бойса - Кодда (або НФБК, або БКННФ, або 3.5НФ) - нормальна форма використовна в нормалізації баз даних. Це трошки сильніша версія третьої нормальної форми (3НФ). Таблиця знаходиться в НФБК тоді і тільки тоді, коли для кожної її нетривіальної функціональної залежності X → Y, X це суперключ - тобто, X або потенційний ключ, або його надмножина.



  8. Стратегії розподілу даних в розподілених базах даних.

  9. Багатозначні залежності. 4-нормальна форма.

Література


  1. Дейт К. Введение в системы баз данных. – М., Вильямс, 2000.

  2. Ульман Дж. Основы баз данных. – М., Статистика, 1982.

  3. Дрибас В.П. Основы теории реляционных баз данных. – Минск, 1982.


Архітектура ЕОМ та програмування

  1. Основні функціональні елементи ЕОМ. Дешифратор, шифратор, регістри зберігання и зсуву, лічильник, мультиплексор. Місце та роль цих елементів при побудові різноманітних вузлів та пристроїв ЕОМ.

  2. Подання даних у пам’яті комп’ютера. Біти, байти й слова, подання числових даних і системи числення, системи з фіксованою й плаваючою крапкою, подання нечислових даних (коди символів, графічні дані).

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



  3. Принципи фон Неймана організації ЕОМ і її основних функціональних блоків. Алгоритм виконання інструкції (команди) в машині фон Неймана, пристрій керування: вибірка інструкцій, декодування й виконання, набір інструкцій і види інструкцій (маніпуляція даними, керування, ввід-вивід).

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

  5. Аспекти оцінки та класифікація мов програмування.

  6. Типи даних. Скалярні та структуровані дані. Абстрактні типи даних.

  7. Підпрограми та параметри підпрограм. Виклик та використання результату. Рекурсія.

  8. Поняття про структурне програмування.

  9. Лінійні динамічні структури даних.

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

    Структурне програмування - методологія програмування (модель конструювання програмного забезпечення) запропонована в 1970-х роках голландським науковцем Дейкстрою (Edsger Wybe Dijkstra), була розроблена та доповнена Ніклаусом Віртом.

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

    Списки, стеки та черги. Операції, послідовні та зв’язані способи збереження.

  10. Дерева. Представлення та проходження. Бінарні дерева.

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

    Рекурсивні та ітеративні алгоритми обробки дерев.

  11. Дерева бінарного пошуку. Схеми збалансованих дерев. Повністю збалансовані дерева. АВЛ-дерева. 2-3 – дерева. Червоно-чорні дерева.

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

    Червоно-чорне дерево (англ. red-black tree, англ. RB tree) - в інформатиці - різновид бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний).

    В-дерева.

  12. Алгоритми сортування, їх ефективність.

  13. Хешування і хеш-таблиці. Методи розв'язання колізій.

  14. Класи. Інкапсуляція. Атрибути класів. Функції-члени класу. Статичні члени класу.

  15. Конструктори та деструктори. Абстрактні класи.

  16. Поняття наслідування в . Поліморфізм.

  17. Віртуальне наслідування. Особливості віртуального наслідування.

  18. Множинне наслідування в .

  19. Шаблони класів.

  20. Перевантаження функцій. Три кроки вирішення перевантаження функцій.

    Перевантаження функції, перевантаження процедури або ж перевантаження методу (англ. function overloading or method overloading) - в програмуванні один із засобів реалізації поліморфізму (ad hoc поліморфізм), що полягає в можливості створювати кілька реалізацій функції (методу) із тим же ім'ям проте з різною сигнатурою - з різною кількістю параметрів або з різним типом параметрів.



  21. Шаблони функцій. Перевантаження в шаблонах функцій.

  22. Виключення. блок.

Література


  1. Гуров В.В., Чуканов В.О. Основы теории и организации ЭВМ Интернет-университет информационных технологий - ИНТУИТ.ру, 2006.

  2. Богданов А.В., Корхов В.В., Мареев В.В., Станкова Е.Н. Архитектуры и топологии многопроцессорных вычислительных систем. Интернет-университет информационных технологий - ИНТУИТ.ру, 2004

  3. Гуров В.В., Ленский О.Д., Соловьев Г.Н., Чуканов В.О. Архитектура, структура и организация вычислительного процесса в ЭВМ типа IBM PC, М.: МИФИ, 2002. Под ред. Г.Н. Соловьева.

  4. Каган Б.М. Электронные вычислительные машины и системы. - М.: Энер­го­атом­из­дат, 1991.

  5. Вирт Н. Алгоритмы Структуры данных = Программы. – М., Мир, 1984.

  6. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М., Издательский дом «Вильямс», 2000.

  7. Кривий С.Л. Вступ до методів створення програмних продуктів.

    Програ́мний проду́кт (англ. programming product) - це: програмний засіб, програмне забезпечення, які призначені для постачання користувачеві (покупцеві, замовникові). програма, яку може запускати, тестувати, виправляти та змінювати будь-яка людина.

    Чернівці:Букрек. 2012.

  8. Рейнгольд Э., Нивергальт, Део Н. Комбинаторные алгоритмы. Теория и практика. – М., Мир, 1980.

  9. Липпман С., Лажойе Ж. Язык программирования . Вводный курс. 3-е издание. – М., ДМК, 2001.

  10. Страуступ Б. Язык программирования . 3-е издание. – С.Петербург, Невский диалект, 2000.

  11. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ. 3-е издание. – М.: ИД "Вильямс", 2013.


Теорія ймовірностей та математична статистика, аналіз даних

  1. Аксіоматичне означення ймовірностей.

    Аналіз даних - розділ математики, що займається розробкою методів обробки даних незалежно від їх природи.

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

    Формула повної ймовірності та формула Байеса.

  2. Випадкові величини. Властивості функцій розподілу.

  3. Нерівність Чебишова. Закон великих чисел.

  4. Основні типи дискретних та неперервних розподілів.

  5. Центральна гранична теорема для однаково розподілених незалежних випадкових величин.

  6. Поняття випадкового процесу. Вінерівський та Пуассонiвський процеси.

  7. Випадкове середнє та дисперсія. Емпірична функція розподілу.

    Випадко́вий проце́с (англ. stochastic process) - важливе поняття сучасної теорії ймовірностей. Є певним узагальненням поняття випадкова величина, а саме - це випадкова величина, що змінюється з часом (іншими словами: випадкова величина, що залежить від змінної величини, яку називають час, або іншими словами - це набір випадкових величин, параметризованих величиною T - часом).

    Випадкова величина (англ. Random variable) - одне з основних понять теорії ймовірностей.

    Емпірична функція розподілу - це функція розподілу реалізації випадкової величини, яку будують за результатами вимірювань (спостережень).

    Теореми Глівенка та Колмогорова.

  8. Перевірка статистичних гіпотез. Критерії Колмогорова та Пiрсона.

  9. Видалення викидів у випадку скалярних спостережень.

  10. Частинний коефіцієнт кореляції. Його властивості та перевірка на значимість.

  11. Рангові коефіцієнти кореляції Спірмена та Кендала. Їх властивості та перевірка на значимість.

  12. Задача однофакторного дисперсійного аналізу та її розв’язання.

    Дисперсійний аналіз (англ. analysis of variance (ANOVA)) являє собою статистичний метод аналізу результатів, які залежать від якісних ознак. Кожен фактор може бути дискретною чи неперервною випадковою змінною, яку розділяють на декілька сталих рівнів (градацій, інтервалів).



  13. Гребенева оцінка. Її властивості та методика використання.

  14. Пряма та обернена крокова регресія.

  15. Задача коваріаційного аналізу та її розв’язання.

Література

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

  2. Братійчук М.С., Чечельницький О.А. Математична статистика. Навчальний посібник. К.: 2009.- 243с

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

  4. Лебєдєв Є.О., Шарапов М.М. Вступ до теорії ймовірностей. – К.

    Теорія ймовірності - розділ математики, що вивчає закономірності випадкових явищ: випадкові події, випадкові величини, їхні функції, властивості й операції над ними. Математичні моделі в теорії ймовірності описують з деяким ступенем точності випробування (експерименти, спостереження, вимірювання), результати яких неоднозначно визначаються умовами випробування.

    : ВПЦ «Київський університет», 2010.-151с

  5. Айвазян С.А., Енюков Н.С., Мешалкин Л.Д. Прикладная статистика. – М., Финансы и статистика, 1983.

  6. Афифи А., Эйзен С. Статистический анализ. Подход с использованием ЭВМ. – М., Мир, 1982.

  7. Слабоспицький О.С. Аналіз даних. Попередня обробка. – ВПЦ “Київський університет”, 2001.

  8. Слабоспицький О.С. Основи кореляційного аналізу даних. – К.

    Кореляційний аналіз - це статистичне дослідження (стохастичної) залежності між випадковими величинами (англ. correlation - взаємозв'язок). У найпростішому випадку досліджують дві вибірки (набори даних), у загальному - їх багатовимірні комплекси (групи).

    , ВПЦ “Київський університет”, 2006.

  9. Слабоспицький О.С. Дисперсійний аналіз даних. – К., ВПЦ “Київський університет”, 2013.


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

  1. Призначення та функції операційної системи. Класифікація операційних систем.

  2. Інтерфейс пристроїв вводу-виводу. Способи організації вводу-виводу в операційних системах.

  3. Основні поняття в галузі знань про операційні системи.

  4. Концепція процесу та потоку. Діаграма станів процесу. Багатопоточна модель.

  5. Ресурси. Взаємне блокування.

    Операці́йна систе́ма, скорочено ОС (англ. operating system, OS) - це базовий комплекс програм, що виконує управління апаратною складовою комп'ютера або віртуальної машини; забезпечує керування обчислювальним процесом і організовує взаємодію з користувачем.

    Взає́мне блокува́ння (англ. Deadlock) - ситуація, коли кожен із групи процесів очікує на подію, яку може викликати лише інший процес з цієї групи. Часто, така ситуація спостерігається в парадоксах типу «Курка або яйце».

    Стратегії по управлінню тупиками в операційних системах.

  6. Сторінкова віртуальна пам’ять. Суть, призначення, апаратна підтримка організації. Класифікація алгоритмів заміщення сторінок.

  7. Основні абстракції, інтерфейс та внутрішній устрій файлових систем.

  8. Мовні процесори. Структура компілятора та фази компіляції.

  9. Формальні граматики. Ієрархія Н.Чомскі.

  10. Суть, призначення та принципи побудови лексичного аналізатора.

  11. Регулярні мови. Скінченні автомати. Конструкція підмножин станів. Мінімізація скінченних автоматів.

  12. Контекстно-вільні мови, поняття та види виводу.

  13. Синтаксичний розбір, поняття абстрактного синтаксичного дерева.

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

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

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

    Абстрактне синтаксичне дерево (англ. Abstract syntax tree) (АСД) в інформатиці - це скінченна множина, позначене і орієнтоване дерево, в якому внутрішні вершини співставлені з відповідними операторами мови програмування, а листя з відповідними операндами.



  14. Метод рекурсивного спуску. Нерекурсивний парсинг з передбаченням. LL-граматики. Синтаксичний розбір знизу вверх.

    Синтаксичний розбір - розбір, покликаний виробити уміння аналізувати структуру простого, простого ускладненого і складного речення, розкривати характер синтаксичних зв 'язків слів у словосполученні й реченні та синтаксичних відношень, що сприяє розвиткові зв'язного мовлення учнів.



Література.

  1. Andrew Tanenbaum Modern operating systems (3rd Edition) / Andrew Tanenbaum. — Prentice Hall, 2008. — 1104 pp.

  2. Alfred Aho Compilers: Principles, Techniques, and Tools (2nd Edition) / Alfred Aho, Monica Lem, Ravi Sethi, Jeffrey Ullman. — Addison Wesley, 2007.

    Addison-Wesley - американське видавництво, що спеціалізується на технічній, особливо комп'ютерній літературі. Належить медіа-концерну Pearson PLC.

    — 1009 pp.


Скачати 103.57 Kb.

  • Література