Трансформаційні методи синтезу
обчислювальних систем

Галузь знань: 12 Інформаційні технології
Спеціальність: 121 Інженерія програмного забезпечення
Освітня програма: Програмне забезпечення систем

Викладач: доцент Петрушенко Анатолій Миколайович (лекції)

Викладається: в 2-му семсетрі магістратури.
Загальний обсяг: 90 год, з яких:
  • Лекції – 14 год.
  • Лабораторні заняття – 14 год.
  • Самостійна робота – 60 год.
  • Консультації – 2 год.

Предмет дисципліни

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

Мета та завдання дисципліни

Мета та завдання дисципліни полягає у:
  • формуванні у магістрів основ знань, необхідних для розуміння принципів організації, функціонування і проектування обчислювальних систем (ОбС) – довільних технічних (тобто створених людиною) систем обробки інформації, поведінка яких може бути описана алгоритмічно, зокрема програм та засобів обчислювальної техніки (апаратури);
  • демонстації близкості математичних моделей проектування програмного забезпечення (software) та апаратних засобів (hardware) комп'ютерів, знаходженні "спільного знаменника" цих моделей;
  • алгебраїчного (діалогового автоматно-граматичного) підходу до синтезу ОбС (як різновиду трансформаційних методів синтезу);
  • дослідженні взаємозв'язку названих вище моделей з основними поняттями інженерії знань (штучного інтелекту), зокрема, принципами побудови, функціонування та проектування систем, що засновані на знаннях (систем знань);
  • практичному оволодінні навичками як проектування систем знань, так і роботи з ними на прикладі діалогової трансформаційної машини (ДТМ) – інструментарія алгебраїчних (діалогових автоматно-граматичних) методів представлення знань та маніпулювання цим знанням в довільних, зокрема великих і складних, предметних областях.
