DOI: https://doi.org/10.15802/ecsrt2015/73851

Про дуалізм випадкового та детермінованого в алгоритмах

V. I. Shinkarenko, T. M. Vasetska

Анотація


Будь-яка величина, яку отримують шляхом вимірів може бути водночас і випадковою і детермінованою. Випадковість проявляється в силу великої кількості факторів, які погано контролюються, і які деякою мірою можуть компенсувати один одного. Метою даної роботи є дослідження двоїстого прояву випадкового та детермінованого в алгоритмах.

Детермінованість алгоритмів є їхньою невід’ємною властивістю. Під детермінованістю алгоритмів розуміють, що для будь-яких даних із множини вхідних даних при будь-якому виконанні алгоритму буде виконано одну і ту ж послідовність дій і отримано один і той же результат.

Ця властивість алгоритмів підтримуються всіма обчислювальними пристроями як абстрактними (машини Тюрінга, Поста), так і реальними.

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

Розуміння вказаних аспектів дозволить уникнути помилок при програмуванні та відповідно використовувати їх при аналізі та дослідженнях алгоритмів.


Ключові слова


детермінізм, випадковість, алгоритм, програма, вхідні дані, результат, дуалізм, випадкові числа

Повний текст:

PDF (Русский)

Посилання


Успенский, В. А., Теория алгоритмов: основные открытия и приложения: научное издание [Текст] / В. А. Успенский, А. Л. Семенов. М.: Физ.-мат. лит.: На-ука, 1987. – 288 с.

Кнут, Д. Э. Искусство программирования., том 1. Основные алгоритмы. [Текст] / Д. Э. Кнут. М.: Издательский дом «Вильямс», 2000. – 720 с.

Цейтлин, Г. Е. Введение в алгоритмику.[Текст] / Г. Е. Цейтлин. Киев: Сфе-ра, 1998. – 310 с.

Игошин, В. И. Математическая логика и теория алгоритмов. [Текст] / В. И. Игошин. Саратов: Изд-во Сарат. ун-та, 1991. – 256 с.

Колмогоров, А. Н. Теория информации и теория алгоритмов. [Текст] / А. Н. Колмогоров. М.: Наука, 1987. – 304 с.

Вьюгин, В. В. Колмогоровская сложность и алгоритмическая случайность (учебное пособие). [Текст] / В. В. Вьюгин. М.: 2012. 131 с.

Саати, Т. Л. Принятие решений. Метод анализа иерархий. [Текст] / Т. Л. Саати. М.: Радио и связь, 1989. – 316 с.

Thomas L. Saaty Relative Measurement and Its Generalization in Decision Making Why Pairwise Comparisons are Central in Mathematics for the Measurement of Intangible Factors The Analytic Hierar-chy/Network Process [Text] / T. L. Saaty // Royal Academy of Sciences, Spain, Se-ries A. Mathematics, 2008 November С. 251-318.

Саати, Т. Л. Об измерении неосязаемого. Подход к относительным измерениям на основе главного собственного вектора матрицы парных сравнений / Т. Л. Саати // Журнал "Cloud Of Science". 2015. Т. 2 № 1.

Шинкаренко, В. И. Методология измерения временной эффективности программных средств [Текст] / В. И. Шинкаренко. // Теоретичні та прикладні аспекти побудови програмних систем: Тези доповідей. К.: НаУ-КМА, 2005. C. 61-65.

Фленов, М. В. Библия Delphi 3-е издание [Текст] / М. В. Фленов – С Петербург: БХВ-Петербург, 2012 – 688 с.




ISSN: 2223–5620 (Print)

ISSN: 2411–1554 (Online)