Лекция по информатике на тему: "Алгоритм и его свойства"

Курс лекций по дисциплине «Физика»

преподаватель Русскова О.б.

Лекция № 14

Тема: Этапы решения задач на ЭВМ. Алгоритм и его свойства.

Слово «Алгоритм» происходит от algorithmi – латинского написания имени аль-Хорезми, под которым в средневековой Европе знали известного математика из Хорезма (город в современном Узбекистане) Мухаммеда Бен Муссу, который жил в 783 – 850 годах.

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

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

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

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

Те действия, которые может делать исполнитель, называются допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя. Объекты, над которыми исполнитель может выполнять действия, образуют так называемую среду исполнителя.

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

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

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

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

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

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

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

2.            Ветвление – это алгоритмическая структура, в которой та или иная серия команд выполняется в зависимости от истинности условия;

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

4.            Цикл – это алгоритмическая структура, в которой серия команд (тело цикла) выполняется многократно.

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

1.     В виде текстовых описаний:

Например: переменной i присвоить значение n.

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

Например: алг Присваивание

                        нач

                            i:=n

                        кон

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

алг – описание имени алгоритма и входящих в него переменных;

нач – начало алгоритма;

кон – конец алгоритма;

нц – начало цикла;

кц – конец цикла;

если – условие;

то – результат выполнения условия;

иначе – результат невыполнения условия;

пока – условие цикла.

3.     В виде блок схемы:

Например:

Правила отображения алгоритма в виде блок – схемы:

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

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Развитие языков программирования.

         В 50-е годы (начало развития ЭВМ) программы писались на машинном языке и представляли собой очень длинные последовательности из нулей и единиц. Составление и отладка таких программ было очень трудным делом.

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

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

          Одним из первых процедурных языков программирования был Бейсик (Basic), созданный в 1964 году. Позже появились другие его версии: MSX – Basic, Бейсик – Агат, QBasic и др. Другим из распространенных языков программирования алгоритмического типа является Pascal.

         В настоящее время наибольшей популярностью пользуются системы объектно-ориентированного визуального программирования: Microsoft Visual Basic и Borland Delphi. Для создания приложений в среде Windows&Office используется язык программирования Visual Basic for Applications (VBA).

Этапы решения задач на ЭВМ.

Решение прикладной задачи с применением ЭВМ состоит из нескольких этапов:

При выполнении этапов решения задач на ЭВМ применяется моделирование – это особая форма представления этапов решения задач на ЭВМ. Различают различные формы моделирования:

ü Информационная модель – это материальный или мысленно представленный объект, который используется вместо объекта оригинала и содержит информацию про наиболее важные для данного исследования свойства оригинала;

ü Математическая модель – замена объекта исследования соответствующим аналогом формул математических зависимостей (формула);

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

Модель необходима для того, чтобы:

- определить структуру, основные свойства и законы взаимодействия с другими объектами;

- обнаружить эффективные способы управления объектами при заданных целях и критериях по решению задачи;

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