Лекция 0

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

решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок».

годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча —

Тьюринга), Н. Винера, А. А. Маркова.

ЕДИНОГО «ИСТИННОГО» ОПРЕДЕЛЕНИЯ ПОНЯТИЯ «АЛГОРИТМ» НЕТ.

для решения конкретного множества задач и обладает пятью важными чертами:

конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информационные технологии»)

форме содержат следующий ряд общих требований:
Дискретность — алгоритм должен представлять

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

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

его систему команд.
Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
Результативность — завершение алгоритма определёнными результатами.
Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.

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

для исполнителя Pобота из школьного учебника [1] сpеда — это

бесконечное клеточное поле. Стены и закpашенные клетки тоже часть сpеды. А их pасположение и положение самого Pобота задают конкpетное состояние среды.
Система команд. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат — смещение Pобота на одну клетку ввеpх.
После вызова команды исполнитель совеpшает соответствующее элементаpное действие.
Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.

все полученные команды, не задавая вопросов "почему" и "зачем".
В

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

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

включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
программная (тексты на языках программирования).

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

языке.

натуральных чисел (алгоритм Эвклида).
Алгоритм может быть следующим:
задать два

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

должен приводить к решению поставленной задачи.
Недостатки:
Словесный способ не имеет

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

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

соответствует выполнению одного или нескольких действий.

блок-схемой.
В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений

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

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

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

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

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

строгие синтаксические правила для записи команд, присущие формальным языкам, что

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

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

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

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

комбинацией трех базовых структур: следование,   ветвление,   цикл.

следующих одно за другим:

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

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

некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов

представлены в таблице:

натуральные

Набор действий

Второй шаг:
Вывести Х => write(x);
Третий шаг
Уменьшаем Х на 1 =>

X:=X-1; (dec(x);)
Проверка конца работы
Число натуральное? => x>0
Цикл
Если х>0, перейти к второму шагу, иначе перейти на Конец
Конец

Второй шаг:
Число натуральное? => x>0; (если не натуральное в конец)
Третий

шаг
Вывести Х => write(x);
Четвёртый шаг
Уменьшаем Х на 1 => X:=X-1; (dec(x);)
Пятый шаг
Перейти к второму шагу
Конец

9 до 1)
Вывести Х => write(x);
Конец

точке 100:
0,5*x, если x100

Х:=0;
Второй шаг
Условие излома => x

шагу Три иначе к шагу Четыре
Третий шаг
Вычислить f(x) => y:=0.5*x;
Идти на пункт Конец цикла
Четвёртый шаг
Вычислить f(x) => y:=2*x;
Идти на пункт Конец цикла
Конец цикла
Вывести x -> f(x)
Увеличить х
Х в диапазоне => x<199
Если условие истина перейти к шагу Два иначе к Конец программы
Конец программыё

точках 5 и 15:
0, если x15
f(x)=
10, если x>=5

и x<=15

Х:=0;
Второй шаг
Условие излома => x>=5 и x

перейти к шагу Три иначе к шагу Четыре
Третий шаг
Вычислить f(x) => y:=10;
Идти на пункт Конец цикла
Четвёртый шаг
Вычислить f(x) => y:= 0;
Идти на пункт Конец цикла
Конец цикла
Вывести x -> f(x)
Увеличить х
Х в диапазоне => x<=20
Если условие истина перейти к шагу Два иначе к Конец программы
Конец программыё

неизвестно. Для его организации используется цикл типа   пока  .

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

 (для данной знакочере-дующейся бесконечной суммы требуемая точность будет достигнута,

когда очередное слагаемое станет по абсолютной величине меньше ).

 i-ом шаге частичной суммы  
S:=S + ((-1)**(i-1)) * (x**i)

/ i ,
мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой  р , то у следующего слагаемого числитель будет равен  —р*х   (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое  m  будет равно  p/i , где  i  — номер слагаемого.

некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая структура

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

А(5,3).

матрицы A(10,10), которые расположены на пересечении четных строк и четных

столбцов.

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

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

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

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

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

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

(Basic, Pascal, C и др.), которые предназначены для однозначного описания

алгоритмов; для решения задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения;
логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;
объектно-ориентированные (Object Pascal, Java, C++, C# и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

три его составляющие:

алфавит,
синтаксис,
семантика.

основных символов, т.е. "букв алфавита", из которых должен состоять любой

текст на этом языке — никакие другие символы в тексте не допускаются.

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

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

стандартными функциями, которые заранее запрограммированы и встроены в транслятор языка.

стандартными функциями, которые заранее запрограммированы и встроены в транслятор языка.

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

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

вида подпрограмм - процедуры и функции.
Процедуры и функции помещаются

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

имя процедуры (формальные параметры);
раздел описаний процедуры
begin

исполняемая часть процедуры

end;

(формальные параметры):тип результата;
раздел описаний функции
begin

исполняемая часть функции

end;

функций записываются в виде:

var имя праметра: имя типа

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

производится оператором, имеющим следующий формат:

имя процедуры(список фактических параметров);

массива }

var
fi: array [1..N] of integer; { описание

массива }
i: integer;
min_i,max_i,min,max: integer;

procedure Min_Max;
var i: integer;
begin
for i := 2 to N do
begin
if fi[i] > max then
begin
max:= fi[i];
max_i:=i;
end;
if fi[i] < min then

begin
min:= fi[i];
min_i:=i;
end;end;
write('index Minimal element = ',min_i);
write('index Maximal element =',max_i);
end;

begin
clrscr;
writeln ('введите массив размерностью N элементов');
for i:= 1 to N do {ввод элементов массива }
read(fi[i]);

min:=fi[1]; max:=fi[1];
min_i:=1; max_i:=1;

min_max;

end.

опускать знак умножения между сомножителями и ставить рядом два знака

операций.
Индексы элементов массивов записываются в квадратных (школьный АЯ, Pascal) или круглых (Basic) скобках.
Для обозначения переменных используются буквы латинского алфавита.
Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, потом умножение и деление и в последнюю очередь — сложение и вычитание.
Операции одного старшинства выполняются слева направо. Однако, в школьном АЯ есть одно исключение из этого правила: операции возведения в степень выполняются справа налево. Так, выражение   2**(3**2)  в школьном АЯ вычисляется как   2**(3**2) = 512. В языке QBasic аналогичное выражение   2^3^2   вычисляется как   (2^3)^2 = 64.     А в языке Pascal вообще не предусмотрена операция возведения в степень, в Pascal   x^y   записывается как   exp(y*ln(x)),   а   x^y^z   как   exp(exp(z*ln(y))*ln(x)).

1 (пропущен знак умножения между 5 и х)
a + sin

x (аргумент x функции sin x не заключен в скобки)
((a + b)/c**3 (не хватает закрывающей скобки)

e-mail: eart@ukr.net.
Также могут пригодиться материалы с сайта EART.HO.UA (разделы «Преподаватель\Материалы

для скачивания» и «Полезности»)