Пожалуйста, приостановите работу AdBlock на этом сайте.

В этом уроке разберём некоторые теоретические понятия, которые формализуют понятие программирования. Заодно точнее сформулируем основную задачу вашего обучения.

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

Рис.1 Скриншот игрового поля на code.org

Надеюсь, у вас всё получилось. Теперь на этом примере опишем несколько основных понятий:

• исполнитель;
• система команд исполнителя;
• алгоритм.

В игрушке мы управляем красной птичкой. Задача каждого этапа: добраться птичкой до свиньи. Птичка умеет выполнять определённые команды, например: переместить вперёд, повернуть налево, повернуть направо и др.

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

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

Необходимо заострить внимание на нескольких моментах.

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

Это означает, например, что нельзя написать исполнителю-птичке: «Иди к свинье!». Точнее записать можно, но только ничего не произойдёт, т.к. исполнитель таких команд не знает.

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

Исполнитель выполняет точно то, что предписывает ему алгоритм.

Исполнитель-птичка очень доверчивая. Она не подвергает сомнению то, что вы пишете в программе. Если, например, вы забудете развернуть птичку, то она врежется в стенку. Поэтому вы должны следить за всем самостоятельно.

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

Теперь от наглядного примера перейдём к компьютерным реалиям. Мы пишем программы для компьютера, а значит, компьютер в нашем случае является исполнителем. Система команд – стандартные функции и конструкции языка Си.

В чём состоит основная задача вашего обучения основам программирования? Овладеть навыком алгоритмического мышления. То есть научиться записывать решение различных задач в виде алгоритма для конкретного исполнителя (в нашем случае компьютера).

Итак, подытожим:

Компьютерная программа – алгоритм решения какой-либо задачи, записанный на языке программирования.

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

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

ТЕМА 8. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

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

"Алгоритм" является фундаментальным понятием информатики. Представление о нем необходимо для эффективного применения вычислительной техники к решению практических задач. Алгоритм - это предписание исполнителю (человеку или автомату) выполнить точно определенную последовательность действий, направленных на достижение заданной цели. Алгоритм - это сформулированное на некотором языке правило, указывающее на действия, последовательное выполнение которых приводит от исходных данных к искомому результату. Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ . Однако любой алгоритм, в отличие от рецепта или способа, обязательно обладает следующими свойствами.
Свойства алгоритма (отличающие его от любых других предписаний): понятность (для конкретного исполнителя); дискретность (команды последовательны, с точной фиксацией моментов начала и конца выполнения команды); точность (после выполнения каждой команды точно известно, завершено ли исполнение алгоритма или же какая команда должна выполниться следующей); результативность (после конечного числа шагов задача решается или же становится ясно, что процесс решения не может быть продолжен): массовость (алгоритм единым образом применяется к любой конкретной формулировке задачи, для которой он разработан).
1. Дискретность - разбиение алгоритма на ряд отдельных законченных действий - шагов. Выполнение алгоритма разбивается на последовательность законченных действий - шагов. Каждое действие должно быть закончено исполнителем алгоритма прежде, чем он приступит к исполнению следующего действия.
2. Точность - однозначные указания. На каждом шаге однозначно определено преобразование объектов среды исполнителя, полученной на предыдущих шагах алгоритма. Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат. Запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнять следующей.
3. Понятность - однозначное понимание и исполнение каждого шага алгоритма его исполнителем. Алгоритм должен быть записан на понятном для исполнителя языке.
4. Результативность - обязательное получение результата за конечное число шагов. Каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. Работа алгоритма должна быть завершена за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов. 5. Массовость - применение алгоритма к решению целого класса однотипных задач.
Система команд исполнителя - точно описанная обстановка, включающая формулировку решаемой задачи, перечень объектов, вовлекаемых в условие задачи и в ее решение, и возможности исполнителя: свойства объектов, которые он может узнать и действия, которые он может совершить. Формальное исполнение алгоритма производит компилятор или интерпретатор, проверяя семантику.

8.2. Способы записи алгоритма

