Міністерство освіти України icon

Міністерство освіти України




Скачати 130.83 Kb.
НазваМіністерство освіти України
Ющенко К.Л
Дата01.07.2012
Розмір130.83 Kb.
ТипДокументи

Міністерство освіти України


ТИПОВА ПРОГРАМА КАНДИДАТСЬКОГО ІСПИТУ ІЗ СПЕЦІАЛЬНОСТІ

01.05.03 - МАТЕМАТИЧНЕ ТА ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ

ОБЧИСЛЮВАЛЬНИХ МАШИН І СИСТЕМ


Київ, 1996


Програми розроблена авторським - колективом у складі: Ющенко К.Л. - член-корєспондент НАН України (інститут кібернетики ім. Глушкова НАН України), Перевозчикова О.Л. - доктор фізико-математичних наук (Інститут кібернетики ім. Глушкова НАН України) , Парасюк І.М. - доктор технічних наук (Інститут кібернетики ім. Глушкова НАН України).

Програма погоджена з науково- методичною комісією Міністерства освіти України.


Затверджена ВАК України "16" травня 1995 р. та Атестаційною колегією Міністерства освіти України " 25” квітня 1996 р., № 2/4/9-2


1. Теоретичні основи


  1. Алгебра множин та відношень. Алгебраїчні системи, моделі, ал­гебри. Породжуючі сукупно-сті: системи твірних та системи визначаючих співвідношень. Конгруенції.

  1. Одноосновні та багатоосновні універсальні алгебри. Структури. Решітки. Булеві алгебри. Ка-тегорії. Топоси.

  1. Формальні мови та теорії. Числення висловлювань. Виконувані та загальнозначимі форму-ли. Теорема Геделя про неповноту.

  2. Числення предикатів. Нормальна форма. Теорема Ербрана. Метод резолюцій. Лямбда-чис-лення. Поняття редекса. Теорема Черча-Россера.

  1. Основні обчислювані оператори. Примітивно-рекурсивні, загально-рекурсивні та част-ково-рекурсивні функції. Тезис Черча-Тьюрінга-Поста-Кліні. Теорема про універсальну машину та s-m-n-теорема. Теорема Кліні про нерухому точку.

  2. Алгоритмічно нерозв'язні проблеми. Проблема зупинення. Теорема Черча про нерозв'язні проблеми розпізнавання виведенності в численні предикатів першого порядку. Теорема Райса про розпізнавання власти­востей.

  3. Поняття скінченого автомата. Гомоморфізм та ізоморфізм авто­матів. Мінімізація автоматів. Скінчені автомати та їх зв'язок з регулярними мовами. Аналіз та синтез скінчених автоматів. Диск-ретні перетворювачі. Системи алгоритмічних алгебр Е.М.Глушкова.

  4. Формальні граматики. Класифікація мов за Хомським. Синтаксис та семантика формальних мов. Алгоритми визначення регулярності гра­матики. Контекстно-вільні мови та їх зв'язок з магазин-ними автоматами. Нормальна форма Хомського. Нормальна форма Грейбах. Контекстно-віль­на мо-ва як розв'язання рівняння. Аналіз та синтез магазинних автоматів.

  5. Синтаксичний аналіз "зверху-вниз". LL(k)-граматики. Рекурсив­ний спуск. Синтаксичний розбір "знизу-вверх". Граматики передування.

  6. Дискретні системи та задачі їх реалізації. Приклади дискрет­них систем. Графи. Мережі Петрі.

  7. Складність алгоритмів та обчислень. NP-складні та NP-повні задачі. Градієнтні методи, евристичний пошук, лінійне та динамічне програмування, розфарбування вершин графа, задача про комівояжера.


^ 2. Архітектура систем обробки інформації


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

    2. Керування зовнішніми пристроями: клавіатура (перевірка символів в буфері, перепрограмування окремих клавіш ); дисплей (керування курсором, виведення символів на екран, зсув екрану та сторінки); дискові накопичувачі (читання таблиці розміщення файлів, робота з файлами); принтер (встановлення специфікацій друку,посилання даних на принтер); введення/виведення (доступ до послідовного порту, створення драйвера пристрою).

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

    4. Поняття обчислювального комплексу. Багатомашинні комплекси: слабозв' язані, прямозв'язані, сателітні. Багатопроцесорні комп-лекси: із загальною шиною, з перехресною комутацією, багатовходовим ОЗП. Особливості організації обчислювальних процесів в комплексах. Порівняння багатомашинних і багатопроцесорних комплексів.

    5. Поняття обчислювальної системи. Системи з конвеєрною оброб­кою інформації; матричні системи; асоціативні системи і осе-редки; функціонально розподільні системи; системи з перебудовуванною струк­турою. ЗІ М0~ і МІ Ш- арх і тектура.

    6. Поняття обчислювальної мережі і її структура. Характеристики мережі: операційні можливості, час доставки повідомлень, продук­тивність і вартість обробки даних. Процеси. Рівні керування. Інтер­фейси. Структура повідомлень. Протоколи. Способи і засоби комутації і передачі даних. Адресація, маршрутизація пакетів і керування потоками даних. Транспортна служба. Протоколи високо-го рівня. Адміністративне керування. Локальні обчислювальні мережі.


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


  1. Операційні системи (ОС): призначення та основні концепції ОС.

  2. Файлова система; драйвери зовнішніх пристроїв; процесор командної мови. Командні файли. Кофігурування системи.

  3. Структура та функції MS-DOS: базова система введення-виведення; блок початкового завантаження, модуль розширення базової системи введення-виведення, модуль обробки переривань, командний процесор; утиліти MS-DOS.

  4. Організація взаємодії програм через переривання. Динамічне завантаження. Завантаження та запуск програмових оверлеїв.

  5. Апаратні, логічні і програмові переривання. Написання власного переривання; доповнення до існуючого переривання.

  6. Організація мультипрограмних процесорів. Утворення процесів. Програмові засоби комплектування ЕОМ та мультипроцесорних систем.

  7. Структура та функції ОС UNIX.

  8. Середовище Windows. Базові класи вікон. Керуючі елементи, кнопки, фокус введення. Об'єкти. Організація сценаріїв.


^ 4. Мови та системи програмування


  1. Процедурні та проблемно-орієнтовані мови: особливості ор­ганізації і напрямки роз-витку. Основні концепції і можливості мов Фортран, Паскаль, Модула-2, Сі, С++, Ада, Лісп, Пролог.

  2. Транслятори (асемблери і компілятори) та інтерпретатори. Етапи трансляції; лексич-ний, синтаксичний, семантичний аналіз, оптимізація, генерація об'єктного коду, зби-рання.

  3. Керування пам'яттю в програмі, що створюється транслятором:
    статична, автоматична, базована та динамічна пам'ять. Методи гешування.

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

  5. Мови, що орієнтовані на паралельну та розподілену обробку. Особливості реалізації.

  6. Генератори систем програмування. Макрогенератори та розширювані системи програмування, препроцесори.

  7. Метасистеми програмування: багатомовні системи, параметричні системи та метатранслятори.

  1. Діалогові системи програмування: призначення та архітектура. Форми організації діалогу. Способи мовного спілкування-, відео-форми, меню, електронні таблиці, використання функціональних клавіш і т. п.. Діалог на природній мові.



^ 5. Технологія програмування та проектування програмного забезпечення (ПЗ)


    1. Основні стадії та етапи проектування програм та документу­вання. Технічне завдання. Ескізний, технічний, робочий проекти. Впровадження та супроводження. Життєвий цикл П3. Каскадна та спіральна моделі життєвого циклу ПЗ.

    2. Специфікація програм. Понятійні засоби специфікації. Денотаційна, операційна та аксіоматична семантики. Класифікація мов специфікацій.

    3. Якість програмового забезпечення. Методи налагодження та тес­тування програм, вери-фікація програм.

    4. Організація роботи колективів програмістів. Бригада головного програміста. Плану-вання виробництва ПЗ. Проектування послідовних та паралельних програм.

    5. Поняття рекурсії. Рекурсивні означення та рекурсивні програ­ми. Властивості рекур-сивних алгоритмів, функціональні і рекурсивні структури даних.

    6. Структурне програмування. Теорема про структурування програми. Багатоосновні ал-гебри структур даних. Теоретико-множини і структури даних.

    7. Схеми програм над пам'яттю. Алгебра алгоритмів. Повторне використання ПЗ. Модифікованість алгоритмів та програм.

    8. Об'єктно-орієнтоване програмування. Мови: Smalltalk, С++. Функціональне програмування. Концепції та приклади. Мова Лісп.

    9. Логічне програмування. Приклади систем програмування "за правилами". Мова Пролог.

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




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

  2. Фізична організація даних: модель організації зовнішньої . пам'яті, гешовані та індексовані файли, В-дерева, файли зі щі-льним індексом, файли із записами змінної довжини; пошук за частковою відповідністю.

  3. Реляційна, мережева та ієрархічна моделі даних і їх реалізація; порівняння моделей.

  4. Мови маніпулювання даними для реляційної моделі: реляційна алгебра та реляційне числення; алгебраїчні мови та мови чис-лення.

  5. Теорія проектування реляційних баз даних: функціональні заложності, декомпозиція схем відношень, нормальні форми схем відно­шень; багатозначні залежності.

  6. Тезаурус в автоматизованих системах управління і обробки інформації.

  7. Системи словників-довідників даних: основні поняття, використання, питання проектування, стратегії реалізації.

  8. Розподілені бази даних: централізовані і децентралізовані СУБД; проблеми розподілення баз даних; виконання запитів; одночасна обробка та оновлення.

  9. Машина баз даних як апаратно-програмовий мультипроцесорний комплекс, призначений для виконання функцій СУВД.




    1. Системи, що грунтуються на знаннях




  1. Концепція знання. Відмінність понять "знання" та "дані". Вави знань. Системи програмування баз знань.

  2. Моделі подання знань: продукційні, логічні, мережеві та фрей­мові.

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

  4. Мови та системи подання знань: концепції і приклади.

  5. Поняття експертної системи та її структура: база даних; база знань; роз-в'язувач (машина виведення); компонент придбання знань; пояснювальний та діалоговий компонент. Формалізовані і неформалі зовані знання.

  6. Пакети прикладних програм (ППП): моделі, функції, режими роботи, архітектура. Системне і функціональне наповнення ППП і міжмодульний інтерфейс. Модульний аналіз предметної області.

  7. Системи підтримки прийняття рішень та особливості їх реалізації.

  8. Етапи розробки систем, що грунтуються на знаннях: ідентифікація, концептуалі заці я, формалі заці я, виконання, тестування, дослі дна експлуатація, модифікація. Інструментарій і методологія розробки сис­тем, що грунтуються на знаннях, класифікація інструменталь-них засобів.

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



ЛІТЕРАТУРА


  1. Агафонов В. Е Спецификация програми; понятийные ередотва и их организация. -             Новосибирск; СО изд-во "Наука",1987. - 240с.

  2. Архитектура многопроцессорних вычислительньгх систем /под редакцией Тимохина             В.И. - Л-д: ЛГУ, 1961. - 104 с.

  3. Ахо А. .Ульман Дж. Теория синтаксичеекого анализа, перевода и компиляции. Т. 1,2.             - Мир, 1978. - 620 о.

  4. Бар Р. Язык Ада в проектировании систем. -М.: Мир, 1988. - 320 с.

  5. Борисов А. Н. , Вивамс Э. П. , Сокур Л. Я. Диалоговие системы принятия решений на             базе  мини-ЭВМ.- Рига: Зинатне, 1966.

  6. Братко И. Программирование на языке Пролог для искуственного интеллекта. - М.:            Мир, 1990. - 560 с.

  7. Браун П. Макропроцессоры и мобильность программного обеспечення. М. : Мир, 1977.             - 254 с.

  8. Брябрин В. М. Программное обеспечение персональних ЗВМ. -М.: Наука, 1968. - 272 с.

  9. Вагин В. Н. Дедукция и обобщение в системах принятия решений. - М.: Наука, 1968.             - 384 с.

  1. Вагнер П. Программирование на языке Ада. - М.: Мир, 1983.

  1. Вельбицкий И. В. Технология программирования. - Киев: Техника,1964. - 280 с.

12. Вирт М. Программирование на языке Модула-2. - М.: Мир, 1987.

13. Гаек П., Гавранек Т. Автоматическое образование гипотез.-М.: Наука,1984.-260 с.

  1. Глушков В. М. Основы безбумажной информатики. - М.: Наука, 1962. - 324 с.

  2. Глушков В. М., Цейтлин Г. Е., Ющенко Е.Л. Алгебра. Языки. Программирование.                 3-е изд. Киев: Наук. думка, 1989.

  3. Готье Р. Руководство по операционной системе UNIX. - М: Фінанси и статистика,               1965. - 232 с.

  1. Грис Д. Конструирование компиляторов. - М.: Мир, 1976.

  2. Грис Д. Наука программирования. - М.: Мир, 1984.

  3. Девис У. Операционнме системи. - М.: Мир, 1960. - 346 с.

  1. Джехани Н. Программирование на языке Си. - М.: Радио и связь.1988.