В результаті вивчення навчальної дисципліни студент повинен
знати:
  • тенденції розвитку науки (програмування та апаратури) в області проектування ОбС;
  • основні методи та відповідні їм математичні моделі проектування ОбС, переваги та недоліки цих методів та моделей;
  • алгебраїчний (діалоговий автоматно-граматичний) підхід до аналізу та синтезу знань в довільних (великих та складних) предметних областях;
  • принципи організації та функціонування апаратних засобів комп'ютерів, зокрема:
    • форми (природну, з фіксованою комою, з плаваючою комою або, як її ще називають, нормальну) представлення чисел в комп'ютерах;
    • коди (прямий, обернений, доповнювальний, модифікований доповнювальний) представлення чисел в комп'ютерах;
    • алгоритми виконання в комп'ютерах в названих формах і кодах основних алгебраїчних операцій (додавання, віднімання, множення, ділення, зсуву і т.д.);
    • методи проектування типових операційних вузлів комп'ютерів (тригерів, регістрів, лічильників, суматорів і т.д.);
    • принципи побудови і методи проектування керуючих автоматів (КА) (блоків керування процесорів у комп'ютерах) на "твердій" та "м'якій" логіці (як автоматів Мілі та Мура);
    • принципи побудови і методи проектування операційних автоматів (ОА) (арифметико-логічних пристрої комп'ютерів) заданої архітектури (як автоматів з канонічною структурою, зі структурою І-автоматів, М-автоматів, ІМ-автоматів з паралельною і послідовною комбінаційними частинами, S-автоматів);
    • принципи побудови і методи проектування (в заданому структурному базисі, заданої архітектури, на задану систему команд) операційних пристроїв (процесорів) як композиції із зворотнім зв'язком КА і ОА;
    • математичні методи оптимізації (як структурні, так і алгебраїчні) операційних пристроїв та їх компонент по найбільш важливим структурно-функціональним і техніко-економічним характеристикам – швидкодії, продуктивності, затратам обладнання (вартості), надійності;
  • основні поняття інженерії знань, принципи побудови та функціонування систем, що засновані знаннях, у тому числі:
    • архітектуру систем знань та тенденції їх розвитку;
    • моделі та мови представлення знань у комп'ютерах;
    • способи, стратегії та схеми виводу в системах знань;
    • методи накопичення та набування знань в системах знань;
    • методи побудови пояснювального інтерфейсу в системах знань;
  • принципи побудови та особливості ДТМ як різновиду систем знань (архітектуру, вхідну мову, послідовність етапів аналізу та синтезу в ДТМ програмного забезпечення та апаратних засобів комп'ютерів і т.д.).
та вміти:
  • працювати з літературою, ставити завдання, давати порівняльну характеристику різноманітним варіантам рішень на етапах проектування ОбС;
  • використовувати сучасний математичний апарат для вирішення наукових та інженерних задач, що виникають при розробці ОбС;
  • давати порівняльну характеристику сучасним методам та відповідним їм моделям проектування ОбС;
  • синтезувати (з використанням схемотехнічних засобів автоматизації проектування електронної апаратури) типові операційні вузли комп'ютерів, керуючі та операційні автомати, операційні пристрої;
  • застосовувати математичні методи оптимізації (як структурні, так і алгебраїчні) в процесі синтезу операційних пристроїв та їх компонент;
  • підключати до вхідної мови ДТМ, що наближена до природної, цільові мови (програмування, проектування та їх різновиди);
  • наповнювати базу знань ДТМ конкретними знаннями про конкретну предметну область;
  • розробляти деякі програмні модулі, що використовуються в процесі синтезу програм та операційних пристроїв в ДТМ;
  • проектувати з використанням ДТМ в конкретній предметній області програмне забезпечення і апаратні засоби комп'ютерів;
  • досліджувати якість спроектованих ОбС.

Вимоги до знань та вмінь

Для вивчення курсу Трансформаційні методи синтезу обчислювальних систем студент повинен прослухати наступні курси:
  • Дискретна математика
  • Об'єктно-орієнтоване програмування
  • Фізичні основи комп'ютеорної електроніки
  • Теорія алгоритмів та математична логіка
  • Організація баз даних та знань
  • Системний аналіз та проектування комп'ютерних інформаційних систем
  • Моделювання систем
  • Системи штучного інтелекту
  • Розподілені обчислення
  • Інформаційні системи
  • Програмна інженерія
  • Теоретичні основи та методи розробки інформаційних систем

Програма курсу

Змістовий модуль 1: Вступ до теорії трансформаційних методів синтезу обчислювальних систем (ОбС).

Тема 1: Цифрові комп'ютери та їх синтез.
  • Вступ до курсу.
  • Інформаційні, алгоритмічні та архітектурні (схемотехнічні) принципи та методи побудови цифрових комп'ютерів.
  • Синтез операційних пристроїв (моделей процесорів сучасних комп'ютерів) на базі "твердої" та "м'якої" (програмованої) логіки.
Тема 2: Моделі та генератори дискретних процесів обробки інформації в ОбС.
  • Операції, відношення, предикати. Алгебраїчні системи (АС).
  • АС як Ω-система.
  • Універсальні алгебри (УА).
  • Моделі (реляційні системи).
  • Багатоосновні (багатосортні) УА.
  • Групоїди.
  • Півгрупи.
  • Групи.
  • Моноїди.
  • Автомати (без виходів).
  • Тризначна алгебра логіки (алгебра Поста).
  • Формальні мови і граматики.
  • Абстрактні машини.
  • Автомати.
  • Дискретні перетворювачі інформації (ДПІ).
  • Мережі Петрі.
  • Генератори дискретних (інформаційних) процесів (ГДП).
  • Системи алгоритмічних алгебр (САА).
  • Подання ДПІ регулярними схемами (РС).
  • Сіткова модель РС оператора.
  • РС ланцюгів Маркова.
  • Приклади, що демонструють введені поняття і результати.
Модульна контрольна робота 1

Змістовий модуль 2: Формалізоване проектування ОбС.

Тема 3: Схемотологія та паралельні обчислення.
  • Схеми програм.
  • Алгоритмічна алгебра логіки.
  • Алгоритмічні алгебри з замкнутими логічними умовами.
  • S*-алгебри.
  • Приклади використання введених понять для опису ОбС.
  • Паралельні ДПІ.
  • Паралельні регулярні схеми (ПРС) алгоритмів символьної обробки.
  • Однорідні та неоднорідні періодично-визначені перетворення.
  • Проектування алгоритмів сортування.
  • Розпаралелювання алгоритмів послідовного сортування.
Тема 4: Інженерія знань: трансформаційний підхід.
  • Алгебраїчні моделі генерації схем програм.
  • Алгебри гіперcхем та їх модифікації.
  • Трьохосновні САА.
  • Граматичні моделі проектування ОбС.
  • Інженерія знань: основні поняття і результати.
  • ДТМ:
    • принципи побудови,
    • вхідна мова,
    • архітектура,
    • процес проектування в ДТМ програм і апаратури.
Модульна контрольна робота 2

Рекомендована література

Основна:

  1. Агафонов В.Н. Спецификация программ: понятийные средства и их организация. – Новосибирск: Наука, 1987. – 240 с.
  2. Алгоритмический язык АНАЛИТИК-89 / В.П. Клименко, Ю.С.Фишман, Б.А. Бублик и др. – К.: 1990. – 42 с. – (Препр. / АН Украины. Ин-т кибернетики; №90-1).
  3. Анисимов А.В. Рекурсивные преобразователи информации. – К.: Вища школа, 1987. – 231 с.
  4. Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 232 с.
  5. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных. – Киев: Либiдь, 1992. – 191 с.
  6. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наук. думка, 1989. – 376 с.
  7. Ершов А.П. Трансформационный метод в технологии программирования // Пленарные докл. 1 Всесоюзн. конф. по технологии программирования. – К.: 1978 – С. 12-26.
  8. Ершов А.П. Трансформационная машина: тема и вариации // Проблемы теоретического и системного программирования. – Новосибирск: НГУ. – 1979. – С. 5-45.
  9. Искуственный интеллект: - В 3 кн.: Справочник Под ред. Э.В. Попова, Д.А.Поспелова, В.Н.Захарова, В.Ф.Хорошевского. – М.: Радио и связь, 1990. Кн. 1. – 464 с.; Кн. 2. – 304 с.; Кн. 3. – 368 с.
  10. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. – М.: Наука, 1988. – 296 с.
  11. Кокорева Л.П., Перевозчикова О.Л., Ющенко Е.Л. Диалоговые системы и представление знаний. – Киев: Наук. думка, 1993. – 446 с.
  12. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. – Л.: Машиностроение, 1974. – 432 с.
  13. Многоуровневое структурное проектирование программ. Теоретические основы. Инструментарий / Е.Л. Ющенко, Е.Л. Цейтлин, В.П. Грицай, Т.К. Терзян М.: Финансы и статистика. – 1989. – 208 с.
  14. Представление знаний в человеко-машинных и робототехнических системах: В 3 т. – М. : ВИНИТИ, ВЦ АН СССР, 1984. – Т.А. – 216 с.; Т.В. - 236 с.; Т.С. - 378 с.
  15. Самофалов К.Г., Корнейчук В.Н., Тарасенко В.П. Цифровые ЭВМ. – К.: Вища шк., 1989. – 423 с.
  16. Самофалов К.Г., Корнейчук В.Н., Тарасенко В.П., Жабин В.Н. Цифровые ЭВМ. Практикум. – К.: Вища шк., 1990. – 215 с.
  17. Цейтлин Г. Е. Введение в алгоритмику. – К.: Сфера, 1998. – 310 с.
  18. Ющенко К.Л., Суржко С.В., Цейтлін Г.О, Шевченко А.І. Алгоритмічні алгебри. Навч. посібник. – К.: ІЗММ, 1997. – 480 с.
  19. Bauer F.L., Wossner H. Algorithmische sprache und programmentwicklung. – Berlin ets.: Springer Verlag, 1981. – 513 p.

Додаткова:

  1. Петрушенко А.Н. Очерки по методологии научного познания: от математических к информационным моделям мира. – К.: Наукова думка, 1998. – 119 с.
  2. Петрушенко А.Н. Об одном подходе к решению проблемы общения человека с вычислительной системой на естественном языке. // Проблемы программирования. – 1998. – Вып. 3. – С. 65-72.
  3. Петрушенко А.Н., Хохлов В.А. Об использовании естественного языка для представления абстрактных типов данных и полиморфизма. // Там же. – 1999. – № 1. – С. 135-144.
  4. Петрушенко А.Н., Хохлов В.А., Ткачев В.А., Шепетухин Е.С. Диалоговая трансформационная машина: некоторые функциональные возможности. // Там же. – 2000. – № 1-2 (Спец. выпуск) – С. 323-334.
  5. Петрушенко А.Н., Хохлов В.А. Диалоговая трансформационная машина как инструментарий прототипирования программных изделий со спиральной моделью жизненного цикла. // Вестник ХГТУ. – 1997. – № 2. – С. 144-148.
  6. Петрушенко А.Н. О машинно-независимых методах программирования адресно-вычислимых функций. // Там же. – 1998. – № 4. – С. 142-146.
  7. Петрушенко А.Н., Хохлов В.А. Пример синтеза в диалоговой трансформационной машине САА/Д-cхемы и реализующих ее программы и управляющего автомата операционного устройства // Там же. – 1999. – № 3. – С. 440-443.
  8. Петрушенко А.Н., Хохлов В.А., Ткачев В.А. Об автоматизации проектирования управляющих автоматов с жесткой логикой. // Автоматика. Автоматизация. Электротехнические комплексы и системы. – 1999. – № 1. – С. 80-87.
  9. Петрушенко А.Н. Диалоговая трансформационная машина как разновидность систем знаний. // Там же. – 1999. – № 2. – С. 65-72.
  10. Петрушенко А.Н. Граф-схемы Калужнина и синтез микропрограммных автоматов. // Друга міжнародна конференція в Україні, присвячена пам'яті професора Л.А. Калужніна (1914-1990): Зб. наук. пр. – Київ-Вінниця: Київський університет ім. Тараса Шевченка, 1999. – С. 100-101.
  11. Petrushenko A.N. Interactive computations in algorithmic algebras. // Cybernetics. – Consultants Bureau, New York and London, 1990. – Vol. 26, № 1. – P. 14-21.
  12. Petrushenko A.N. An approach to automation of optimizing transformations of algorithms and programs. // Cybernetics and systems analysis. – Consultants Bureau, New York and London, 1990. – Vol. 26, № 1. – P. 14-21.
  13. Petrushenko A.N. On dialog transformations of program scheme in therm algebra and in accessibility spaсe. // Cybernetics and computing technology. – Allerton press, Inc., New York, 1998. – Number 112. – P. 62-65.