На практике наиболее распространенными являются следующие формы записи алгоритмов:
1) графическая запись (блок-схемы);
2) словесная запись (псевдокоды);
3) язык программирования.
Словесная форма записи алгоритма представляет собой описание на естественном языке последовательных этапов обработки данных. Словесный способ не имеет широкого распространения, так как такие описания строго не формализуемы, допускают неоднозначность толкования отдельных предписаний. Алгоритм, записанный с помощью псевдокода, представляет собой полуформализованное описание на условном алгоритмическом языке, включающее как основные элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другие.
Графическая форма записи, называемая также схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Графическая запись является более компактной и наглядной по сравнению со словесной. В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий.
Графическая форма записи, называемая также структурной схемой или блок-схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В дальнейшем мы будем использовать блок-схемы алгоритмо в. Они позволяют представить алгоритмы в более наглядном виде, это дает возможность анализировать их работу, искать ошибки в их реализации и т.д. В блок-схемах всегда есть начало и конец , обозначаемые эллипсами, между ними - последовательность шагов алгоритма, соединенных стрелками .

Шаги бывают безусловными (изображаются прямоугольниками, параллелограммами) и условными (изображаются ромбами). Из ромба всегда выходят две стрелки - одна означает дальнейший путь, в случае выполнения условия (обозначается обычно словом "да" или "+"), другая - невыполнение (словом "нет" или "-"). Ввод с клавиатуры или вывод на экран значения выражения изображается параллелограммом. Команда, выполняющая обработку действий (команда присваивания), изображается в прямоугольнике.

Если решение задачи сложное и достаточно длинное, то алгоритм может получиться очень большим. Избежать этого можно, заменив некоторую законченную последовательность шагов алгоритма блоками, которые будут являться вспомогательными алгоритмами. Блок обычно не элементарен, его размеры выбираются в зависимости от необходимости, однако если он правильно составлен, то обладает всеми необходимыми признаками алгоритмического шага: имеет точку входа (четко выделенное начало) и может быть условным или безусловным. Разные блоки алгоритма связаны друг с другом только через точки входа и выхода, поэтому если блок верно решает свою задачу, то его внутренняя структура несущественна для остальной части алгоритма. Такое блочное представление особенно удобно на первых этапах решения сложных задач, когда детализация блоков производится позднее и, возможно, другими разработчиками.
Язык программирования - язык, используемый для формальной записи алгоритмов. Большинство языков программирования относятся к алгоритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой.
Язык, используемый для формальной записи алгоритмов, называется алгоритмическим языком . При описании любого языка (в том числе естественного, например, русского, английского и т.д.) используются следующие понятия: алфавит, синтаксис и семантика .
Алфавит языка - это множество простейших знаков, которые могут быть использованы в текстах этого языка. Последовательность символов алфавита называют словом . Правила, согласно которым образуются слова из алфавита, называются грамматикой. Сам же язык - это множество всех слов, записываемых в данном алфавите согласно данной грамматике.
Синтаксис - это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита. Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы.
Семантика - это набор правил, определяющих значение (смысл) отдельных конструкций языка.
Одним из самых распространенных алгоритмических языков является язык Pascal, который полезен как для начинающих, так и для опытных программистов. Обучение программированию чаще всего основывается на этом языке.

8.3. Основные алгоритмические конструкции

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

	Данный блок имеет один вход и один выход . Из простых команд и проверки условий образуются составные команды, имеющие более сложную структуру и тоже один вход и один выход . Структурный подход к разработке алгоритмов определяет использование только базовых алгоритмических структур (конструкций): следование, ветвление, повторение, которые должны быть оформлены стандартным образом.
	Рассмотрим основные структуры алгоритма. Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2 . Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры.
	Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1 , или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.
	Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P . Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа.
	Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S . Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы. Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел.
	В команде повторения с постусловием вначале выполняется действие S и лишь затем, проверяется условие P . Причем действие повторяется до тех пор, пока условие не соблюдается. Примером команды повторения с постусловием будет уменьшение положительного числа до тех пор, пока оно неотрицательное. Как только число становится отрицательным, команда повторения заканчивает свою работу. С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности.

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

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

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

8.5. Разветвляющийся алгоритм

Приведем пример записи разветвляющегося алгоритма для нахождения наибольшего из двух чисел.

8.6. Циклический алгоритм

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