21. Довгяло А. М. Диалог пользователя и ЗВМ. Основи проектирования и реализации.                - Киев: Наук, думка,1976. -232 с.

  1. Заморин А. П. и др. Вычислительные машини, системи,комплекси. - М.: Наука,1985.

  2. Замулин А. В. Системи программирования баз данних и знаний. - М.: Наука, 1990.

  3. Зелковец М. , Шоу А. , Геннон Дж. Принципы разработки программного обеспечения.                - М.: Мир, 1982. -368 с.

  4. Искуственный интеллект. Справочник в 3-х кн. -М.: Радио и связь.1990.

  5. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. - М.: Финансы и статистика, 1982.

  6. Капитонова Ю. В. , Летичевский А. А. Математическая теория проектирования вычисли-               тельных систем. М.: Наука, 1988. - 295 с.

28. Калиниченко Л. А. , Ривкин В. М. Машины баз данных и знаний. М. : Наука, 1990. -                296 с.

29. Калиниченко Л. А. Методи и средства интеграции неоднородных баз данних. - М.: Наука, 1983.

  1. Касьянов К Н. Оптимизирующие преобразования программ. М.: Наука, 1988. - 335 с.

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

32. Кожевникова Г.П. Структуры данных и проектирование эффективной                вичислительной среды. - Львов: изд-во ЛГУ,1986.

33. Л. Е Кокорева, 0. Л. Перевозчикова, Е. Л. Ющенко. Диалоговые системи и представ-             ление знаний. -Киев: Наукова думка. 1993,-448с.

34. Королев Л.Н. Структура ЗВМ и их математическое обеспечение. М.: Наука, 1978.-352 о.

  1. Котов В. Е. Введение в теорию схем программ. Новосибирск: Наука, 1978. - 857 с.

  2. Котов В. Е. Сети Потри. - М.: Наука, 1984. - 160 с.

  3. Коутс Р. .Влеймик И. Интерфейс ''Человек-компьютер".

  4. Ларионов А. М. , Майоров С. А. , Новиков Г. И. Вычислительные комплекси, системи и                сети. - Л-д: Энергоатом изд. ,1967. - 288 с.

  5. Ларичев 0. И. .Мечитов А. И. Мошкович Е. М. , Фуремс Е. М. Выявление                экспертных знаний . - М.: Наука,1989.

40. Леонг-Хонг Б. Системы словарей - справочников данних. -М.: Финансы и                 статистика, 1986. - 311 с.

  1. Логический подход к искуственному интеллекту: от классической логики к логичес-кому программированию /Тей А. .Грибомон П., Луи Ж. и др. - М. : ,1990. - 632 с.

  2. Лорьер Ж. - Л. Системы искуственного интеллекта. - М: Мир,1990. - 568 с.

  3. Мальцєв А. И. Алгебраические системы, - М.: Наука, 1970. 393 с.

  1. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1966. - 368 с.

  1. Медник С. .Донован Дж. Операционние системи. М.: Мир. 1979.

  1. Мелихов А. Е , Бернштейн Л. С., Коровин С. Я. Ситуационные советующие системы с               нечетной логикой. - М.: Наука, 1990.-272 с.

47. Объектно-ориентированное программирование. Тематический випуск.  Программиро-               вание,1992. – N2.

48. Организация экспертных систем /М. Стефик. Я Эйкинс, Р. Балзер, Дж. Беноит и др.               //Кибернетичеекий сборник. - М.: Мир, 1985, вып. 22. - 170-2207

49. Оре 0. Теория графов. - М.: Наука, 1960. - 336 с.

50. Осуга С . Обработка знаний. - Мир, 1969. - 293 с.

  1. Парасюк И.Н ,Сергиенко И.В. Пакети програми анализа данных: технология разра-               ботки. - М.: Финансы и статистика, 1988. - 159 с.

  2. Представление и использование знаний /X. Уэно,Т. Кояма, Т. Окамото и др. - М.: Мир,                1989. - 220 с.

  3. Приобретение знаний / Под ред. С. Осуги, Ю. Саэки. -М: Мир, 1990. - 304 с.

  4. Программное обеспечение персональних ЗВМ /Стогний А.А.,Ананьевский С. А., Бар-              сук Я И. и др. - Киев: Наукова думка, 1969. 386 с.

  5. Секарахан 3.Машини баз данных и управление базами данных. М. : Мир, 1989. - 695 с.

  6. Системи параллельной обработки /Под ред. Д. Ивекса. - М.: Мир, 1985.

  7. Системи управлення базами данных и знаний/ Наумов А. Е , Вандров А. М., Иванов В.                К. и др. /М.: изд. Финансы и статистика, 1991. - 352с.

  8. Тыугу 3. X. Концептуальное программирование. - М.: Наука, 1984. - 256 с.

  9. Успенский В. А. , Семенов А. Л. Теория алгоритмов: основные открытия и приложения.                - М.: Наука, 1987. - 288 с.

  10. Хантер П. Проектирование и конструирование компиляторов.М.: Финансы и статис-               тика, 1984. - 232 с.

  1. Хоар Ч. Взаимодействующие последовательные процессы. М: Мир, 1969. - 264 с.

  2. Хоггер К. Введение в логичеекое программирование. - М.: Мир,1988. - 384 с.

  3. Хювенен Э. Сеппенек Й., Мир Лиспа: в 2 т. - М.: Мир, 1990.-Т.1 - 447 с.; Т. 2 - 319 с.

  4. Паленко М. Ш, Моделирование семантики в базах данных, М.: Наука, 1989. - 288 с.

65. Цикритзис Д. .Леховски Ф. Модели данных. - М. Финансы и статистика, 1985. - 344 с.

66: Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. -               М.: Наука, 1983. -358 с.

67. Шемакин Ю.И. Тезаурус в автоматизированных системах управления и обработки               информации. - М.: Воениздат,1974. - 188 с.

68. Экспертные системи: принципи работы и примери / Под редакцией Р. Форсайта. - М.:                Радио и связь, 1987. -223 с.

69. Элти Дж. , Кумбе М. Экспертные системы: концепции и примеры. - М.: Финансы и                статистика, 1987. - 191 с.

70. Якубайтис Э. А. Информационно-вичислительные сети. - М: Финансы и статистика,                 1964.

Схожі:

Міністерство освіти України iconМіністерство освіти І науки України Департамент міжнародного співробітництва та європейської інтеграції
Міністерство освіти І науки України інформує, що Федеральним агентством з питань освіти Російської Федерації для громадян України...
Міністерство освіти України iconМіністерство освіти І науки україни 01135, м. Київ, проспект Перемоги
Міністерства освіти і науки України від 17. 04. 2009 року №341 «Про затвердження Плану дій щодо вдосконалення викладання дисципліни...
Міністерство освіти України iconМіністерство освіти І науки україни міністерство охорони здоров’я україни сумський державний університет медичний інститут факультет післядипломної медичної освіти
Етіопатогенез виразкової хвороби шлунка та дванадцятипалої кишки
Міністерство освіти України iconМіністерство освіти І науки україни міністерство охорони здоров’я україни сумський державний університет медичний інститут факультет післядипломної медичної освіти
Механічне подразнення назостравохідним зондом і трахеостомічною трубкою
Міністерство освіти України iconПоложення про Міністерство освіти І науки України, далі Замовник, І (назва установи, організації, підприємства, його підпорядкованість, місце знаходження) в особі, (посада, піб)
Сторони, Міністерство освіти І науки України в особі заступника міністра Стріхи Максима Віталійовича, який діє на підставі Положення...
Міністерство освіти України iconПоложення про нагородження нагрудним знаком "А. С. Макаренко" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти України iconМіністерство освіти І науки, молоді та спорту україни міністерство охорони здоров’я україни сумський державний університет медичний інститут факультет післядипломної медичної освіти
Оптимізація хірургічного лікування ушкоджень селезінки з урахуванням архітектоніки її судин
Міністерство освіти України iconПоложення про нагородження нагрудним знаком "Василь Сухомлинський" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти України iconПоложення про нагородження нагрудним знаком "Софія Русова" Міністерства освіти І науки України
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Міністерство освіти України iconМіністерство освіти та науки України Міністерство освіти та науки України
Орієнтований перелік пріоритетних складових для використання при оцінці екологічних ризиків
Міністерство освіти України iconРішення про нагородження Нагрудним знаком ухвалюється Колегією Міністерства освіти І науки України, затверджується наказом Міністра І публікується в газеті "Освіта України"
Міністерству освіти І науки України Міністерство освіти І науки Автономної Республіки Крим, управління освіти І науки обласних, Київської...
Додайте кнопку на своєму сайті:
Документи


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