Файл: «Алгоритмизация как обязательный этап разработки программы».pdf

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений.

Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах [9, с.67].

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную теории отношений Евдокса, изложенной в V книге «Начал» Евклида.

Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Перебор делителей.

Перебор делителей – алгоритм факторизации числа путем полного перебора всех возможных потенциальных делителей. Суть алгоритма заключается в переборе всех целых чисел i от 2 до квадратного корня из n и вычислении остатка от деления n на i (n mod i). Если остаток от деления на i равен нулю, то i является делителем n.

Описание алгоритма с полным перебором.

1. i = 2.

2. Если n mod i = 0, то i добавить в список делителей числа n.

3. i = i + 1.

4. Если i > , то завершить работу, иначе перейти к шагу 2.

Приведенный алгоритм позволяет найти простые сомножители, но не их степени (например, для n = 8 будет найден один простой сомножитель - 2, хотя их три - 2 * 2 * 2). Более эффективная (по вычислительной сложности) реализация алгоритма перебора, позволяющая найти также и повторы простых сомножителей приведена ниже.

1. i = 2.

2. Если n mod i = 0, то

2.1. Добавить i в список делителей числа n.

2.2. n = n / i.

2.3. Перейти к шагу 2.

3. Если i = 2, то i = i + 1, иначе i = i + 2.

4. Если i > , то завершить работу, иначе перейти к шагу 2.

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n.

В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n).

По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым [1, с.45].

Для ускорения перебора часто не проверяются чётные делители, кроме числа 2, а также делители кратные трём, кроме числа 3. При этом тест ускоряется в три раза, так как из каждых шести последовательных потенциальных делителей необходимо проверить только два, а именно вида 6·k±1, где k - натуральное число.

В практических задачах данный алгоритм применяется редко ввиду его большой асимптотической сложности (в О-нотации), однако его применение оправдано в случае, если проверяемые числа относительно невелики, так как данный алгоритм довольно легко реализуем.

Решето Эратосфена.

Решето Эратосфена - алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых [7, с.66].

По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются [6, с.56].

Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна двум - первому простому числу.

Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).

Найти первое не зачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4, пока возможно.

Теперь все не зачёркнутые числа в списке - это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n. Также, все p большие чем 2 - нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

2.4. Квантовый алгоритм.

Квантовый алгоритм - это алгоритм, предназначенный для выполнения на квантовом компьютере [29, с.33].

Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием, над какими именно кубитами их надо совершать. Квантовый алгоритм задается либо в виде словесного описания таких команд, либо с помощью их графической записи в виде системы вентилей (quantum gate array).

Результат работы квантового алгоритма носит вероятностный характер. За счёт небольшого увеличения количества операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.

Множества задач, допускающих решение на квантовом компьютере и на классическом, совпадают. Квантовый компьютер, таким образом, не увеличивает число алгоритмически разрешимых задач. Весь смысл применения квантового компьютера в том, что некоторые задачи он способен решить существенно быстрее, чем любой из классических. Для этого квантовый алгоритм должен по ходу вычисления генерировать и использовать запутанные квантовые состояния.

Любая задача, решаемая квантовым алгоритмом, может быть решена и классическим компьютером путем прямого вычисления унитарных матриц экспоненциальной размерности, получения явного вида квантовых состояний [13, с.15].

В частности, проблемы, неразрешимые на классических компьютерах (например, проблема остановки), остаются неразрешимыми и на квантовых.

Но такое прямое моделирование требует экспоненциального времени, и потому возникает возможность, используя квантовый параллелизм, ускорять на квантовом компьютере некоторые классические алгоритмы.

Ускорение на квантовом компьютере не связано с тактовой частотой процессора. Оно основано на квантовом параллелизме.

Один шаг квантового вычисления совершает гораздо большую работу, чем один шаг классического. Однако было бы ошибкой приравнивать квантовое вычисление к распараллеленному классическому.

Классификация квантовых алгоритмов может проводится по типу квантовых преобразований, используемых алгоритмом.

Среди часто используемых преобразований можно отметить: en:phase kick-back, phase estimation, en:quantum Fourier transform, en:quantum walk, en:amplitude amplification, en:topological quantum field theory. Также возможна группировка квантовых алгоритмов по типу проблем, решаемых ими.

Таким образом наиболее известными алгоритмами являются: алгоритм Евклида, перебор делителей, решето Эратосфена, квантовый алгоритм.

Заключение

Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком», знакомые теперь каждому школьнику.

В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

Особую роль выполняют прикладные алгоритмы, предназначенные для решения определенных прикладных задач. Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат). Алгоритм (программа) содержит ошибки, если для некоторых исходных данных он дает неправильные результаты, сбои, отказы или не дает никаких результатов вообще. Последний тезис используется в олимпиадах по алгоритмическому программированию, чтобы оценить составленные участниками программы.

Важную роль играют рекурсивные алгоритмы (алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения). Начиная с конца XX - начала XXI века активно разрабатываются параллельные алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно.

Наиболее известными алгоритмами являются: алгоритм Евклида, перебор делителей, решето Эратосфена.

Алгоритм Евклида - эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

Перебор делителей – алгоритм факторизации числа путем полного перебора всех возможных потенциальных делителей. Суть алгоритма заключается в переборе всех целых чисел i от 2 до квадратного корня из n и вычислении остатка от деления n на i (n mod i). Если остаток от деления на i равен нулю, то i является делителем n.

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

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

1. Акулов О. А. Информатика: базовый курс: учебник для технических вузов. - М.: Омега-Л, 2012. - 551 с.
2. Биллиг В.А. Основы программирования. - М.: Проспект, 2011. - 432 с.
3. Вирт Н. Алгоритмы и структуры данных. - М.: Академия, 2012. – 224 с.
4. Гейн А.Г., Сенокосов А.И. Информатика. – М.: ЮНИТИ, 2013. - 372 с.
5. Гришина Е.А. Прикладная информатика: практикум: учебное пособие для средних специальных учебных заведений. - Минск: Вышэйш. шк., 2012. - 223 с.
6. Дональд К. Основные алгоритмы. – М.: Современная школа, 2011. - 448 с.
7. Есипов А.С. Информатика: учебник по базовому курсу. - СПб.: Наука и техника, 2012. - 384 с.
8. Иванова Г.С. Технология программирования. - М.: АО Ассиана, 2013. - 288 с.
9. Извозчиков В.А. Информатика в понятиях и терминах. - М.: ИНФРА-М, 2012. - 307 с.
10. Информатика: учебник по базовому курсу / А.С. Есипов. - Изд. 2-е, перераб. и доп. - СПб.: Наука и техника, 2012. - 384 с.
11. Информатика: сборник задач и решений для общеобразовательных учебных заведений / А.С. Есипов; Н.Н. Паньгина; М.И. Громада. - СПб.: Наука и техника, 2013. - 368 с.
12. Информатика: учебник / Е.В. Филимонова. - 3-е изд., перераб. и доп. - М.: Дашков и К' , 2014. - 480 с.
13. Информатика: учебное пособие для вузов / С.А. Домрачев; В.П. Харьков. - М.: Национал. ин-т бизнеса, 2012. - 218с.
14. Информатика и информационные технологии: учебное пособие / И.Г. Лесничая; рук. авт. коллектива Ю.Д. Романова. - М.: Эксмо, 2012. - 543 с.
15. Информатика: учебное пособие для вузов / С.А. Домрачев; В.П. Харьков. - М.: Национал. ин-т бизнеса, 2012. - 218с.
16. Порублев И.Н. Алгоритмы и программы. – М.: МГУ, 2013. - 504 с.
17. Практикум по курсу «Информатика». Работа в Windows, Word, Excel: учебное пособие для вузов / В.Т. Безручко. - М.: Финансы и статистика, 2011. - 271 с.
18. Касаткин В.Н. Информация, алгоритмы. - М.: Омега, 2013. - 242 с.
19. Каймин В. А. Информатика: учебник для вузов. - 3-е изд.- М.: ИНФРА-М, 2011. - 271 с.
20. Каймин В. А. Информатика: учебник для вузов. - 4-е изд.- М.: ИНФРА-М, 2012. - 284 с.
21. Козырев А.А. Информатика: конспект лекций. - СПб.: Изд-во Михайлова В.А., 2013. - 46 с.
22. Кушниренко А.Г. и др. Информатика. - М.: Форум, 2012. - 335 с.
23. Кулаков А.Г. Алгоритмика. - М.: Кнорус, 2012. – 240 с.
24. Макарова Н. В. Информатика: практикум по технологии работы на компьютере: учебное пособие для экономических вузов. - М.: Финансы и статистика, 2013. - 255 с.
25. Марченко А.И. Программирование в среде. − М.: Экзамен, 2013. – 576 с.
26. Патрушина С. М. Информатика: учебное пособие.. - Ростов н/Д: МарТ, 2011. - 399 с.
27. Ставровский А.Б. Первые шаги в программировании. - М.: ИНФРА-М, 2011.- 275 с.
28. Томас Х. Алгоритмы: построение и анализ. - М.: Кнорус, 2011. – 208 с.
29. Фридланд А. Я. Информатика: толковый словарь основных терминов: учебное пособие для вузов. - М.: ПРИОР, 2012. – 240 с.