Блок-схема состоит из следующих базовых структур: две составные команды (команда следования и команда повторения с предусловием), далее простая команда. Все команды соединены последовательно. Конструкции оформлены стандартным образом, поэтому их легко распознать и перевести на язык программирования. Каждая конструкция имеет один вход и один выход.
Пунктирные стрелки в таблице отражают последовательность выполнения технологической цепочки. После записи алгоритма в виде блок-схемы каждая команда переводится на школьный алгоритмический язык, а уже затем на язык программирования.
Запишем алгоритм вычисления суммы первых n натуральных чисел. Для этого воспользуемся циклом с параметром, поскольку заранее известно сколько раз будет выполняться команда нахождения суммы. Во всех звеньях цепочки поменяем цикл "пока" на цикл "для" и приведем пример перевода алгоритма с языка блок-схем на школьный алгоритмический язык и на язык программирования Pascal.

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

Вопросы для самоконтроля

1. Понятие алгоритма. Свойства алгоритма. Пример алгоритма. Понятие "переменная".
2. Оператор присваивания. Примеры.
3. Стили программирования (логический, функциональный).
4. Понятие подпрограммы, модуля и объекта
5. Что такое переменная? Правила наименования переменных в Паскале. Примеры.
6. Оператор присваивания. Запись выражений в Паскале. Примеры. Объяснить, как действует оператор x:=x+1;
7. Операторы ввода и вывода в Паскале. Примеры. Форматированный вывод.
8. Условный оператор (if ). Пример. Сравнить с оператором case .
9. Оператор выбора. Пример. Сравнить с оператором if .
10. Логические выражения. Операции or, and и not . Примеры. Таблица истинности.
11. Числовые типы переменных в языке Паскаль. Правила преобразования типов. Примеры.
12. Логический тип данных. Пример использования в программе. Символьный тип данных. Пример. Функции chr и ord , succ и pred .
13. Массивы. Определение. Индексы массивов. Объявления массивов. Обращения к элементам массива. Одномерные и двумерные массивы. Примеры. Сходство и различие массивов и строк.
14. Процедуры. Определение. Зачем нужны процедуры? Примеры. Правила описания процедур. Сравнить процедуры и функции.

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

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

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

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

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

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

Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

цель создания алгоритма (конечное состояние объекта);

систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

дискретность (алгоритм разбит на отдельные шаги - команды);

однозначность (каждая команда определяет единственно возможное действие исполнителя);

понятность (все команды алгоритма входят в систему команд исполнителя);

результативность (исполнитель должен решить задачу за конечное число шагов).

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

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

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

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

Типовые алгоритмические структуры

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

Линейная структура (следование)

Наиболее простой алгоритмической структурой является линейная . В ней все операции выполняются один раз в том порядке, в котором они записаны.

Ветвление

В полном ветвлении предусмотрено два варианта действий исполнителя в зависимости от значения логического выражения (условия). Если условие истинно, то выполняться будет только первая ветвь, иначе только вторая ветвь.

Вторая ветвь может быть пустой. Такая структура называется неполным ветвлением или обходом .

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

Цикл (повторение)

Цикл позволяет организовать многократное повторение одной и той же последовательности команд - она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы: «до », «пока », циклы со счётчиком. В циклах «до» и «пока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием ) или завершать цикл (цикл с послеусловием ).

Циклы «до » - повторение тела цикла до выполнения условия:

Циклы «пока » - повторение тела цикла пока условие выполняется (истинно):

Циклы со счётчиком (с параметром) – повторение тела цикла заданное число раз:

Вспомогательный алгоритм (подпрограмма, процедура)

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

Методы разработки сложных алгоритмов

Существует два метода разработки сложных алгоритмов:

Метод последовательной детализации задачи («сверху-вниз») состоит в том, что исходная сложная задача разбивается на подзадачи. Каждая из подзадач рассматривается и решается отдельно. Если какие-либо из подзадач сложны, они также разбиваются на подзадачи. Процесс продолжается до тех пор, пока подзадачи не сведутся к элементарным. Решения отдельных подзадач затем собираются в единый алгоритм решения исходной задачи. Метод широко используется, так как позволяет вести разработку общего алгоритма одновременно нескольким программистам, решающим локальные подзадачи. Это необходимое условие быстрой разработки программных продуктов.

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

Алгоритмы и процессы управления

Управление - целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие - управляемыми.

В простейшем случае таких объектов два:

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

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

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

В начало темы