Понятие алгоритма. Свойства. Основные характеристики

ЦЕЛЬ И СОДЕРЖАНИЕ КУРСА. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

ПОНЯТИЕ ИНФОРМАЦИИ. НОСИТЕЛИ ИНФОРМАЦИИ

ПРЕДСТАВЛЕНИЕ И ОБРАБОТКА ДАННЫХ

КОДИРОВАНИЕ ИНФОРМАЦИИ

ФАЙЛЫ И ФАЙЛОВАЯ СТРУКТУРА

Лекция 2. Модели решения функциональных и вычислительных задач: алгоритмизация и программирование. Основы алгоритмизации

ПЛАН

Понятие алгоритма. Свойства. Основные характеристики

Способы описания алгоритмов. Правила выполнения блок-схем

Информационные технологии решения задач Структуры алгоритмов

Понятие алгоритма. Свойства. Основные характеристики

Алгоритм^{^[1]}- понятное и точное предписание исполнителю совершить последовательность действий (набор операций и правил их чередования), направленных на достижение указанной цели или на решение поставленной задачи.

Алгоритмизация задачи - процесс разработки (проектирования) алгоритма решения задачи с помощью ПК на основе ее условия и требований к конечному результату.

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

- понятность;

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

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

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

- массовость.

Основные характеристики:

- временные;

- объемные.

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

Такой набор действий– система команд исполнителя.

2.2. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ.

ПРАВИЛА ВЫПОЛНЕНИЯ БЛОК-СХЕМ

Способы описания алгоритмов:

- словесный;

- графический (по "Единая система программной документации": ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения /ИСО 5807-85; ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения; ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические);

- псевдокоды;

- программный;

- табличный (используется на практике).

Табл. 1. Наиболее часто употребляемые символы

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

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

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

Стрелки, выходящие из блока решения, должны быть помечены соответствующими ответами (например, ДА, НЕТ), так чтобы были учтены все возможные ответы.

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

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

Символ "Документ" предназначен для ввода - вывода данных, носителем которых служит бумага.

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

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

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

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

2.3. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ РЕШЕНИЯ ЗАДАЧ. СТРУКТУРЫ АЛГОРИТМОВ

Рис.1

Структуры алгоритмов:

1. Линейная

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

Пример 1. Составить алгоритм и написать программу вычисления стоимости поездки на автомобиле на дачу (туда и обратно). Исходными данными являются: расстояние до дачи (км); количество бензина, которое потребляет автомобиль на 100 км пробега; цена одного литра бензина.

2. Разветвляющаяся

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

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

3. Циклическая

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

Пример 3. Составить алгоритм и написать программу, которая выводят y=x²в диапазоне от -10 до 10, с шагом 0,5.

^{^[1]} Происходит от имени узбекского ученого IX в. Аль-Хорезми, который в своем труде "Арифметический трактат", переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называли алгоритмами.