Лекция №2 Тема: «Алгоритм информационная модель явления, процесса или объекта»

Вид материала

Лекция

Содержание Алгоритм имеет некоторое число входных величин Иными словами Отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами Языки программирования Цель: выясним, что мы знаем об алгоритме, дадим ему определение с точки зрения информационного моделирования Информационная модель BeginWriteln(‘введите целое положительное число’)

Подобный материал:

• 1. Модель: определение, назначение. Классификация моделей, 785.34kb.
• 1. Модель: определение, назначение. Классификация моделей, 1027.74kb.
• Информационный процесс, 76.37kb.
• Первый общие вопросы моделирования и конструирования, 3407.38kb.
• Лекция 1 Тема: Введение в экономико-математическое моделирование, 121.17kb.
• Принципы имитационного моделирования, 125.46kb.
• 1. Понятие о моделях и моделировании, 341.94kb.
• Комплекс алгоритмов Алгоритм главного модуля Алгоритм прорисовки объекта, 102.47kb.
• Лекция №3 Применение эксперимента для построения математических моделей статики объектов, 134.24kb.
• Лекция 1 Тема Основные понятия Понятие план и прогноз, 70.48kb.

Лекция № 2

Тема: « Алгоритм — информационная модель явления, процесса или объекта»


УЭ-0 Интегрированная цель: опираясь на понятие и определение информационной модели дать определение алгоритму, его свойствам, средствам записи.


УЭ-1 Цель: выясним, что мы знаем об алгоритме, дадим ему определение с точки зрения информационного моделирования.


Задание (повторение):

1. Что такое модель? Какие классы моделей вы знаете? Что представляют собой информационные модели?
   
2. Привести определение алгоритма.
   

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

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

Ключевыми словами, раскрывающими смысл этого понятия, являются: исполнитель, команда, система команд исполнителя.

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

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

Обратим внимание на основные особенности алгоритма:

• Алгоритм имеет некоторое число входных величин - аргументов, задаваемых до начала работы.
  

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

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

Для алгоритма можно брать различные наборы входных данных, т.е. можно применять один и тот же алгоритм для решения целого класса однотипных задач, различающихся исходными данными. Это свойство алгоритма называют МАССОВОСТЬЮ.

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

• Чтобы алгоритм можно было выполнить, он должен быть ПОНЯТЕН исполнителю.Алгоритм, составленный на конкретного исполнителя, должен включать только те команды, которые входят в его систему команд, т е. Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем, не предусмотренных составителем алгоритма.
  
• Алгоритм представлен в виде КОНЕЧНОЙ последовательности шагов. Говорят, что алгоритм имеет дискретную структуру. Следовательно, его исполнение расчленяется на выполнение отдельных его шагов и должно завершиться за конечное их (шагов) число.
  
• Данное свойство ещё называется результативностью РЕЗУЛЬТАТИВНОСТЬ.
  

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

• Каждый шаг алгоритма должен быть четко и недвусмысленно (ОДНОЗНАЧНО) определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие - нибудь действия, отличные от предписанных алгоритмом.
  

Иными словами,

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

• Каждый шаг алгоритма должен быть выполнен точно и за конечное время, т.е. алгоритм должен быть эффективен. Следовательно, действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время.
  

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

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

• Кроме того, эффективность означает, что алгоритм может быть выполнен не только за конечное, а за разумное конечное время.
  

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

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

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

1. Словесная запись алгоритма. (ориентирована на исполнителя — человека.)
   

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

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

2. Схемы алгоритмов.
   

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

Для записи внутри блоков используется естественный язык с элементами математической символики. В результате проверки условий возникают два возможных пути продолжения алгоритма. Эти пути изображаются стрелками с соответствующими надписями «Да» и «Нет». Рассмотрим алгоритм «бытовой сферы» записанный двумя способами: словесной записью и с помощью схемы алгоритма

2. Псевдокоды
   

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

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

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

2. Языки программирования
   

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

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

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

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


УЭ-2 Цель: выясним, что мы знаем об алгоритме, дадим ему определение с точки зрения информационного моделирования.


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

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

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

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

• Естественный язык для словесно-пошагового способа записи алгоритма
  
• Искусственный язык блок-схем как графический способ записи алгоритмов
  
• Язык программирования
  

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

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

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

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

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

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

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

Когда метод решения задачи известен и ясна структура исходных данных, то построение алгоритма заключается в следующем:

1. определяется точная (оптимальная, простейшая) последовательность выполнения действий, предписанных методом решения;
   
2. выбирается способ записи (представления) алгоритма;
   
3. последовательность действий записывается по правилам этого способа.
   
4. формализация в этом случае сводится к «перекодированию» одного способа записи, например формульного, в другой, например вид блок-схемы. Запись алгоритма в виде блок-схем получила широкое распространение, потому что написание программы по блок-схеме может быть вполне формальной процедурой, поскольку каждому элементу блок-схемы в большинстве языков программирования в точности соответствует некоторый оператор языка
   

Пример:

Дано целое положительное число n. Присвойте переменной m последнюю цифру этого числа.

1.Введем обозначения для тех переменных, которые нам даны и являются существенными:
Дано: n-целое положительное число

Найти: m

Связь (метод решения): используя встроенную функцию нахождения остатка от деления мы можем найти последнюю цифру в записи числа и присвоить значение этой цифры переменной m

Ограничения: нет

2. Последовательная формализация алгоритма


Программа на Turbo Pascal 7.0


Program ex;


Var m,n : integer;


Begin


Writeln(‘введите целое положительное число’);

Readln(n);


m:=n mod 10;


writeln( ‘последняя цифра в записи числа равна’,m);

readln


end.



Блок-схема





Вопросы для самоконтроля

1. Что такое алгоритм?
   
2. Каковы основные свойства алгоритмов, сравните со свойствами информации?
   
3. Перечислите основные блоки, используемые в блок-схемах алгоритмов. Можно ли использовать для обозначения действий другие геометрические фигуры