Известные алгоритмы в истории информатики

1. Содержание 

1. Содержание…………………………………………………………………..…1

2. Введение………………………………………………………………………...2

3. Свойства  алгоритма…………………………………………………………….4

4. Виды  алгоритмов………………………………………………………….……5

     4.1. Линейные алгоритмы………………………………………………….5

     4.2. Разветвленные алгоритмы………………………………………….…6

     4.3. Циклические алгоритмы………………………………………………7

5. Способы  описания алгоритма………………………………………......……10

     5.1. Словесное описание алгоритма……………………………..……….10

     5.2. Графическое описание алгоритма……………………...…………...10

     5.3. Описание алгоритма на алгоритмическом языке……………..…....12

6. Заключение………………………………………………………………....….14

7. Литература………………………………………………………………….…15 
 
 
 
 
 
 
 
 
 
 

2. Введение

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

     Слово «Алгоритм» происходит от algorithmi -  латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика Мухаммеда иби Муса, жившего в 783-850 гг. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма процесс творческий, доступен лишь живым существам, долгое время считалось, что только человеку. Другое дело - реализация уже имеющегося алгоритма, которую можно поручить субъекту или объекту, который не обязан вникать в суть дела, может и не способен его понять – этот субъект (объект) принято называть формальным исполнителем.

     Исполнителем  алгоритма может быть и человек. Часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть  дверь ключом, перейти улицу и  т. д.: рецепты приготовления какого-либо лекарства или кулинарные рецепты  являются алгоритмами. На самом деле алгоритмы для людей никто  не составляет. Человек в принципе не может действовать по алгоритму. Выполнение алгоритма – это автоматическое, бездумное выполнение операций. Между тем исполнение алгоритма – это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, просто не было бы специальности – повар.

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

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

     Исполнителя характеризуют: среда; система команд; элементарные действия; отказы.

     Дальше  я более подробно расскажу о видах  алгоритма в информатике. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Свойства алгоритма

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

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

 

4. Виды алгоритмов

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

• линейные алгоритмы;
• разветвленные алгоритмы;
• циклические алгоритмы.

 

4.1. Линейные алгоритмы 

       Алгоритм линейной структуры представляет собой последовательность действий и не содержит каких-либо условий.

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

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

       Пример . Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника. Пусть a, b, c – длины сторон треугольнике. Необходимо найти S –площадь треугольника и P – периметр.

       Для нахождения площади можно воспользоваться формулой Герона:

4.2. Разветвленные алгоритмы

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

       

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

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

       Блок-схема  решения задачи. Блок 1 предназначен для ввода коэффициентов квадратного уравнения. В блоке 2 осуществляется вычисление дискриминанта. Блок 3 осуществляет проверку знака дискриминанта, если дискриминант отрицателен, то корни комплексные, их расчет происходит в блоке 4 (действительная часть корня записывается в переменную x₁, модуль мнимой - в переменную x₂), а вывод - в блоке 5 (первый корень x₁ + i x₂, второй - x₁- i x₂). Если дискриминант положителен, то вычисляются действительные корни уравнения (блок 6) и выводятся на экран (блок 7). 

         

4.3. Циклические алгоритмы 

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

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

• в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла;
• в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;
• в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.

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

     Пример. Найти наибольший общий делитель (НОД) двух натуральных чисел А и В.

Входные данные: А и В. 
Выходные данные: А - НОД.

     В блок-схеме решения задачи, представленной на рис. 2.5, для решения поставленной задачи используется цикл с предусловием, то есть тело цикла повторяется до тех пор, пока А не равно В.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5. Способы описания алгоритма

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

• словесное описание алгоритма (запись на естественном языке);
• графическое описание алгоритма (изображения из графических символов);
• описание алгоритма на алгоритмическом языке (псевдокоде).

5.1. Словесное описание алгоритма

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

     Пример: Найти корни квадратного уравнения.

     AX² + BX + C = 0

Ввести  величины A; B; C;

Вычислить дискриминант (D) по формуле: D = B² + 4AC;

Если  D <0, то действительных корней нет;

Если  D > 0, то переходим к пункту 5;

;

Вывести значения X₁ и X₂;