Введение
При изучении дисциплины «Информатика» студенты приобретают навыки пользования не только стандартными прикладными программными средствами, но и учатся выполнять все последовательные этапы решения задач на компьютере: правильно ставить задачу, определять технические и программные средства ее решения, при необходимости – самостоятельно разрабатывать дополнительные программные компоненты на языках высокого уровня. Важнейшим этапом освоения технологии решения задач на компьютере является развитие навыков разработки алгоритмов, их правильного представления в соответствии с общепринятыми стандартами, знание базовых алгоритмических структур.
Для повышения эффективности применения компьютера как инструмента решения задач необходимо освоение основной фундаментальной концепции подхода к использованию цифровых вычислительных средств. В информатике таким фундаментом является алгоритмизация возникающих задач. Алгоритмический стиль мышления позволяет связать воедино функционирование информации в конкретной прикладной среде с требованиями обработки информации на компьютере.
Алгоритмическое мышление помогает сформировать следующие основные навыки решения задач:
· умение правильно планировать структуру предстоящих действий для достижения заданной цели при помощи стандартного набора средств;
· строить информационные структуры для описания объектов и процессов в конкретной предметной области;
· правильно организовывать поиск информации, необходимой для решения задачи;
· четко и однозначно формулировать способ решения задачи в общепринятой форме и правильно понимать способ решения, предложенный другим разработчиком;
|
|
· формировать навыки анализа имеющейся информации, умения представлять ее в структурировном виде.
Развитие системного, логического мышления, освоение навыков оперирования формальными понятиями и объектами, характерными для используемых информационных технологий – это тот необходимый уровень, который формируется на базе правильного понимания алгоритмов и способов алгоритмизации.
Понятие алгоритма
Происхождение термина «алгоритм». Слово произошло от имени среднеазиатского ученого Аль-Хорезми (8–9 вв., Хорезм – историческая область на территории современного Узбекистана). В 1857 в библиотеке Кембриджского университета был найден перевод на латинский язык математической работы Аль-Хорезми, в котором имя Аль-Хорезми упоминается как Алгоритми, откуда и появилось слово «алгоритм». Оно стало особенно употребительным с появлением компьютеров для обозначения совокупности действий, составляющих какой-либо вычислительный процесс.
Термин «алгоритм» в бытовом понимании. В повседневной жизни выполнение каждой, даже простой задачи обычно осуществляется в несколько последовательных этапов (шагов). Например, такую цепочку шагов описывает инструкция для получения наличных денег со счета по банковской карте. Подобную инструкцию - четкую последовательность шагов в решении какой-либо жизненной задачи принято называть алгоритмом. Каждое отдельное действие – это шаг алгоритма.
Формализация понятия алгоритма, теория алгоритмов. Приведенное выше общее описание понятия алгоритма не всегда позволяет сравнить какие-либо две таким образом определенные инструкции. Можно, например, сравнивать два алгоритма решения системы уравнений и выбрать из них более подходящий, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т.е. отвлечься от существа решаемой алгоритмом задачи и выделить свойства алгоритмов, привлекая к рассмотрению только форму их записи.
|
|
Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, является одной из важнейших в теории алгоритмов. В этой теории предполагается, что каждый шаг алгоритма должен быть таков, что его может выполнить достаточно простое устройство (например - машина). Так, для уточнения понятия «алгоритм» и получения возможности математического исследования алгоритмов в 30-х г.г. ХХ века были предложены абстрактные вычислительные машины - машина Поста и машина Тьюринга. Эти механизмы, обладающие свойствами универсальности и простоты своей логической структуры, позволили решить проблему существования алгоритма решения любой практической задачи. В частности, было доказано, что если для решения задачи можно построить машину Поста-Тьюринга, то такая задача алгоритмически разрешима. Также была доказана возможность существования математических задач, для решения которых вообще не может существовать никакой алгоритм.
Вычислительный алгоритм. Это - упорядоченный набор основных математических и логический действий, однозначно определяющий процесс перехода от допустимых исходных данных задачи к конечному результату ее решения и обладающий свойствами массовости, конечности, определенности, детерминированности. Основные особенности вычислительных алгоритмов состоят в следующем.
|
|
Массовость – это возможность применять многократно один и тот же алгоритм к различным вариантам его исходных данных. Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так алгоритм сложения столбиком применим к любому конечному набору натуральных чисел. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель – тоже любым, но за исключением нуля.
Конечность - это обязательное наличие искомого результата после завершения алгоритма либо четкая фиксация причины, по которой результат не мог быть получен. Следует отметить, что на практике встречаются примеры формально бесконечных алгоритмов, например - алгоритм обработки данных системы абонентских пунктов банка. Этот алгоритм состоит в непрерывном повторении цепочки действий («идентифицировать клиента», «зафиксировать запрос клиента на транзакцию», «проверить допустимость транзакции», «выполнить транзакцию» и т.д.), выполняемых с определенной частотой (через каждую секунду, минуту, час) во все время функционирования данной банковской системы.
Определенность – это наличие на каждом шаге алгоритма у исполнителя достаточной информации для того, чтобы его можно было выполнить. Исполнителю также нужно четко знать, каким именно образом этот шаг выполняется. Сами шаги инструкции должны быть достаточно простыми, а исполнитель должен однозначно понимать смысл каждого из действий, составляющих алгоритм (например, при вычислении корней квадратного уравнения он должен понимать смысл вычисления дискриминанта).
Детерминированность – это отсутствие элементов случайности при выполнении алгоритма. При многократном применении алгоритма к одним и тем же исходным данным должен получаться всегда один и тот же результат. Поэтому, например, процесс преобразования информации, в котором участвует бросание монеты, не может быть назван алгоритмом.
Формы представления алгоритмов
Для записи алгоритма могут использоваться различные формы его представления.
Вербальная форма представления алгоритма предполагает запись алгоритма на русском языке (или любом другом естественном языке) в виде последовательности пронумерованных инструкций. Как правило, эта форма записи алгоритма громоздка, неудобна и недостаточно наглядна.
Например, в ней описание алгоритма нахождения НОД (наибольшего общего делителя) двух целых положительных чисел m и n может быть представлено в виде последовательности следующих четырех шагов:
Шаг 1: Сравнить m и n.
Шаг 2: Если m равно n, то m и есть исходный НОД, расчет окончен. Иначе перейти к шагу 3.
Шаг 3: Если m больше n, то уменьшить значение m на величину n и вернуться к шагу 1. Иначе перейти к шагу 4.
Шаг 4: Уменьшить значение n на величину m и вернуться к шагу 1.
Эта современная запись алгоритма нахождения НОД - весьма упрощенная. Запись, данная первоначально Евклидом, заполняет целую страницу текста, причем последовательность элементарных действий там значительно сложней.
Представление алгоритма в форме блок-схемы реализуется в виде набора геометрических элементов (блоков), соединенных стрелками. Каждый блок – это «шаг» алгоритма, его отдельное действие. Направление стрелок между блоками задает последовательность действий. В табл.1 представлены основные стандартные элементы блок-схем.
Таблица 1
| Название элемента | Обозначение | Пояснение |
| Пуск-останов |  
| Начало или конец вычислений. Внутри фигуры пишут: «начало» или «конец» соответственно |
| Ввод-вывод | 
| Операция ввода-вывода данных |
| Процесс | 
| Вычислительное действие или последовательность действий |
| Решение | 
| Проверка условия, указанного внутри фигуры |
| Модификатор | 
| Заголовок цикла с параметром |
| Предопределенный процесс | 
| Вычисления по подпрограмме |
| Документ | 
| Вывод данных на печать |
| Линия перехода | 
| Соединяет между собой блоки, указывая очередность их выполнения |
Элементы блок-схемы различаются по своему внешнему виду и назначению. Так, элементы, содержащие инструкции по каким-либо преобразованиям величин, обозначаются прямоугольниками, а элементы, содержащие проверку условий – ромбами. Операции ввода-вывода данных обозначаются параллелограммами. Начало и конец алгоритма обозначаются прямоугольниками с двумя скругленными противоположными сторонами, внутри которых пишут: «начало» или «конец» соответственно.
Из прямоугольника выходит единственная стрелка, входить в него может несколько стрелок. Из обеих острых вершин ромба выходят стрелки: одна из них помечается словом «да», другая – словом «нет», они задают дальнейшее направление вычислений в случае, соответственно, выполнения или невыполнения записанного внутри ромба условия.
Назначение и правила использования всех типов блоков приведены в табл.1 в графах Название элемента и Пояснение.
С использованием приведенных в табл.1 стандартных элементов вышеуказанный алгоритм нахождения НОД двух положительных целых чисел m и n примет вид блок-схемы на рис.1. Внутри блоков в ней знаком:= обозначена операция присваивания переменной величине, указанной слева от знака, ее значения, вычисляемого по формуле, стоящей справа от знака.
Блок-схемы наиболее удобно использовать для отображения уже разработанных, готовых алгоритмов, а также на начальных стадиях изучения программирования, так как они позволяют подключить к восприятию алгоритма наглядные зрительные образы производимых операций. Кроме того, на стадии проектирования сложных программ эта форма представления алгоритмов используется при формировании верхних уровней в иерархической структуре программ, а также - на нижних уровнях, если не полностью определены средства описания программ.
На стадиях детальной разработки сложных алгоритмов использование блок-схем оказывается неэффективным, так как запутанное переплетение многочисленных соединительных стрелок затрудняет понимание разрабатываемого алгоритма.
Представление алгоритма в форме псевдокода основано на описании этапов решения задачи с помощью ограниченного набора стандартных синтаксических конструкций. В псевдокоде, в частности, могут использоваться отдельные инструкции формальных алгоритмических языков программирования. Например, возведение X в степень A обозначается как X**A, извлечение квадратного корня из X обозначается как Sqrt (X).
Так же, как в формальных языках программирования, в псевдокоде присутствуют ключевые слова, смысл которых заранее оговорен и фиксирован. В табл.2 приведен базовый перечень ключевых слов.
В качестве ключевых могут использоваться также соответствующие английские слова-аналоги: else вместо иначе, then вместо то, и т.д.
В самом общем виде запись алгоритма в форме псевдокода выглядит следующим образом:
алг название алгоритма ( аргументы - входные параметры и параметры - результаты работы алгоритма )дано | условия применимости алгоритма надо | цель выполнения алгоритма нач описание промежуточных (внутренних) величин алгоритма команда 1; команда 2; … команда N кон
Здесь часть записи от слова алг до слова нач называется заголовком алгоритма, а часть, заключенная между словами нач и кон - его телом. Внутри тела также могут встречаться слова нач и кон, группа команд между нимиобразует свой отдельный блок команд. Команды отделяются друг от друга символом «;».
Сразу после названия алгоритма в круглых скобках указываются характеристики (арг или рез) и тип значения(цел, вещ, сим, лог или таб) всех входных (арг) и выходных (рез) величин. При описании массивов служебное слово таб дополняется граничными парами значений по каждому индексу элементов массива.
Таблица 2
| Ключевое слово | Пояснение |
| алг | Начало описания алгоритма |
| арг | Входные данные (аргументы) алгоритма |
| вещ | Вещественный тип данных |
| все | Конец команды ветвления вычислений |
| да | Логическая константа «TRUE» |
| дано | Описание условий применимости алгортима |
| до | Конечное значение параметра цикла |
| и | Логическая связка «И» |
| или | Логическая связка «ИЛИ» |
| иначе | Часть конструкции если … то … иначе … |
| кон | Конец всего алгоритма или блока команд |
| кц | Конец цикла |
| лит | Символьный (литерный) тип данных |
| лог | Логический (булевский) тип данных |
| надо | Описание цели алгоритма |
| нач | Начало тела алгоритма или блока команд |
| нет | Логическая константа «FALSE» |
| нц | Начало цикла |
| от | Начальное значение параметра цикла |
| рез | Выходные данные (результаты) алгоритма |
| таб | Табличный тип данных (массив данных) |
| то | Часть конструкции если … то … иначе |
| цел | Целый тип данных |
| шаг | Шаг изменения параметра цикла |
В конце любой строки в текст псевдокода после знака «|» можно вставлять комментарий, облегчающий понимание алгоритма.
Разделы дано и надо в записи алгоритма не являются обязательными.
К числу основных действий, составляющих тело алгоритма, относятся команды ввода-вывода, присваивания, перехода, ветвления и циклов. Для обозначения этих команд используются соответствующие ключевые слова.
Команда ввода: ключевое слово ввод, за которым указываютсяимена переменных, для которых вводятся значения. Например, команда ввод a,b,c означает ввод значений соответственно для переменных a,b,c.
Команда вывода: ключевое слово вывод, за которым следуютимена выводимых переменных, выводимые выражения и тексты (тексты помещаются в кавычки). Например, команда вывод "S = ", S означает вывод имени переменной S, за которым после знака равенства = следует вывод текущего значения этой переменной.
Команды присваивания используются для вычисления выражений и присваивания их значений переменным. Общий вид команды: "переменная":="выражение", где знак ":=" означает команду замены прежнего значения переменной, стоящей в левой части, на вычисленное значение выражения, стоящего в правой части. Например, команда x:= y + z означает присваивание переменной x значения суммы величин y и z, а команда k:= k+1 означает увеличение текущего значения переменной k на единицу.
Команда перехода : ключевые слова идти к, после которых указывается номер той строки, команда которой должна выполняться следующей. Таким образом, команда перехода изменяет естественную последовательность выполнения команд по возрастанию номеров строк. Например, записанная в 5-й строке команда идти к 10 означает, что далее должна выполняться команда, записанная в 10-й строке, а не команда, записанная в следующей 6-й строке.
Для организации ветвлений вычислительного процесса применяются команды, начинающиеся с ключевых слов если и выбор, циклические вычисления организуются с помощью команд, начинающихся с ключевых слов пока и для. Подробно эти команды рассмотрены далее при описании базовых структур алгоритмов.
С использованием псевдокода вышеуказанный алгоритм нахождения НОД двух положительных целых чисел m и n примет следующий вид:
1. алг Наибольший Общий Делитель (арг цел m, n, рез цел nod)
2. дано | положительные целые числа m, n
3. надо | nod – наибольший общий делитель чисел m, n
4. нач
5. ввод m, n;
6. если m = n то идти к 9 все;
7. если m > n то m:= m - n иначе n:= n – m все;
8. идти к 6;
9. nod:= m;
10. вывод “Значение НОД равно”, nod
11. кон
Эта форма представления облегчает запись алгоритма на стадии его проектирования и дает возможность в дальнейшем легко перевести алгоритм в более широкий набор команд формального языка программирования.