Преподаватель который помогает студентам и школьникам в учёбе.

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

Содержание:

Введение

Алгоритм - точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи.

Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль- Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм - есть результат европейского произношения слов аль - Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

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

Значительный вклад в развитие теории алгоритмов внесли советские ученые А. А. Марков, А. И. Мальцев, В. М. Глушков, А. Н. Колмогоров, А. П. Ершов, Ю. Л. Ершов, А. А. Ляпунов, П. С. Новиков, С. В. Яблонский и многие другие.

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

Поставленная цель обусловила следующие задачи:

- рассмотреть понятие алгоритмов;

- изучить формы представления алгоритмов;

- описать известные алгоритмы.

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

Теоретические основы изучения алгоритмов.

Понятие алгоритмов.

Алгоритм является фундаментальным понятием информатики.

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

Алгоритм в программировании - это понятная и точная последовательность действий, записанных на языке программирования.

Алгоритмы - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений [6, с.56].

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

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

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

Поиск теоретических моделей алгоритмов происходил в трех направлениях, которые и определили три основных класса таких моделей.

Для создания алгоритма (программы) необходимо знать:

- полный набор исходных данных задачи (начальное состояние объекта);

- цель создания алгоритма (конечное состояние объекта);

- систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

- дискретность (алгоритм разбит на отдельные шаги - команды);

- однозначность (каждая команда определяет единственно возможное действие исполнителя);

- понятность (все команды алгоритма входят в систему команд исполнителя);

- результативность (исполнитель должен решить задачу за конечное число шагов).

Большая часть алгоритмов обладает также свойством массовости (с помощью одного и того же алгоритма можно решать множество однотипных задач).

Некоторые алгоритмы, к примеру, для вычисления последовательности Фибоначчи, являются интуитивно понятными и относятся к врожденным навыкам логического мышления и решения задач [12, с.45].

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

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

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

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

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

В теории алгоритмов установлен важный факт: в универсальной алгоритмической модели всегда существует универсальный алгоритм, т. е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой модели. Универсальный алгоритм устроен следующим образом. Имеется метод кодирования S для любого алгоритма А в данной модели [20, с.113].

Если на вход универсального алгоритма U подать код S(A) алгоритма A и исходные данные х, то результат работы U будет равен результату работы А над х: U(S(A),x) = А(х). По существу, метод кодирования алгоритмов - это язык программирования, а код S(A) - это программа алгоритма А в языке S.

Поэтому концепция универсального алгоритма, существование которого было доказано в 30-х гг. нашего века (раньше, чем появились универсальные ЭВМ), свидетельствует о том, что в основе работы ЭВМ лежат не только физические, но и математические идеи (успехи электроники влияют лишь на быстродействие и размеры ЭВМ).

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами:

- дискретностью;

- массовостью;

- определенностью;

- результативностью;

- формальностью.

Дискретность (разрывность - противоположно непрерывности) - это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

Массовость - применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.

Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е., рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет [28, с.89].

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

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

Формальность - это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания, поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

Формы представления алгоритмов.

На практике наиболее распространены следующие формы представления алгоритмов:

Словесная – запись на естественном языке;

- в псевдокодах – полуформализованное описание алгоритма на условном алгоритмическом языке, включающее в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и т.д.;

- табличная;

- графическая – с помощью графических символов;

- программная – запись на искусственном языке (языке программирования).

Словесный способ не имеет широкого применения по следующим причинам:

- описания не строго формализуемы;

- страдают многословностью записей;

- допускают неоднозначность толкования отдельных предписаний.

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

Графическое представление алгоритма является наиболее компактным и наглядным по сравнению со словесным и псевдокодами. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий [14, с.71].

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

Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице 1 приведены наиболее часто употребляемые символы.

Таблица 1

Графические символы алгоритмов

Название символа	Пояснение
Процесс	Вычислительное действие или последовательность действий
Решение	Проверка условий
Модификация	Начало цикла
Предопределенный процесс	Вычисления по подпрограмме, стандартной подпрограмме
Ввод/Вывод	Ввод/Вывод данных в общем виде
Пуск - Останов	Начало, конец алгоритма, вход в подпрограмму и выход из нее
Документ	Вывод результатов на печать

Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Иногда для улучшения наглядности схемы несколько отдельных блоков объединяют в один блок.

