Математичне та програмне забезпечення обчислювальних машин і систем

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Поняття обчислювальної системи. Системи з конвеєрною обробкою інформації; матричні системи; асоціативні системи і осередки; функціонально розподільні системи; системи з перебудованою структурою. SIMD- і MIMD-архітектура.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Об'єктно-орієнтоване програмування. Мови: Smalltalk, C++.

9. Функціональне програмування. Концепції та приклади. Мова Лісп.

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

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

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

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

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

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

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

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

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

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

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

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

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 с.

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

11. Вельбицкий И.В. Технология программирования. – Киев: Техника,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58. Тыугу Э.Х. Концептуальное программирование. – М. : Наука, 1984. – 256 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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