лекция 7,8

Лекция Модели и алгоритмы (4 часа)

Вопросы:

1.Понятие модели

2.Моделирование как метод познания

3.Классификация моделей

1.Моделирование

1.1.Понятие модели

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

Любая модель каким-то образом соответствует объекту исследования, подобна ему. Причем подобие может быть:

1)по внешнему виду (похожесть);

2)по структуре (выделены составляющие элементы объекта и указаны их взаимосвязи);

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

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

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

Модели́рование — исследование объектов познания на их моделях; построение и изучение моделей реально существующих предметов, процессов или явлений с целью получения объяснений этих явлений, а также для предсказания явлений, интересующих исследователя.

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

В наиболее общем виде понятие «модель» чаще всего определяют следующим образом:

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

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

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

1.2. Классификация моделей. Виды и основные этапы построения модели

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

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

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

Информационные модели делятся на описательные и формальные.

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

Формальные информационные модели - это модели, созданные на формальном языке (т.е. научном, профессиональном или специализированном). Примеры формальных моделей: все виды формул, таблицы, графы, карты, схемы, алгоритмы, программы, БД и т.д.

Моделирование начинается с определения цели моделирования. Варианты цели:

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

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

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

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

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

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

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

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

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

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

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

1.Для восполнимых ресурсов (лес, рыба…) темпы потребления не должны превышать темпов естественного восстановления.

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

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

Модели, построенная в рамках проекта WORLD-3, охватывает временной промежуток 19002100 гг. Согласно модели, основанной на гипотезе, что не будет меняться отношение к окружающей среде и мир будет политически устойчивым, мы еще не достигли пика роста численности населения и роста объемов производства, которые приходятся примерно на 2020 г. (Временные шкалы неустойчивы). Далее следует снижение продолжительности жизни, численности населения, объема, как промышленного производства, так и продуктов питания. Ресурсы к 2100 году полностью истощаются. Модель, основанная на оптимистичном предположении, что соблюдаются правила стабилизации ресурсов дают иной результат.

2. Алгоритмы

Вопросы:

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

Основные свойства

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

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

Термин алгоритм (алгорифм) происходит от латинской формы имени среднеазиатского математика IX в. аль - Хорезми, который разработал правила выполнения четырех арифметических действий в десятичной системе счисления. Строгая теория алгоритмов возникла с внутренними проблемами теоретической математики в 1920-1930 гг. и ее появление связано с работами математиков Гильберта, Геделя, Черча, Поста, Тьюринга. Эта теория является пограничной областью знаний между математикой и информатикой. В настоящее время положения теории алгоритмов являются теоретической основой таких составных частей современной информатики как теория программирования, построение алгоритмических языков, анализ алгоритмов с целью выбора наиболее эффективного.

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

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

Под алгоритмом понимается «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» (ГОСТ 19.781-74).

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

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

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

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

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

2.массовость- алгоритм создается для целого класса задач.

3.дискретность- алгоритм допускает разбиение на отдельные простые блоки.

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

2.3. Объекты обработки в алгоритмах и программах

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

Константы - это такие данные (числа или символы), которые заданы в явном виде и не изменяются в процессе выполнения алгоритма или программы. Константы хранятся и обрабатываются под фиксированным именем, имеют неизменные тип и значение.

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

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

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

Присваивание - одно из основных действий, выполняемых ПК. В алгоритмах присваивание записывается знаком «=», или «:=».

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

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

(скалярными).

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

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

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

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

с помощью графического или словесного описания,

методом блок-схем,

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

Алгоритм на алгоритмическом языке в общем виде записывается в форме:

алг название алгоритм (аргументы и результаты)

дано условия применимости алгоритма надо цель выполнения алгоритма

нач описание промежуточных величин | последовательность команд (тело алгоритма)

кон

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

Пример вычисления суммы квадратов: алг Сумма квадратов (арг цел n, рез цел S)

кон

Обозначения, используемые в блок-схемах:

начало и завершение алгоритма

ввод-вывод данных

типовой процесс

подготовка цикла

условие

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

1. Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим:

Алгоритмический язык Язык блок-схем

действие 1 действие 2

. . . . . . . . .

действие n

2. Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:

если—то;

если—то—иначе;

выбор;

выбор—иначе.

1. если—то

если условие то действия

все

2. если—то—иначе

если условие то действия 1

иначе действия 2

все

3. выбор

выбор при условие 1: действия 1

при условие 2: действия 2

. . . . . . . . . . . .

при условие N: действия N

все

4. выбор—иначе

выбор при условие 1: действия 1

при условие 2: действия 2

. . . . . . . . . . . .

при условие N: действия N иначе действия N+1

все

выбор

при n = 1: y := sin(x) при n = 2: y := cos(x) при n = 3: y := 0

все

выбор

при a > 5: i := i+1 при a = 0: j := j+1 иначе i := 10; j:=0

все

3. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:

Цикл типа пока.

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.

нц пока условие тело цикла

(последовательность действий)

кц

Цикл типа для.

Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.

нц для i от i1 до i2

тело цикла (последовательность действий)

кц

Примеры структуры цикл

нц пока i <= 5 S := S+A[i] i := i+1

кц

нц для i от 1 до 5 X[i] := i*i*i Y[i] := X[i]/2

кц

2.5. Итерационные циклы

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

Пример. Составить алгоритм вычисления бесконечной суммы

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

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

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

Вложенные циклы

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

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

Пример вложенных циклов для

Вычислить сумму элементов заданной матрицы А(5,3).

Матрица А

S := 0;

нц для i от 1 до 5 нц для j от 1 до 3

S:=S+A[i,j]

кц

кц

Пример вложенных циклов пока

Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.

i:=2; P:=1

нц пока i <= 10 j:=2

нц пока j <= 10 P:=P*A[i,j] j:=j+2

кц

i:=i+2

кц

2.6. Формализация понятия алгоритма. Теория алгоритмов.

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

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