Лекция 7. Основы алгоритмизации изучить содержание понятий “алгоритм” и

вопросы
История термина алгоритм.
Понятие алгоритма.
Свойства алгоритмов.
Способы записи алгоритмов.
Простейшие структуры алгоритмов.
Литература
Кирнос

В.Н. Информатика 2. Основы алгоритмизации и программирования на языке C++ [Электронный ресурс]: учебно-методическое пособие/ Кирнос В.Н.— Электрон. текстовые данные.— Томск: Эль Контент, Томский государственный университет систем управления и радиоэлектроники, 2013.— 160 c

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

Информатика (1с)

– Абу Абдаллах (или Абу Джафар) Мухаммад ибн Муса ал

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

История термина алгоритм

который еще в IX в. (825 г.) дал правила выполнения

четырех арифметических действий в десятичной системе счисления.
Процесс выполнения арифметических действий был назван алгоризмом.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

смысл которого состоял в комбинировании четырех операций арифметического исчисления —

сложения, вычитания, умножения, деления.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

всего связывался с алгорифмами Евклида — процессами нахождения наибольшего общего

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

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

n, где m> n , сводится к построению убывающей последовательности

чисел
m, n, a1, a2, a3,…ak, ak+1, НУЛЬ.
Величина a1, равна остатку от деления числа m на число n, величина а2 равна остатку от деления числа n на число a1, величина а3 равна остатку от деления числа a1 на число a2 и т.д. Наибольший делитель чисел m и n равен ak+1, так как при делении ak на ak+1 получен остаток, равный нулю.
Пример: найти наибольший общий делитель 956 и 56.
Последовательность имеет вид: 956, 56,4, 0, так как 956=56x17+4, 56= 4х14 + 0. Соответственно 4 является наибольшим делителем чисел 956 и 56.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

теоретической математики. Математическая логика, основания математики, алгебра, геометрия и анализ

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

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

указать путь решения любой из этих задач (П.С. Новиков) .
Алгоритм

- это точное предписание, определяющее вычислительный процесс, ведущий от способных варьироваться исходных данных к результату (А.А. Марков).
Алгоритмом принято называть систему вычислений, которая для некоторого класса математических задач из записи А условий каждой задачи позволяет при помощи, однозначно определенной последовательности операций, совершаемых "механически", без вмешательства творческих способностей человека, полупить записи решения задачи (А.Н. Колмогоров, В.А. Успенский).
Государственный стандарт (ГОСТ 19.781-74) дает такое определение: «Алгоритм — это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату».

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

(алгоритмизация).
Написание программы.
Реализация программы на языке программирования.
Анализ результатов.
Информатика (1с)
Лекция 7. ОСНОВЫ

АЛГОРИТМИЗАЦИИ

Пример: составить алгоритм вычисления площади данного параллелограмма.

Решение:
Опустить высоту на одну из сторон.
Измерить длину h этой высоты.
Измерить длину а основания, на которое опущена высота h.
Перемножить а на h.

возможность получения искомого ре­зультата за конечное число операций (шагов).
Массовость возможность

применения алгоритма к не­которому классу однотипных (задач), различающихся конкретными значениями исходных данных.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

Существует различные способы записи алгоритма

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

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

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

Этот процесс может быть записан в виде следующей системы последовательных указаний:
Полагаем с равным единице и переходим к следующему указанию.
Полагаем i равным единице и переходим к следующему указанию.
Полагаем с равным ai ×ai+1, и переходим к следующему указанию.
Проверяем, равно ли i числу k. Если i = k, то вычисления прекращаем. Если i < k, то увеличиваем i на единицу и переходим к 3 указанию.

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

линиями связи (направление которых слева направо и сверху вниз принимается естественным).

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

ГОСТом 19.003-80 «СХЕМЫ АЛГОРИТМОВ И ПРОГРАММ.
ОБОЗНАЧЕНИЕ УСЛОВНЫЕ ГРАФИЧЕСКИЕ»

указанным именем
Информатика (1с)
Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

условия. Условие – выражение, находящееся между словами «если» и «то» и принимающее значение «истина» или «ложь».
Циклическая - схема состоит из последовательности действий, которые должны выполняться указанное число раз или пока не выполнено заданное условие.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

однократно в заданном порядке.

Каждый блок S описывает определенное конкретное преобразование

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

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

АЛГОРИТМИЗАЦИИ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

с логическим условием).
Циклы с заранее известным числом повторения (циклы

с параметром цикла).

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

раз?
Наклониться влево
Наклониться вправо
Сесть
конец
нет
да
Информатика (1с)
Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

В
Из числа А вычесть число В.
Если получилось отрицательное значение,

то сообщить, что число В больше.
Если получилось положительное значение, то сообщить, что число А больше.

4. Если получился ноль, то сообщить, что числа равны.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

площади треугольника.
Нахождения меньшего из трех чисел.
Информатика (1с)
Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

через реку волка, козу и капусту. Лодка может выдержать только

старика и одного «пассажира». В каком порядке старик перевезёт «пассажиров»? Не забудь, что волк может съесть козу, а коза – капусту. Найди два варианта решения.

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

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

Информатика (1с)

Лекция 7. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

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

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

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

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

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

памяти. В память также помещается программа на языке программирования высокого

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