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

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



122 Комп’ютерні науки

Скачати 80.33 Kb.

122 Комп’ютерні науки




Скачати 80.33 Kb.
Дата конвертації30.03.2019
Розмір80.33 Kb.
Київський національний університет імені Тараса Шевченка факультет комп’ютерних наук та кібернетики П Р О Г Р А М А вступного іспиту до аспірантури за спеціальністю 122 Комп’ютерні науки Затверджено вченою радою факультету комп’ютерних наук та кібернетики (протокол № 10 від «15» __червня__ 2017 р.) Київ – 2017 ТЕОРІЯ МНОЖИН Основні операції над множинами; основні співвідношення. Прямий та узагальнений прямий добуток. Потужність множин; порівняння множин; теорема Кантора-Бернштейна-Шредера. Бінарні відношення; основні класи бінарних відношень: еквівалентності, часткові та лінійні порядки, функціональні відношення. Основні операції над бінарними відношеннями: теоретико-множинні операції, добуток, інверсія, замкнення. Частково-впорядковані множини; основні класи: лінійно впорядковані, повністю впорядковані множини, повні решітки, решітки, піврешітки. Трансфінітна індукція. Основні топологічні конструкції: топологія, засоби введення топологій, неперервність, конкретні топології, топологія Скотта. ЛІТЕРАТУРА Александров П.С. Введение в теорию множеств и общую топологию. - М.: Наука. 1977. Базилевич Л.Є. Дискретна математика у прикладах і задачах : теорія множин, математична логіка, комбінаторика, теорія графів.
Алгебра множин - розділ теорії множин, який визначає закони композиції множин, виходячи з основних властивостей операцій над ними, а також пропонує певну систематичну процедуру для обчислення теоретико-множинних рівнянь та співвідношень.
Дискре́тна матема́тика - галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру.
Теорія графів - розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E - підмножина V × V.
Математи́чна ло́гіка - розділ математики, що вивчає мислення за допомогою числень, застосовуючи математичні методи та спеціальний апарат символів. Предметом математичної логіки є математичні теорії в цілому, які вивчаються за допомогою логіко-математичних мов.
Трансфінітна індукція - метод доведення, що узагальнює математичну індукцію у випадку незліченного числа значень параметра.
Тео́рія множи́н - розділ математики, в якому вивчаються загальні властивості множин (переважно нескінченних). Виділення теорії множин в самостійний розділ математики відбулося на рубежі XIX і XX століть.
 — Математичний практикум. — Львів, 2013. — 486 с.  Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. - М.: Мир. 1985. Бурбаки Н. Общая топология. Основные структуры. - М.: Наука. 1968. Карнаух Т.О., Ставровський А.Б. Вступ до дискретної математики — Київ: 110 с. Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін. Основи дискретної математики. – К., 2002. Курош А.Г. Лекции по общей алгебре. - М.: Наука. 1973. Мальцев А.И. Алгебраические системы. - М.: Наука. 1970. Скорняков Л.А. Элементы теории структур. - М.: Наука. 1982. АЛГЕБРАЇЧНІ СИСТЕМИ Алгебраїчні системи (АС); найважливіші часткові випадки: алгебри, реляційні моделі. Системи породжуючих та базиси. Конгруенції. Гомоморфізми АС. ЛІТЕРАТУРА Ван дер Варден Б.Л. Алгебра. - М.: Наука. 1976. 648 с. Винберг Э. Б. Курс алгебры. — 3-е изд. — Москва: Факториал Пресс, 2002. — 544 с. Кон П. Универсальная алгебра. - М.: Мир. 1968. Кострûкин А.И. Введение в алгебру. - М.: Наука. 1977. 495 с. Курош А. Г. Курс вищої алгебри - СПб.: Лань, 2006. - 432 с. Мальцев А.И. Алгебраические системû. - М.: Наука. 1970. 392 с. ФОРМАЛЬНІ МОВИ І ГРАМАТИКИ Природні та формальні мови;
