Одержано 02.09.2022; Виправлено 12.09.2022; Прийнято 29.09.2022

Надруковано 30.09.2022; Вперше Online 05.10.2022

https://doi.org/10.34229/2707-451X.22.2.4

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.6

Моделі комп’ютерних обчислень

В.К. Задірака ^* ,   О.М. Хіміч ,   І.В. Швідченко ^*

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. З позицій теорії обчислень аналізується складність обчислювальних алгоритмів розв’язання типових задач обчислювальної, прикладної та дискретної математики у залежності від архітектури комп’ютера і використовуваної моделі обчислень: однопроцесорна, багатопроцесорна та квантова.

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

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

Показати, що побудова обчислювального процесу при заданих умовах обчислень пов’язана з розв’язанням таких проблем:

– існування ε-розв’язку задачі;

– існування T-ефективних обчислювальних алгоритмів;

– можливістю побудови реального обчислювального процесу за даних умов обчислень.

Дослідити вплив заокруглення чисел на обчислювальну складність (особливо при розв’язанні задач трансобчислювальної складності).

Навести оцінки складності та повної похибки обчислювального алгоритму для ряду типових задач обчислювальної, прикладної та дискретної математики.

Результати. Наведено оцінки складності обчислювальних алгоритмів перелічених класів задач для однопроцесорної, багатопроцесорної та квантової моделей обчислень.

Основна увага приділена високопродуктивним обчисленням: використання принципів паралельної обробки даних та квантової механіки.

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

Наведено характеристики перших квантових комп’ютерів (2016 – 2022 рр.), які вийшли за межі лабораторних досліджень.

 

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

 

Цитувати так: Задірака В.К., Хіміч О.М., Швідченко І.В. Моделі комп’ютерних обчислень. Cybernetics and Computer Technologies. 2022. 2. С. 38–51. https://doi.org/10.34229/2707-451X.22.2.4

 

Список літератури

           1.     Бахвалов Н.С. О свойствах оптимальных методов решения задач математической физики. Журнал. Вычислительная математика и математическая физика. 1970. 10 (3). С. 555–568.

           2.     Иванов В.В. Методы вычислений на ЭВМ: Справочное пособие. Киев: Наук. думка, 1986. 584 с.

           3.     Иванов В.В., Бабич М.Д., Березовский А.И., Бесараб П.Н., Задирака В.К., Людвиченко В.А. Характеристики задач, алгоритмов и ЭВМ в комплексах программ вычислительной математики. Киев, 1984. 53 с. (Препринт/АН УССр, Ин-т кибернетики; 84–36).

           4.     Бесараб П.Н. О сложности интегрирования обыкновенных дифференциальных уравнений. Кибернетика и системный анализ. 1996. 3. С. 122–130.

           5.     Химич А.Н., Молчанов И.Н., Попов А.В., Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной математики. Киев: Наук. думка, 2008. 247 с.

           6.     NetLib. http://www.netlib.org/ (звернення: 23.09.2022)

           7.     Карцев М.А. Арифметика цифровых машин. М.: Наука, 1969. 575 с.

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

           9.     Алгоритмы, математическое обеспечение и архитектура многопроцессорных систем / Под ред. В.Б. Котова и Й. Миклошко. М.: Наука, 1982. 336 с.

       10.     Хайрер Э., Нерсетг С., Ваннер Т. Решение обыкновенных дифференциальных уравнений. М.: Мир, 1990. 512 с.

       11.     Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

       12.     Михалевич В.С., Молчанов И.Н., Сергиенко И.В. и др. Численные методы для многопроцессорного вычислительного комплекса ЕС. М.: ВВИА им. проф. Н.Е. Жуковского, 1986. 401 с.

       13.     Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: Мир, 1988. 518 с.

       14.     Задірака В.К., Бабич М.Д., Березовський А.І., Бесараб П.М., Гнатів Л.О., Людвиченко В.О. T-ефективні алгоритми наближеного розв’язання задач обчислювальної та прикладної математики. Київ-Тернопіль, “Збруч”, 2003. 261 с.

       15.     Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the General Theory of Optimal Algorithms. Springer, 2021. P. 378. https://doi.org/10.1007/978-3-030-90908-6

       16.     Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. М.: Мир. 2006. 824 с.

       17.     Каптьол Є.Ю., Горбенко І.Д. Аналіз можливостей та особливості програмування задач криптологіі на квантовому комп’ютері. Радіотехніка. 2020. Вип. 202. C. 37–48. https://doi.org/10.30837/rt.2020.3.202.03

       18.     Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proc. of the 35th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press. 1994. P. 124–134.

       19.     Boneh D., Lipton R.J. Quantum cryptanalysis of hidden linear function. Lect. Notes Comput. Sci. 963. 1995. Р. 424–437. https://doi.org/10.1007/3-540-44750-4_34

       20.     Cleve R. A note of computing Fourier transforms by quantum programs. 1994.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна