Информатика - Зачет ...

Лекция 9 Основы алгоритмизации

 

Содержание

Введение2

Понятие алгоритма2

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

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

Условные графические обозначения4

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

Примеры построения блок - схем6

Введение

Слово «алгоритм» содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока - Мухаммеду ибн Мусе ал - Хорезми (Магомет, сын Моисея из Хорезма), жившего примерно в 783 - 850 гг. В латинских переводах с арабского арифметического трактата ал - Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово «алгоритм» - сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины последовательно определяются из исходных данных по определенным правилам - инструкциям.

Вплоть до 30-х годов нашего столетия понятие алгоритма оставалось интуитивным, имевшим скорее методологическое, чем математическое значение. К началу ХХ в. много ярких примеров алгоритмов дали алгебра и теория чисел.

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

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

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

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

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

Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки программирования ЭВМ. Например, микропрограммирование строится на идеях машин Тьюринга, структурное программирование заимствовало свои конструкции из теории рекурсивных функций, языки символьной обработки информации (РЕФАЛ, ПРОЛОГ) берут начало от нормальных алгоритмов Маркова и систем Поста.

 

 

Понятие алгоритма

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

 

Пример: Вычислить значение Y(X) по формуле: Y(X) = (АХ + В) * (СХ - D)

 

А умножить на Х (АХ = R1) → R1;

R1 сложить с В (R1+В = AX+B) → R2;

С умножить на Х (СХ = R3) → R3;

из R3 вычесть D (R3 – D = CX - D) → R4;

R2 умножить R4 (R2*R4 = (AX+B)*(CX-D) = Y(X)) → Y(X).

 

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

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

Исполнителя характеризуют:

1. Среда (обстановка) – «место обитания » исполнителя, а также состояние среды.

2. Система команд – команды некоторого заданного списка для исполнителя, где

по выполнению описывается достижения результат.

3. После вызова команды исполнитель совершает определенные элементарные

действия.

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

нее состоянии среды.

 

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

Точность - на каждом этапе алгоритма точно известно, что нужно делать

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

Массовость – с помощью одного алгоритма можно решать однотипные задачи и делать это неоднократно.

Конечность – результат достигается за конечное число шагов.

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

 

 

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

Известно три основных способа записи алгоритмов:

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

Программная – тексты на языках программирования.

Псевдокоды – описание на алгоритмическом языке.

Алгоритмический язык – это средство для записи алгоритмов в аналитическом виде, промежуточном между записью алгоритма на естественном языке и записью на языке ЭВМ.

4. Графический – в виде блоков. Каждый блок на этой схеме изображается

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

действий блокам соответствуют различные геометрические фигуры.

 

 

 

 

 

Условные графические обозначения

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

 

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Разветвляющий алгоритм схематически изображается так:

 

Полная форма записи Неполная форма записи

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Циклический тип алгоритма включает в себя цикл.

Цикл – часть алгоритма (подпрограммы), выполняемая многократно, каждый раз

при новых значениях параметра.

 

 

 

 

 

 

 

 

 

 

 

 

 

Примеры построения блок - схем

Пример 1. Составить алгоритм нахождения значения функции: Y(x) = x² + 1. В данном задании можно проследить признаки линейного типа алгоритма.

Прежде чем строить блок - схему для данного

задания, необходимо записать по шагам на

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

значение данной функции.

1. начало;

2. ввод переменной x;

3. Y(x) = x² + 1;

4. вывод Y(x);

5. конец.

 

 

 

 

 

 

 

Пример 2. Вывести на печать наибольшее из двух произвольных чисел A и B (A ≠ B).

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

разветвляющего типа алгоритма, т.к. явно

видно, что присутствует условие, которое

скрывается под сравнением (наибольшее

из двух произвольных чисел).

Описание на алгоритмическом языке:

1. начало;

2. ввод переменных А, В;

3. если A>B, то вывести на печать A

иначе В;

4. конец.

 

 

 

 

 

 

 

Пример 3. Задана последовательность чисел 3,5,7,…,21. Составить блок - схему вывода суммы всех элементов.

Данное задание на построение циклического типа алгоритма.

Итак, из условия задачи ясно, что дана

последовательность нечетных чисел,

отсюда выясняем, что нечетные числа

получаем прибавлением 2 к предыдущему

числу. Сумма подразумевает собой

накопление. А поскольку необходимо

найти сумму всех элементов

последовательности, то необходимо

зарегистрировать ячейку начальной суммы S₀.

+ - Т.о. получим:

x₀ = 3

x₁ = x₀ + 2 = 5

и т.д.

Т.е. x = x + 2

S₀ = 0 (начальная сумма), тогда

 

 

 

 

Запись на алгоритмическом языке: общая сумма равна S = S + x

1. начало;

2. x = 3;

3. S = 0;

4. пока x < 21, будет вычисляться S = S + x при x = x + 2 иначе вывод S;

5. конец.