Ukrainian Journal of Information Technology
Permanent URI for this communityhttps://ena.lpnu.ua/handle/ntb/56854
Browse
Item Впорядкування та впорядковування у дискретній математиці та інформатиці(Видавництво Львівської політехніки, 2021-10-10) Овсяк, В. К.; Овсяк, О. В.; Петрушка, Ю. В.; Ovsyak, V. K.; Ovsyak, O. V.; Petruszka, J. V.; Українська академія друкарства; Київський національний університет культури і мистецтв; Ukrainian Academy of Printing; National University of Culture and ArtsДосліджено наявні засоби впорядкувань і впорядковувань у деяких важливих розділах дискретної математики та інформатики, а саме: в теорії множин, класичній математичній логіці, теорії доведень (доказів), теорії графів, методі Поста, системі алгоритмічних алгебр, алгоритмічних мовах об’єктного й асемблерного програмування. Наведено декартів добуток множин, впорядковані пари і впорядковані n-ки, опис засобами теорії множин впорядкованої пари, який виконали Вінер, Хаусдорф і Куратовський. Описано вимоги до відношень, якими впорядковуються множини. Важливість впорядкувань у класичній математичній логіці та теорії доведень проілюстровано прикладами обчислень значень істинності логічних формул і формальним виведенням формули на підставі правил виведення і правил заміни. Впорядкування у теорії графів показано на прикладі блок-схеми алгоритму Евкліда, призначеного для знаходження найбільшого спільного дільника двох натуральних чисел. Описано впорядкування та впорядковування як настанов, утворених двома, трьома і чотирма впорядкованими полями, так і наявне впорядкування настанов у програмі методу Поста. Показано, що програма, утворена пронумерованими настановами, характеризується неповторюваними номерами настанов і наявністю єдиної настанови з номером 1. Проілюстровано засоби системи алгоритмічних алгебр, які застосовують для виконання впорядкувань і впорядковувань у теорії алгоритмів. Наведено операції системи алгоритмічних алгебр, в які входять узагальнені на тризначний алфавіт операції булевої алгебри та операторні операції операторної алгебри. Описано властивості операції композиції, яка призначена для опису впорядкувань операторів операторної алгебри системи алгоритмічних алгебр. Впорядкування, виконувані засобами алгоритмічних мов програмування, проілюстровано на гіпотетичному застосуванні сучасної мови об’єктного програмування C#. Програма має використовувати тільки один метод Main(), з якого починається її виконання. Асемблерна програма мікропроцесора ARM повинна містити тільки одну директиву ENTRY, з якої починається її виконання. Настанови впорядковуються послідовно зверху вниз у вигляді стовпця і записуються в оперативну пам’ять під послідовно впорядкованими адресами. Для виконання переходів застосовуються адреси, записані в настановах переходів. Вектор переривань містить фіксовані адреси комірок пам’яті, в яких записано початкові адреси програм опрацювання переривань.