Алгоритм: понятие, свойства, виды

ЦЕНТРАЛЬНЫЙ ФИЛИАЛ

Кафедра правовой информатики, информационного права

И естественнонаучных дисциплин

Утверждаю

Заведующий кафедрой

к.т.н., доцент

А.В. Мишин

«____» _______ 2011 г.

ПЛАН

Практического занятия

Дисциплина: «Информационные технологии в юридической деятельности»

Тема 6: «Основы алгоритмизации»

Разработал:

профессор кафедры

д.т.н., доцент

Л.Е. Мистров

Материалы обсуждены и одобрены

на заседании кафедры ПИИПЕД,

протокол № 1 от « 29 » августа 2011г.

Воронеж — 2011

План проведения занятия

Тема 6.2. Основы алгоритмизации

Учебные вопросы Время, мин.
Вступительная часть. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Основные понятия моделирования систем, процессов и явлений 2. Алгоритм: понятие, свойства, виды. . . . . . . . . .. . . . . . . . . . . 3. Представление алгоритмов с помощью схем . . . . . . . . . . . . . . 4. Описание алгоритмов с помощью псевдокода. . . . . . . . . .. . . Заключительная часть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Литература

основная:

1. Мистров Л.Е. Информатика и математика: информатика / Л.Е. Мистров, А.Ю. Кузьмин, С.А. Мишин. – Воронеж, Научная книга, 2008. – 282 с.

2. Информатика для юристов и экономистов: учебник для вузов / Под ред. С.В. Симоновича. — СПб.: Питер, 2004. — 688 с.

дополнительная:

1. Информатика: практикум по технологии работы на компьютере / Под ред. Н.В. Макаровой. — М.: Финансы и статистика, 2003. — 256 с.

2. Кормен Т.Х. Алгоритмы: построение и анализ / Т.Х. Кормен, Ч.И. Лейзерсон, Л.Р. Рональд. — Вильямс, 2005. — 1296 с.

3. Острейковский В.А. Информатика: учебник для студентов вузов / В.А. Острейковский. — М.: Высшая школа, 2001. — 511 с.

4. Попов В.Б. Основы компьютерных технологий / В.Б. Попов. — М.: Финансы и статистика, 2002. — 704 с.

Содержание занятия и методика его проведения

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

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

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

Основные понятия моделирования систем, процессов и явлений

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

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

Объект (система, (процесс, явление) Эксперимент (информация об объекте) Модель объекта Изучение модели объекта Коррекция модели объекта

Исходя из этого, модель включает в себя: объект О, субъект (не обязательно) А, задачу Z, ресурсы B, среду моделирования С: М=.

Модель используется того, чтобы:

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

2. определить наиболее важные связи (качественные) внутри структуры;

3. установить качественно-количественные связи;

4. прогнозировать изменения объекта и среды при определенных воздействиях;

5. провести оптимизацию объекта и (или) внешних воздействий на него.

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

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

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

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

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

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

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

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

Задача моделирования состоит в:

построении модели (задача мало формализуема и конструктивна, так как нет алгоритмов для построения моделей);

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

применении модели (задача конструктивна и конкретизируема).

Модель М, описывающая объект , имеет вид: , где , , – множества отношений над X – множеством входной, выходной информации и состояний объекта, Z – множество описаний, представлений элементов и подмножеств X. Обобщенная схема построения модели М объекта О с входными сигналами X и выходными сигналами Y изображена на рис. 1. Если на вход М поступает информация из X и на входе появляется информация Y, то задан закон, правило функционирования модели, объекта.

Алгоритм: понятие, свойства, виды

Рис. 1. Схема построения модели

Исходя из различных классификаций различают модели:

статические, если среди параметров описания, нет временного параметра; модель в каждый момент времени дает лишь фотографию объекта, его срез;

динамические, если среди параметров есть временной параметр, т.е. модель отображает объект (процессы) во времени;

дискретные, если они описывают поведение объекта в дискретные моменты времени;

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

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

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

функциональные, если они представимы в виде системы каких-либо функциональных соотношений;

игровые, если они описываю некоторую игровую ситуацию между участниками игры (лицами, коалициями) и т.д.

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

Разработка любой модели основывается на основе учета свойств:

l целенаправленности – модель всегда отображает некоторый объект, т.е. имеет цель;

l конечности – модель отображает оригинал лишь в конечном числе его отношений и, кроме того, ресурсы моделирования конечны;

l упрощенности – модель отображает только существенные стороны объекта и должна быть проста для исследования или воспроизведения;

l приблизительности – действительность отображается моделью приблизительно;

l адекватности – описывать моделируемый объект;

l наглядности, обозримость основных ее свойств и отношений;

l информативности – содержать достаточную информацию об объекте (в рамках гипотез, принятых при построении модели) и давать возможность получить новую информацию;

l сохранения информации, содержавшейся в оригинале (с точностью рассматриваемых при построении модели гипотез);

l полноты – должны быть учтены все основные связи и отношения, необходимые для обеспечения цели моделирования;

l устойчивости – должна описывать и обеспечивать устойчивое поведение объекта, если даже она вначале является неустойчивой;

l целостности – реализует некоторый объект или процесс (т.е. целое);

l замкнутости – учитывает и отображает замкнутую систему необходимых основных гипотез, связей и отношений;

l адаптивности – модель может быть приспособлена к различным входным параметрам, воздействиям окружения;

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

Алгоритм: понятие, свойства, виды

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

Алгоритм — точное и понятное предписание совершения последовательности действий, направленных на решение поставленной задачи, ведущие от исходных данных к искомому результату. Название «алгоритм» произошло от латинской формы имени среднеазиатского математика аль-Хорезми — Algorithmi.

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

Исполнителя (компьютер) характеризуют: среда, элементарные действия, система команд, отказы.

Среда (или обстановка) — это «место обитания» исполнителя, определяемое пространственные, временные и другие условия существования объекта и ограничения.

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

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

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

понятность — исполнитель алгоритма должен знать, как его выполнять;

дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов (этапов);

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

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

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

Способы записи алгоритмов — наиболее распространены следующие формы представления алгоритмов:

словесная (записи на естественном языке);

графическая (изображения из графических символов);

псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

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

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

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

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

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

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

Алгоритмы. Виды и свойства алгоритмов


Похожие статьи.

Понравилась статья? Поделиться с друзьями: