Понятие и свойство алгоритма. Способы записи алгоритма. Классы алгоритмов

Понятие и свойство алгоритма. Способы записи алгоритма. Классы алгоритмов

1.История алгоритма 4

2.Понятие алгоритма 5
3.Свойства алгоритма 5
4.Способы описания алгоритма 5

История алгоритма
Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.
Таким образом, мы видим, что латинизированное имя среднеазиатского ученого было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.
Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.


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

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

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

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

Например, нам хорошо известно, как открывать дверь ключом. Однако, чтобы научить этому малыша, придется четко разъяснить и сами действия, и порядок их выполнения.
Словесно-пошаговый способ описания алгоритма
Запишем алгоритм выполнения открывания двери:

1. 
   Достать ключ из кармана.
   
2. 
   Вставить ключ в замочную скважину.
   
3. 
   Повернуть ключ против часовой стрелки два раза.
   
4. 
   Вынуть ключ.
   
5. 
   Открыть дверь.
   

Словесно-пошаговый алгоритм передвижения из точки А в точку Б:

1. 
   Выйти из дома (точка А).
   
2. 
   Повернуть направо.
   
3. 
   Пройти один квартал до остановки.
   
4. 
   Сесть в автобус № 7, идущий через центр города.
   
5. 
   Проехать пять остановки.
   
6. 
   Выйти из автобуса.
   
7. 
   Найти по указанному адресу дом и квартиру (точка Б).
   

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

Описание алгоритма с помощью языка программирования

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