Форма́льна мо́ва - множина скінчених послідовностей символів, які описуються правилами певного виду, які називаються граматикою, або синтаксисом мови (див. формальна граматика).
семантика та синтаксис. Способи завдання формальних мов: граматики та автомати. Класифікація граматик і мов. Регулярні множини та вирази, праволінійні граматики, скінченні автомати: еквівалентність.
Скінче́нний автома́т - особливий різновид автомату - абстракції, що використовується для описання шляху зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Його особливістю є скінченність множини станів автомату.
Алгебра регулярних множин Кліні, замкненість класу регулярних множин. Основні алгоритмічні проблеми для регулярних множин. Скінченновільні граматики та мови, автомати з магазинною пам’яттю: еквівалентність. Алгебра скінченновільних мов, замкненість класу скінченновільних мов. Основні алгоритмічні проблеми для контекстно вільних мов. ЛІТЕРАТУРА Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1, 2. - М.: Мир. 1978. Базилевич Л.Є. Дискретна математика у прикладах і задачах : теорія множин, математична логіка, комбінаторика, теорія графів. — Математичний практикум. — Львів, 2013. — 486 с.  Дж. Андерсон. Дискретная математика и комбинаторика. - М.: Вильямс. 2004. Гладкий А.В. Формальные грамматики и языки. - М.: Наука. 1973. Нікітченко М.С. Теоретичні основи програмування : навчальний посібник М.С Нікітченко - Ніжин : Видавництво НДУ імені Миколи Гоголя, 2010. - 121с. Нікітченко М.С., Шкільняк С.С. Прикладна логіка Навчальний посібник. K.: ВПЦ Київський університет, 2013. – 278 с. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир. 1979. ТЕОРІЯ АЛГОРИТМІВ І МАТЕМАТИЧНА ЛОГІКА Інтуїтивні властивості алгоритмів. Формальні уточнення: частково рекурсивні функції;
Навчальний посібник - видання, яке частково доповнює або замінює підручник у викладі навчального матеріалу з певного предмета, курсу, дисципліни або окремого його розділу, офіційно затверджений як такий.
Го́голь Мико́ла Васи́льович (рос. Гоголь Николай Васильевич ; прізвище при народженні Яно́вський, з 1821 року - Го́голь-Яно́вський; 20 березня [1 квітня] 1809(18090401) року, Сорочинці, нині Великі Сорочинці, Миргородський район, Полтавська область - 21 лютого [4 березня] 1852 року, Москва) - український письменник з роду Гоголів-Яновських, класик російської літератури, вважається найвизначнішим з представників її «української школи». Був одним із засновників реалізму та заклав соціально-критичний («гоголівський») напрямок в російській літературі.
Рекурсивні функції - клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій.
функції, що обчислюються на машинах з необмеженими регістрами; машини Тьюрінга і нормальні алгоритми Маркова. Примітивно рекурсивні, рекурсивні, загально рекурсивні і частково рекурсивні функції. Рекурсивні та рекурсивно перераховні предикати. Алгоритмічні проблеми: розв’язні, нерозв’язні і частково розв’язні. Приклади. Теореми Райса та Райса-Шапіро. Обчислювальні функціонали: монотонність, неперервність. Приклади. Теореми Кліні про нерухому точку обчислювальних функціоналів.
Нормальні алгоритми (нормальні алгоритми) - вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритму введене радянським математиком А. А.
Маши́на Тю́рінга - математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост.
Нерухома точка відображення множини в себе - точка, яка відображається сама в себе.
Алгебра логіки: булевські функції та їхня реалізація формулами; еквівалентність формул, нормальні форми; повнота та замкненість; теорема про повноту. Числення висловлювань: тавтології, повні системи, зв’язок, аксіоматизації. Теорії першого порядку: мова, інтерпретація, основні властивості теорій, теореми дедукції та повноти. Формальна арифметика: теореми неповноти Геделя. ЛІТЕРАТУРА Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир. 1983. Мальцев А.И. Алгоритмы и рекурсивные функции. - М.: Наука. 1965. Мендельсон Э. Введение в математическую логику. - М.: Наука. 1971. Нікітченко М.С., Шкільняк С.С. Прикладна логіка Навчальний посібник. K.: ВПЦ Київський університет, 2013. – 278 с. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008.
Теорія алгоритмів (англ. Theory of computation) - окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття.
Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир. 1972. Яблонский С.В. Введение в дискретную математику. - М.: Наука. 1986. АЛГОРИТМІКА Структури даних: стек, черга, куча, дерево, граф, хеш-таблиця. Алгоритми сортування та їх часові оцінки. Швидке сортування.
Швидке сортування (англ. Quick Sort) - алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Гоаром, який не потребує додаткової пам'яті і виконує у середньому O ( n log n ) операцій. Однак, у найгіршому випадку робить O ( n 2 ) )} порівнянь.
Медіани та порядкові статистики. Мажоруючий елемент. Обробка послідовностей та підпослідовностей. Динамічне програмування та жадібні алгоритми. Приклади. Графи: методи представлення. Пошук в глибину та в ширину. Класифікація ребер. Топологічне сортування.
Жа́дібний алгори́тм - простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення.
Топологічне сортування - впорядковування вершин безконтурного орієнтованого графа згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин.
Графи: зв’язність, двозв’язність, сильна зв’язність. Пошук циклів в графі. Ейлерів та Гамільтонів цикл.
Гамільто́нів гра́ф - в математиці це граф, що містить гамільтонів цикл.
Пошук найкоротших шляхів: алгоритми Дейкстри, Флойда-Уоршела. Алгоритм Беллмана - Форда. Остовні дерева. Алгоритми Крускала та Пріма. Матриця Кірхгофа пошуку кількості остовних дерев.
Матриця Кірхгофа (англ. Laplacian matrix) - один з методів подання графа за допомогою матриці. Матриця Кірхгофа використовується для підрахунку остовных дерев даного графа , а також в спектральній теорії графів.
Потоки та паросполучення. Задача про максимальний потік. ЛІТЕРАТУРА Анисимов А.В. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001.-153 с. Т.Кормен, Ч.Лейзерсон, Р.Ривест. АЛГОРИТМЫ. Построение и анализ. - Москва : ИД «Вильямс», 2011. – 1296 с. Д.Э.Кнут. Искусство программирования. Т.1,2,3. - М.: Вильямс. 2001. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы : учебн. пособ. Москва : ИД Вильямс, 2000. – 384 с.  Дж. Андерсон. Дискретная математика и комбинаторика. - М.: Вильямс. 2004. МОВНІ ПРОЦЕСОРИ Класифікація мов програмування: процедурно орієнтовані, проблемно-орієнтовані, низького рівня та інші. Синтаксис і семантика. Класифікація мовних процесорів: транслятори, інтерпретатори. Основні етапи трансляції: лексичний, синтаксичний та семантичний аналізи, оптимізація та генерація коду. Синтаксичний аналіз: розбір знизу-вверх та зверху-вниз. Основні класи спеціальних граматик: LL(k)–, LR(k)–граматики. Семантичні програми, генератор коду, методи оптимізації коду.
Оптиміза́ція (англ. optimization, optimisation) - процес надання будь-чому найвигідніших характеристик, співвідношень (наприклад, оптимізація виробничих процесів і виробництва). Задача оптимізації сформульована, якщо задані: критерій оптимальності (економічний - тощо; технологічні вимоги - вихід продукту, вміст домішок в ньому та ін.)
ЛІТЕРАТУРА Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1, 2. - М.: Мир. 1978. Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. - М.: Мир. 1985. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир. 1975. Волохов В.М. Методичні рекомендації до лабораторного практикуму побудови мовних процесорів з дисципліни «Системне програмування» — Київ: 2013. — 53 с. Льюнс Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир. 1979. Пратт Т., М.Зелковиц. Языки программирования. Разработка и реализация. - Питер. 2002. – 690 с. МЕТОДИ ПРОГРАМУВАННЯ Структурне програмування: суть і основні принципи, транслювання в структурні програми, структурний підхід в конкретних мовах програмування.
Мо́ва програмува́ння (англ. Programming language) - це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.
Функціональне програмування: суть і основні принципи, взаємне транслювання функціональних і імперативних програм. Переваги та недоліки, області застосування, функціональні мови програмування. Логічне програмування: суть і основні принципи, хорнівська логіка, SLD-резолюція, повнота, адекватність. Переваги та недоліки, області застосування, мови логічного програмування.
Логі́чне програмува́ння - парадигма програмування, а також розділ дискретної математики, що вивчає методи і можливості цієї парадигми, засновані на виведенні нових фактів з даних фактів згідно із заданими логічними правилами.
Специфікація, верифікація, тестування програмного забезпечення. Сучасні тенденції в методах програмування. ЛІТЕРАТУРА Андерсен Р. Доказательство правильности программ. - М.: Мир. 1982. Анісімов А.В., Дорошенко А.Ю., Погорілий С.Д., Дорогий Я.Ю. Програмування числових методів мовою Python. К.
Python (найчастіше вживане прочитання - «Па́йтон», запозичено назву з британського шоу Монті Пайтон) - інтерпретована об'єктно-орієнтована мова програмування високого рівня з строгою динамічною типізацією.
: ВПЦ «Київський університет», 2014. – 640 с. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционнûе базû даннûх. - К.: Либідь. 1992. Гради Буч, Роберт А. Максимчук, Майкл У. Энгл, Бобби Дж. Янг, Джим Коналлен, Келли А. Хьюстон. Обúектно-ориентированный анализ и проектирование с примерами приложений. - М.: Вильямс. 2010. 720 с. Грис Д. Наука программирования. - М.: Мир. 1994. Зубенко, Л.Л. Омельчук. Програмування : навчальний посібник (гриф МОН України) - К. : ВПЦ Київський університет, 2011. - 623 c. Лавріщева К.М., Нікітченко М.С., Омельчук Л.Л.. Технологія програмування інформаційних систем.
Інформацíйна систéма (англ. Information system) - сукупність організаційних і технічних засобів для збереження та обробки інформації з метою забезпечення інформаційних потреб користувачів.
Підручник (гриф МОН України). – Киев: ВПЦ Київський університет, 2015. – 367 с. Лингер Р., Миллс Х., Уатт Б. Теория и практика структурного программирования. - М.: Мир. 1982. Логическое программирование. Сб. статей. - М.: Мир. 1988. Математическая логика в программировании. Сб. статей. - М.: Мир. 1990. Нікітченко М.С. Теоретичні основи програмування : навчальний посібник М.С Нікітченко - Ніжин : Видавництво НДУ імені Миколи Гоголя, 2010. - 121с. Редько В.Н., Басараб И.А. Базû даннûх и информационнûе системû. - М.: Знание. 1986. Хендерсон П. Функциональное программирование. Применение и реализация. - М.: Мир. 1983. Хоггер К. Введение в логическое программирование. - М.: Мир. 1988. Програму склали: Чл.-кор. НАН України, декан факультету кібернетики, доктор фіз.-мат. наук, професор А.В. АНІСІМОВ Завідувач кафедри теоретичної кібернетики, доктор фіз.-мат. наук, професор Ю.В. КРАК Завідувач кафедри теорії та технології програмування, доктор фіз.-мат. наук, професор М.С. НІКІТЧЕНКО Завідувач кафедри математичної інформатики, доктор фіз.-мат. наук, професор В.М. ТЕРЕЩЕНКО


Скачати 80.33 Kb.

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