П.П. Кудрявцев

Курс лекций по дисциплине: «Информатика и программирование»

Барнаул 2007

П.П.Кудрявцев. Курс лекций по дисциплине: "Информатика и программирование"

2

3

П.П.Кудрявцев. Курс лекций по дисциплине: "Информатика и программирование"

Лекция 1. Поня тие алгори тма

Определение алгори тма

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль- Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло в Европе после перевода на латынь книги этого среднеазиатского математика, в которой его имя писалось как «Алгоритми».

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

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

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

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

Основными свойствами алгоритма являются:

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

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

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

4.Дискретность (модульность). Алгоритм можно представить в виде отдельных шагов (этапов), возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

5.Формальность способность исполнителя выполнить все шаги алгоритма , не понимая их смысла.

6.Понятность (единственность толкования).

Помимо этого, алгоритм имеет следующие важные особенности:

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

4

Лекция 1. Понятие алгоритма

время его работы.

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

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

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

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

Типы алгори тмов

Выделяют следующие виды алгоритмов:

1.Линейный (последовательный, следование, цепочка, составная инструкция)

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

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

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

Комбинированный алгоритм содержит несколько типов одновременно .

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

Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи алгоритмов:

1.естественный язык;

2.блок схемы;

3.алгоритмический язык;

5

П.П.Кудрявцев. Курс лекций по дисциплине: "Информатика и программирование"

Естественный язык

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

Пример. Нахождение наибольшего общего делителя (НОД) двух чисел алгоритм Евклида.

Шаг 1. Ввести 2 числа.

Шаг 2. Если числа равны, взять первое и закончить выполнение, в противном случае перейти к шагу 3.

Шаг 3. Определить большее число. Заменить большее число на разность большего и меньшего и перейти к шагу 2.

Достоинство: универсальность. Недостаток: неформальность.

Блок схемы

Наибольшее распространение благодаря своей наглядности получил графический (блок- схемный) способ записи алгоритмов.

Блок-схемой называется графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются государственными стандартами. В настоящий момент это ГОСТ 19.701-90 (ИСО 5807-85) .

Достоинства: наглядность, формальность.

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

Описание символов

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

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

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

6

Лекция 1. Понятие алгоритма

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

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

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

Часто используется при размещении блок-схемы на нескольких листах. Граница на одном листе помещается литерой A, а на другом листе начинается с соединителя в котором также присутствует литера A. При размещении на трех листах, в конце второго листа помещаем соединитель с литерой B и так далее.

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

7