Алгебра алгоритмів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Алгебра алгоритмів - вивчає властивості алгоритмів, виникла в 80-х роках 20 століття. При цьому формальні моделі були запропоновані для первісного поняття алгоритму. Алгебра алгоритмів АА = {A, W}, як і будь-яка алгебра, — це основа А і сигнатура W операцій з елементами цієї основи. За допомогою операції сигнатури можна додати довільний елемент q Î AA. Це називається системою утворювальної алгебри.

Історія розвитку[ред. | ред. код]

Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми (А. Марков, І952) .Дослідження і побудова алгебри алгоритмів або алгоритмічної алгебри почалося з проектування логічних структур ЕОМ під керівництвом академіка В.М.Глушкова. Як результат була створена теорія систем алгоритмічних алгебр (САА), що потім Г.О.Цейтліним була покладена в основу узагальненої теорії структурованих схем алгоритмів і програм, названою ним алгоритмікою. Для формалізації самого поняття алгебри алгоритму були запропоновані точні математичні описи .Алгебра алгоритмів виникла як розділ математичної логіки. Перші застосування алгебри алгоритмів -в математичній логіці. Алгебра алгоритмів є теоретичним фундаментом програмування, вона має застосування , де зустрічаються алгоритмічні проблеми ( математики, теорія інформації, теорія керування, конструктивний аналіз, обчислювальна математика, теорія ймовірності, лінгвістика, економіка та ін.).Наразі розроблено кілька алгоритмічних алгебр, найвідомішими з яких є алгебра Дейкстри, алгебра схем Янова та алгоритміка програм, досліджена у працях В.М. Глушкова і Г.О. Цейтліна,а також теорія секвенційних алгоритмів,комп”ютерна реалізація алгебри алгоритмів.

Основні поняття алгебри алгоритмів[ред. | ред. код]

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

Теорія секвенційних алгоритмів і проектування комп’ютерних систем.Редактор формул алгоритмів і аналіз синтаксису і семантики алгебри алгоритмів-секвенцій.Засоби еквівалентних перетворень алгоритмів. Методи підвищення ефективності математичного моделювання алгоритмів інформаційно-технологічних систем. Принципи побудови комп'ютерної бібліотеки абстрактних алгоритмів.

Застосування алгебри алгоритмів[ред. | ред. код]

  • Синтез, оптимізація і дослідження математичних моделей алгоритмів керування електроприводом друкарської машини і проектування комп'ютерних систем.Практичним результатом досліджень алгебри алгоритмів є побудова оригінальних інструментальних систем проектування програм на основі сучасних засобів підтримки ООП (Rational Rose).

Література[ред. | ред. код]

  • Марков А. А., Нагорный Н. М., Теория алгоритмов, М., 1984;
  • Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965;
  • Успенский В. А., Машина Поста, М., 1979;
  • «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973, рос. вид. 1974;
  • Овсяк Володимир Казимирович. Методи підвищення ефективності математичного моделюванняалгоритмів інформаційно-технологічних систем : Дис… д-ра техн. наук: 05.13.02 / Українська академія друкарства. —Львів, 1996. — 229л.
  • Овсяк В. Засоби еквівалентних перетворень алгоритмів / Овсяк В. // Доповіді національної академії наук України. — 1996. — № 9. — C.83-89.
  • Овсяк В. Принцип побудови підсистеми редагування формул абстрактних алгоритмів / В. Овсяк, А. Василюк // Комп'ютерні технології друкарства: Збірник наукових праць.- Львів: УАД, 2004. — № 12. — С. 137—145.
  • Owsiak W., Owsiak A., Owsiak J. Teoria algorytmów abstrakcyjnych i modelowanie matematyczne systemów informacyjnych / Owsiak W., Owsiak A., Owsiak J. — Opole: Politechnika Opolska, 2005. — 275 s.
  • Овсяк В. Принципи побудови комп'ютерної бібліотеки абстрактних алгоритмів Коба / В. Овсяк, А. Василюк, О. Яремчишин // Комп'ютерні технології друкарства: Збірник наукових праць.- Львів: УАД, 2006. — № 15. — С.85 — 95.
  • Ovsyak V. Automation of the Process of Search of the Algorithms’ Formulae in the Library «КоБА» / V. Ovsyak, A. Vasyluk, O. Yaremchyshyn // Proc. of the IX-th intern. Conference «The experience of designing and application of CAD systems in microelectronics (CADSM'2007)». -Lviv-Polyana: Lviv Polytechnic National University, 2007. — P. 418—420.
  • Овсяк В., Возна М. Синтез, оптимізація і дослідження математичних моделей алгоритмів керування електроприводом друкарської машини // Вісник Державного університету «Львівська політехніка». — № 364. -Прикладна математика. — Львів, 1999. — С. 105 — 110.
  • Бритковський В. М., Овсяк В. К., Огірко О. І. Редактор формул алгоритмів і аналіз синтаксису і семантики алгебри алгоритмів-секвенцій. /Матеріали 7 всеукраїнської наукової конференції «Сучасні проблеми прикладної математики та інформатики» Львів:НУ ім. І. Франка,2000. -С. 17-18
  • Овсяк В. К., Бритковський В. М., Овсяк О. В., Овсяк Ю. В. Теорія секвенційних алгоритмів і проектування комп'ютерних систем : Навчальний посібник. —Львів: УАД, 2001. —141 с.
  • Огірко О. Синтаксис оптимізації моделі та моделювання синтаксису механізму розпізнавання символіки алгебри алгоритмів секвенції. // Комп"ютерні технології друкарства, № 5, 2000. -С. 296- 303.
  • Огірко О. Комп”ютерна реалізація алгебри алгоритмів. // Комп'ютерні технології друкарства, № 5, 2000. -С. 200-205.
  • Огірко О. Автоматизовані способи розпізнавання для алгебри алгоритмів.// Автоматика – 2000. – Т.6. – Львів: Державний НДІ інформаційної інфраструктури, 2000.
  • Огірко О. Модель системи генерації програм СКАНЕР. // Комп'ютерні технології друкарства, № 6, 2001. -С. 42-48.
  • Огірко О. Модель комп”ютерної системи генерації програм з формул алгоритмів. // Комп'ютерні технології друкарства, № 6, 2001. -С. 93-97.
  • Огірко О.І. Принцип побудови системи генерації програм з операцій теорії секвенційних алгоритмів//. КВАЛІЛОГІЯ КНИГИ, № 6, 2003. -С. 189-193.
  • Огірко О.І Реалізація математичної моделі підсистеми генерації програм з операцій теорії секвенційних алгоритмів// Комп'ютерні технології друкарства, № 8, 2004.

Дивіться також[ред. | ред. код]