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

План:

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

2. Язык блок-схем

3. Основные (базовые) структуры алгоритмов

                                             Алгоритмизация.

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

Алгоритм - формальное описание последовательности действий, которое необходимо выполнить  для решения задачи. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока, чье  имя – Мухаммед ибн Муса ал Хорезми. Он жил приблизительно с 783 по 850 гг.

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

 

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

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

Результативность (финитность, конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

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

Язык  блок-схем

    Язык блок схем -  способ формального описания алгоритмов.

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

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

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

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

 

Обработка данных                                                

(вычисление, пересылка и т.п.)

 

 

Вызов процедуры 

 

 

Проверка условия 

 

 

Соединительные линии и их объединение.

Ввод-вывод данных

 

Точки связи или соединители

 

      

Начало, завершение программы или  подпрограммы

Комментарий

    

 

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

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

Простая программа - алгоритм, для  которого:

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

 

Примеры простой и непростых программ:

Простая программа

 

Бесконечный цикл

 

 

Недостижимый  фрагмент

 

 

 

Основные (базовые) структуры алгоритмов и  их производные:

Следование  последовательное выполнение действий (блоков)

          

 

Цикл  «До» (с постусловием) - тело цикла (блок 2) выполняется до тех пор, пока условие (блок 3) не станет истинным

 

Цикл  «Пока» (с предусловием) - пока не будет  нарушено условие (блок 3), осуществляется  повторение тела  цикла (блок 2)

       

Разветвление -  применяется, когда в зависимости  от условия требуется выполнить  либо одно действие, либо другое

 

 

 

 

 

Обход - частный случай разветвления, когда  одна ветвь не содержит ни каких  действий

 

Множественный выбор - обобщение разветвления, когда  в зависимости от значения переменной I выполняется одно из нескольких действий

 

 

Алгоритмы вычисления суммы квадратов первых N целых чисел с использованием псевдокода и языка блок-схем

 

 

 

  Ввести  Число слагаемых                                                     

Сумма = 0

Номер = 1

do

   Сумма  = Сумма + Номер²

   Увеличить  Номер на единицу

Until

   Номер  > Число слагаемых

end-do

Напечатать  Сумму

 

 

 

 

 

 

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

 

 

 

Информация  была использована из локальной сети интернет.