Блок « решение» используется для обозначения переходов управления по условию. В каждом таком блоке должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок « модификация - видоизменение, преобразование» используется для организации циклических структур. Внутри блока записывается параметр цикла, для которого указывается его начальное значение, граничное условие и шаг изменения параметра цикла для каждого повторения.

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

Программы, написанные на языке программирования, можно также рассматривать в качестве форм представления алгоритмов.

Современное программирование в отличие от классической теории алгоритмов стремится предоставить разработчику реальных алгоритмов богатый арсенал мощных и разнообразных средств, как для представления информации, так и для выражения процессов ее обработки. Стремление избавить пользователя от излишней детализации и кодировки при составлении программ привело к появлению целого семейства алгоритмических языков высокого уровня. Этот процесс продолжает бурно развиваться и является определяющим фактором современного программирования [26, с.117].

Понятие алгоритмического языка является одним из основополагающих понятий любого направления информатики, а программирования особенно.

Алгоритмический язык - это язык, используемый для формальной записи алгоритмов. Языки такого типа изучаются и используются в математической логике и в программировании. В математической логике исследуются универсальные алгоритмические языки, на которых можно описать любую процедуру, относимую к интуитивно понимаемому множеству алгоритмов. Примером такого языка может служить язык, на котором функционирует машина Тьюринга.

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

Например, язык ЛИСП опирается на идею реализации алгоритмов как последовательностей вычислений рекурсивных функций. Другой язык программирования - РЕФАЛ использует «универсальный» алгоритмический язык в виде схем нормальных алгоритмов Маркова, а в основе языка ПРОЛОГ лежит модель, заимствованная из логики предикатов первого порядка.

В самом общем случае языком программирования можно назвать фиксированную систему обозначений для описания алгоритмов и структур данных. Такой язык имеет два «лица». Одно из них обращено к человеку, использующему язык для записи своих программ, а другое адресовано ЭВМ, которая должна понимать эти программы.

Язык большинства современных ЭВМ достаточно беден и состоит из команд типа «выделить память определенного размера»; «выбрать из определенного места в памяти информацию»; «запомнить информацию в определенном месте памяти»; «сложить два числа»; «перейти к выполнению очередной команды, выбрав ее из определенного места в памяти» и т. п.

Как правило, команд - несколько сотен. Все они настолько просты, что могут быть эффективно реализованы аппаратурой. Набор команд функционально полон, и, в принципе, используя команды из этого набора (в программировании говорят, пользуясь заданной системой команд), можно описать любой алгоритм [15, с.45].

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

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

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

Такая трансляция может быть одношаговой или многошаговой, в зависимости от числа уровней в иерархии виртуальных ЭВМ.

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

Основные алгоритмические конструкции.

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

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

Рис.1. Блок «один вход и один выход»

Данный блок имеет один вход и один выход. Из простых команд и проверки условий образуются составные команды, имеющие более сложную структуру и тоже один вход и один выход.

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

Рис.2. Основные структуры алгоритма

Рассмотрим основные структуры алгоритма.

Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры.

Рис.3. Команда ветвления

Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.

Рис.4. Неполная форма команды ветвления

Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа.

Рис.5. Команда повторения

Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S. Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы [23, с.77].

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

Рис.6. Выполнение действия S и проверка условия P

В команде повторения с постусловием вначале выполняется действие S и лишь затем, проверяется условие P. Причем действие повторяется до тех пор, пока условие не соблюдается. Примером команды повторения с постусловием будет уменьшение положительного числа до тех пор, пока оно неотрицательное. Как только число становится отрицательным, команда повторения заканчивает свою работу [24, с.71].

С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности.

Рис.7. Способы соединения базовых структур алгоритма

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

Таким образом, можно сделать вывод, что понятие алгоритма - одно из основных в программировании и информатике.

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

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

Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» - почти синонимы.

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

2.1 Алгоритмизация как обязательный этап в разработке программного

обеспечения

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

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

Первое описание алгоритма находится в «Началах Евклида» (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако, в 19 веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как «Евклидово кольцо». Позже алгоритм Евклида также был обобщен на другие математические структуры, такие как узлы и многомерные полиномы [17, с.90].

Для данного алгоритма существует множество теоретических и практических применений. В частности он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений, при построении непрерывных дробей, в методе Штурма. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например, таких как «теорема Лагранжа о сумме четырёх квадратов» и «основная теорема арифметики».

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды - в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

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

Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в 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 века активно разрабатываются параллельные алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно.

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

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

Акулов О. А. Информатика: базовый курс: учебник для технических вузов. - М.: Омега-Л, 2012. - 551 с.
Биллиг В.А. Основы программирования. - М.: Проспект, 2011. - 432 с.
Вирт Н. Алгоритмы и структуры данных. - М.: Академия, 2012. – 224 с.
Гейн А.Г., Сенокосов А.И. Информатика. – М.: ЮНИТИ, 2013. - 372 с.
Гришина Е.А. Прикладная информатика: практикум: учебное пособие для средних специальных учебных заведений. - Минск: Вышэйш. шк., 2012. - 223 с.
Дональд К. Основные алгоритмы. – М.: Современная школа, 2011. - 448 с.
Есипов А.С. Информатика: учебник по базовому курсу. - СПб.: Наука и техника, 2012. - 384 с.
Иванова Г.С. Технология программирования. - М.: АО Ассиана, 2013. - 288 с.
Извозчиков В.А. Информатика в понятиях и терминах. - М.: ИНФРА-М, 2012. - 307 с.
Информатика: учебник по базовому курсу / А.С. Есипов. - Изд. 2-е, перераб. и доп. - СПб.: Наука и техника, 2012. - 384 с.
Информатика: сборник задач и решений для общеобразовательных учебных заведений / А.С. Есипов; Н.Н. Паньгина; М.И. Громада. - СПб.: Наука и техника, 2013. - 368 с.
Информатика: учебник / Е.В. Филимонова. - 3-е изд., перераб. и доп. - М.: Дашков и К' , 2014. - 480 с.
Информатика: учебное пособие для вузов / С.А. Домрачев; В.П. Харьков. - М.: Национал. ин-т бизнеса, 2012. - 218с.
Информатика и информационные технологии: учебное пособие / И.Г. Лесничая; рук. авт. коллектива Ю.Д. Романова. - М.: Эксмо, 2012. - 543 с.
Информатика: учебное пособие для вузов / С.А. Домрачев; В.П. Харьков. - М.: Национал. ин-т бизнеса, 2012. - 218с.
Порублев И.Н. Алгоритмы и программы. – М.: МГУ, 2013. - 504 с.
Практикум по курсу «Информатика». Работа в Windows, Word, Excel: учебное пособие для вузов / В.Т. Безручко. - М.: Финансы и статистика, 2011. - 271 с.
Касаткин В.Н. Информация, алгоритмы. - М.: Омега, 2013. - 242 с.
Каймин В. А. Информатика: учебник для вузов. - 3-е изд.- М.: ИНФРА-М, 2011. - 271 с.
Каймин В. А. Информатика: учебник для вузов. - 4-е изд.- М.: ИНФРА-М, 2012. - 284 с.
Козырев А.А. Информатика: конспект лекций. - СПб.: Изд-во Михайлова В.А., 2013. - 46 с.
Кушниренко А.Г. и др. Информатика. - М.: Форум, 2012. - 335 с.
Кулаков А.Г. Алгоритмика. - М.: Кнорус, 2012. – 240 с.
Макарова Н. В. Информатика: практикум по технологии работы на компьютере: учебное пособие для экономических вузов. - М.: Финансы и статистика, 2013. - 255 с.
Марченко А.И. Программирование в среде. − М.: Экзамен, 2013. – 576 с.
Патрушина С. М. Информатика: учебное пособие.. - Ростов н/Д: МарТ, 2011. - 399 с.
Ставровский А.Б. Первые шаги в программировании. - М.: ИНФРА-М, 2011.- 275 с.
Томас Х. Алгоритмы: построение и анализ. - М.: Кнорус, 2011. – 208 с.
Фридланд А. Я. Информатика: толковый словарь основных терминов: учебное пособие для вузов. - М.: ПРИОР, 2012. – 240 с.