Математическое моделирование, численные методы и комплексы программ

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ» К Р АТ К ИЙ К У Р С Л Е К ЦИЙ по дисциплине Математическое моделирование, численные методы и комплексы программ Код и направление подготовки 09.06.01 – Информатика и вычислительная техника Наименование профиля / программы подготовки научнопедагогических кадров в аспирантуре Математическое моделирование, численные методы и комплексы программ Квалификация (степень) выпускника Исследователь. Преподаватель исследователь. Факультет Прикладной информатики Кафедра – разработчик Информационных систем Ведущий преподаватель Краснодар 2015 Попова Елена Витальевна ЛЕКЦИЯ 1 Тема 1. Методы математического моделирования Основные принципы математического моделирования Принципы определяют общие требования, которым должна удовлетворять правильно построенная модель. Рассмотрим эти принципы. 1. Адекватность. Этот принцип предусматривает соответствие модели целям исследования по уровню сложности и организации, а также соответствие реальной системе относительно выбранного множества свойств. До тех пор, пока не решен вопрос правильно ли отображает модель исследуемую систему, ценность модели незначительна. 2. Соответствие модели решаемой задаче. Модель должна строиться для решения определенного класса задач или конкретной задачи исследования системы. Попытки создания универсальной модели, нацеленной на решение большого числа разнообразных задач, приводят к такому усложнению, что она оказывается практически непригодной. Опыт показывает, что при решении каждой конкретной задачи нужно иметь свою модель, отражающую те аспекты системы, которые являются наиболее важными в данной задаче. Этот принцип связан с принципом адекватности. 3. Упрощение при сохранении существенных свойств системы. Модель должна быть в некоторых отношениях проще прототипа — в этом смысл моделирования. Чем сложнее рассматриваемая система, тем по возможности более упрощенным должно быть ее описание, умышленно утрирующее типичные и игнорирующее менее существенные свойства. Этот принцип может быть назван принципом абстрагирования от второстепенных деталей. 4. Соответствие между требуемой точностью результатов моделирования и сложностью модели. Модели по своей природе всегда носят приближенный характер. Возникает вопрос, каким должно быть это приближение. С одной стороны, чтобы отразить все сколько-нибудь существенные свойства, модель необходимо детализировать. С другой стороны, строить модель, приближающуюся по сложности к реальной системе, очевидно, не имеет смысла. Она не должна быть настолько сложной, чтобы нахождение решения оказалось слишком затруднительным. Компромисс между этими двумя требованиями достигается нередко путем проб и ошибок. Практическими рекомендациями по уменьшению сложности моделей являются: o изменение числа переменных, достигаемое либо исключением несущественных переменных, либо их объединением. Процесс преобразования модели в модель с меньшим числом переменных и ограничений называют агрегированием. Например, все типы ЭВМ в модели гетерогенных сетей можно объединить в четыре типа — ПЭВМ, рабочие станции, большие ЭВМ (мейнфреймы), кластерные ЭВМ; o изменение природы переменных параметров. Переменные параметры рассматриваются в качестве постоянных, дискретные — в качестве непрерывных и т.д. Так, условия распространения радиоволн в модели радиоканала для простоты можно принять постоянными; o изменение функциональной зависимости между переменными. Нелинейная зависимость заменяется обычно линейной, дискретная функция распределения вероятностей — непрерывной; o изменение ограничений (добавление, исключение или модификация). При снятии ограничений получается оптимистичное решение, при введении — пессимистичное. Варьируя ограничениями можно найти возможные граничные значения эффективности. Такой прием часто используется для нахождения предварительных оценок эффективности решений на этапе постановки задач; o ограничение точности модели. Точность результатов модели не может быть выше точности исходных данных. 5. Баланс погрешностей различных видов. В соответствии с принципом баланса необходимо добиваться, например, баланса систематической погрешности моделирования за счет отклонения модели от оригинала и погрешности исходных данных, точности отдельных элементов модели, систематической погрешности моделирования и случайной погрешности при интерпретации и осреднении результатов. 6. Многовариантность реализаций элементов модели. Разнообразие реализаций одного и того же элемента, отличающихся по точности (а следовательно, и по сложности), обеспечивает регулирование соотношения «точность/сложность». 7. Блочное строение. При соблюдении принципа блочного строения облегчается разработка сложных моделей и появляется возможность использования накопленного опыта и готовых блоков с минимальными связями между ними. Выделение блоков производится с учетом разделения модели по этапам и режимам функционирования системы. К примеру, при построении модели Для системы радиоразведки можно выделить модель работы излучателей, модель обнаружения излучателей, модель пеленгования и т.д. В зависимости от конкретной ситуации возможны следующие подходы к построению моделей: • непосредственный анализ функционирования системы; • проведение ограниченного эксперимента на самой системе; • использование аналога; • анализ исходных данных. Имеется целый ряд систем, которые допускают проведение непосредственных исследований по выявлению существенных параметров и отношений между ними. Затем либо применяются известные математические модели, либо они модифицируются либо предлагается новая модель. Таким образом, например, можно вести разработку модели для направления связи в условиях мирного времени. При проведении эксперимента выявляется значительная часть существенных параметров и их влияние на эффективность системы. Такую цель преследуют, например, все командно-штабные игры и большинство учений. Если метод построения модели системы не ясен, но ее структура очевидна, то можно воспользоваться сходством с более простой системой, модель для которой существует. К построению модели можно приступить на основе анализа исходных данных, которые уже известны или могут быть получены. Анализ позволяет сформулировать гипотезу о структуре системы, которая затем апробируется. Так появляются первые модели нового образца иностранной техники при наличии предварительных данных об их технических параметрах. Разработчики моделей находятся под действием двух взаимно противоречивых тенденций: стремления к полноте описания и стремления к получению требуемых результатов возможно более простыми средствами. Достижение компромисса ведется обычно по пути построения серии моделей, начинающихся с предельно простых и восходящих до высокой сложности (существует известное правило: начинай с простых моделей, а далее усложняй). Простые модели помогают глубже понять исследуемую проблему. Усложненные модели используются для анализа влияния различных факторов на результаты моделирования. Такой анализ позволяет исключать некоторые факторы из рассмотрения. Сложные системы требуют разработки целой иерархии моделей, различающихся уровнем отображаемых операций. Выделяют такие уровни, как вся система, подсистемы, управляющие объекты и др. ЛЕКЦИЯ 2 Тема 1. Методы математического моделирования Основные принципы математического моделирования Вариационные принципы. Еще один подход к построению моделей, по своей широте и универсальности сопоставимый с возможностями, даваемыми фундаментальными законами, состоит в применении так называемых вариационных принципов. Они представляют собой весьма общие утверждения о рассматриваемом объекте (системе, явлении) и гласят, что из всех возможных вариантов его поведения (движения, эволюции) выбираются лишь те, которые удовлетворяют определенному условию. Обычно согласно этому условию некоторая связанная с объектом величина достигает экстремального значения при его переходе из одного состояния в другое. Применение аналогий при построении моделей. В огромном числе случаев при попытке построить модель какого-либо объекта либо невозможно прямо указать фундаментальные законы или вариационные принципы, которым он подчиняется, либо, с точки зрения наших сегодняшних знаний, вообще нет уверенности в существовании подобных законов, допускающих математическую формулировку. Одним из плодотворных подходов к такого рода объектам является использование аналогий с уже изученными явлениями. Что, казалось бы, общего между радиоактивным распадом и динамикой популяций, в частности изменением численности населения нашей планеты? Однако на простейшем уровне такая аналогия вполне просматривается, о чем свидетельствует одна из простейших моделей популяций, называемая моделью Мальтуса. Иерархический подход к получению моделей. Лишь в редких случаях бывает удобным и оправданным построение математических моделей даже относительно простых объектов сразу во всей полноте, с учетом всех факторов, существенных для его поведения. Поэтому естествен подход, реализующий принцип "от простого — к сложному", когда следующий шаг делается после достаточно подробного изучения не очень сложной модели. При этом возникает цепочка ( иерархия ) все более полных моделей, каждая из которых обобщает предыдущие, включая их в качестве частного случая. О нелинейности математических моделей. Простота рассмотренных выше моделей во многом связана с их линейностью. В математическом плане это важное понятие означает, что справедлив принцип суперпозиции, т. е. любая линейная комбинация решений (например, их сумма) также является решением задачи. Пользуясь принципом суперпозиции, нетрудно, найдя решение в каком-либо частном случае, построить решение в более общей ситуации. Поэтому о качественных свойствах общего случая можно судить по свойствам частного - различие между двумя решениями носит лишь количественный характер. Например, в случае линейных моделей отклик объекта на изменение каких-то условий пропорционален величине этого изменения. Для нелинейных явлений, математические модели которых не подчиняются принципу суперпозиции, знание о поведении части объекта еще не гарантирует знания поведения всего объекта, а его отклик на изменение условий может качественно зависеть от величины этого изменения. Большинство реальных процессов и соответствующих им математических моделей нелинейны. Линейные же модели отвечают весьма частным случаям и, как правило, служат лишь первым приближением к реальности. Этапы построения моделей. Процесс построения моделей может быть условно разбит на следующие этапы. 1. Конструирование модели начинается со словесно-смыслового описания объекта или явления. Помимо сведений общего характера о природе объекта и целях его исследования эта стадия может содержать также некоторые предположения (невесомый стержень, толстый слой вещества, прямолинейное распространение световых лучей и т.д.). Данный этап можно назвать формулировкой предмодели. 2. Следующий этап завершение идеализации объекта. Отбрасываются все факторы и эффекты, которые представляются не самыми существенными для его поведения. Например, при составлении баланса материи не учитывался, ввиду его малости, дефект масс, которым сопровождается радиоактивный распад. По возможности идеализирующие предположения записываются в математической форме, с тем чтобы их справедливость поддавалась количественному контролю. 3. После выполнения первых двух этапов можно переходить к выбору или формулировке закона ( вариационного принципа, аналогии и т.п.), которому подчиняется объект, и его записи в математической форме. При необходимости используются дополнительные сведения об объекте, также записываемые математически (например, постоянство величины с для всех траекторий лучей света, вытекающее из геометрии задачи). Следует иметь в виду, что даже для простых объектов выбор соответствующего закона отнюдь не тривиальная задача. 4. Завершает формулировку модели ее "оснащение". Например, необходимо задать сведения о начальном состоянии объекта (скорость ракеты и ее массу в момент t = 0 ) или иные его характеристики, без знания которых невозможно определить поведение объекта. И, наконец, формулируется цель исследования модели (найти закон преломления света, достичь понимания закономерностей изменения популяции, определить требования к конструкции ракеты, запускающей спутник, и т. д.). 5. Построенная модель изучается всеми доступными исследователю методами, в том числе со взаимной проверкой различных подходов. В отличие от рассматриваемых простейших случаев, большинство моделей не поддаются чисто теоретическому анализу, и поэтому необходимо широко использовать вычислительные методы. Это обстоятельство особенно важно при изучении нелинейных объектов, так как их качественное поведение заранее, как правило, неизвестно. 6. В результате исследования модели не только достигается поставленная цель, но и должна быть установлена всеми возможными способами (сравнением с практикой, сопоставлением с другими подходами) ее адекватность - соответствие объекту и сформулированным предположениям. Неадекватная модель может дать результат, сколь угодно отличающийся от истинного, и должна быть либо отброшена, либо соответствующим образом модифицирована. ЛЕКЦИЯ 3. Тема 2. Методы математического моделирования Методы исследования математических моделей Все методы математического моделирования можно разделить на четыре класса: аналитические (априорные); имитационные (априорно-апостериорные) модели; эмпирико-статистические (апостериорные) модели; модели, в которых в той или иной форме представлены идеи искусственного интеллекта (самоорганизация, эволюция, нейросетевые конструкции и т.д.). налитические модели (англ. analytical models) – один из классов математического моделирования, широко используемый в экологии. При построении таких моделей исследователь сознательно отказывается от детального описания экосистемы, оставляя лишь наиболее существенные, с его точки зрения, компоненты и связи между ними, и использует достаточно малое число правдоподобных гипотез о характере взаимодействия компонентов и структуры экосистемы. Аналитические модели служат, в основном, целям выявления, математического описания, анализа и объяснения свойств или наблюдаемых феноменов, присущих максимально широкому кругу экосистем. Так, например, широко известная модель конкуренции Лотки–Вольтерра позволяет указать условия взаимного сосуществования видов в рамках различных сообществ. Имитационные модели (англ. simulation models) – один из основных классов математического моделирования. Целью построения имитаций является максимальное приближение модели к конкретному (чаще всего уникальному) экологическому объекту и достижение максимальной точности его описания. Имитационные модели претендуют на выполнение как объяснительных, так и прогнозных функций, хотя выполнение первых для больших и сложных имитаций проблематично (для удачных имитационных моделей можно говорить лишь о косвенном подтверждении непротиворечивости положенных в их основу гипотез). Имитационные модели реализуются на ЭВМ с использованием блочного принципа, позволяющего всю моделируемую систему разбить на ряд подсистем, связанных между собой незначительным числом обобщенных взаимодействий и допускающих самостоятельное моделирование с использованием своего собственного математического аппарата (в частности, для подсистем, механизм функционирования которых неизвестен, возможно построение регрессионных или самоорганизующихся моделей). Такой подход позволяет также достаточно просто конструировать, путем замены отдельных блоков, новые имитационные модели. Если имитационные модели реализуются без блочного принципа, можно говорить о квазиимитационном моделировании. Имитации, в которых все коэффициенты определены по результатам экспериментов над конкретной экосистемой, называются портретными моделями (цитата из В.В. Налимова [1971]: “поражают иной раз так называемые "портретные модели", в которых не заключено какое-либо большое содержание, а просто на языке математики записывается то, что с одинаковым успехом можно было бы выразить и на обычном языке. Ясно, что такие модели вызывают только раздражение у представителей конкретных областей знаний. Что нового, например, получила биология от того, что часть ее представлений была переформулирована в терминах теории информации?”) Методы построения имитационных моделей чаще всего основываются на классических принципах системной динамики Дж. Форрестера [1978] (см. также [Гильманов, 1978; Крапивин c соавт., 1982]). Создание имитационных моделей сопряжено с большими затратами. Так, модель ELM (злаковниковой экосистемы, используемой под пастбище) строилась 7 лет с годовым бюджетом программы в 1,5 млн. долл. около 100 научными сотрудниками из более 30 научных учреждений США, Австралии и Канады [цит. по: Розенберг., 1984]. В настоящее время можно отметить два направления развития имитационного моделирования, где предлагаются достаточно конструктивные методы компенсации априорной неопределенности, проистекающей от нестационарного и стохастического характера экологических систем. Первое направление оформилось в виде методики решения задач идентификации и верификации как последовательного процесса определения и уточнения численных значений коэффициентов модели [Георгиевский, 1982; Сердюцкая, 1984]. Второе направление связано со стратегией поиска скрытых закономерностей моделируемой системы и интеграции их в модель [Лапко с соавт., 1999]. Эмпирико-статистические модели объединяют в себе практически все биометрические методы первичной обработки экспериментальной информации. Основная цель построения этих моделей состоит в следующем: упорядочение или агрегирование информации; поиск, количественная оценка и содержательная интерпретация причинно-следственных отношений между переменными системы; оценка достоверности и продуктивности различных гипотез о взаимном влиянии наблюдаемых явлений и воздействующих факторов; идентификация параметров расчетных уравнений различного назначения. Часто эмпирико-статистические модели являются "сырьем" и обоснованием подходов к построению моделей других типов (в первую очередь, имитационных). Важным методологическим вопросом является определение характера зависимости между факторами и результативными показателями: функциональная она или стохастическая, прямая или обратная, прямолинейная или криволинейная и т.д. Здесь используются теоретикостатистические критерии, практический опыт, а также способы сравнения параллельных и динамичных рядов, аналитических группировок исходной информации, графические методы и др. Детерминированный анализ представляет собой методику исследования влияния факторов, связь которых с результативным показателем носит явно выраженный функциональный характер, т.е. когда результативный показатель представляется в виде произведения, частного или алгебраической суммы исходных факторов. Стохастический анализ представляет собой обширный класс методов, опирающихся на теоретико-вероятностные представления, теоремы, критерии и методы параметрической и непараметрической статистики. Искусственный интеллект ИИ (artificial intelligence) обычно трактуется как свойство автоматических систем брать на себя отдельные функции мыслительной способности человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий. Речь идет, в первую очередь, о системах, в основу которых положены принципы обучения, самоорганизации и эволюции при минимальном участии человека, но привлечении его в качестве учителя и партнёра, гармоничного элемента человеко-машинной системы. Этапы построения математической модели Сущность построения математической модели состоит в том, что реальная система упрощается, схематизируется и описывается с помощью того или иного математического аппарата. Можно выделить следующие основные этапы построения моделей. 1. Содержательное описание моделируемого объекта. Объекты моделирования описываются с позиций системного подхода. Исходя из цели исследования устанавливаются совокупность элементов, взаимосвязи между элементами, возможные состояния каждого элемента, существенные характеристики состояний и отношения между ними. Например, фиксируется, что если значение одного параметра возрастает, то значение другого — убывает и т.п. Вопросы, связанные с полнотой и единственностью выбора характеристик, не рассматриваются. Естественно, в таком словесном описании возможны логические противоречия, неопределенности. Это исходная естественно-научная концепция исследуемого объекта. Такое предварительное, приближенное представление системы называют концептуальной моделью. Для того чтобы содержательное описание служило хорошей основой для последующей формализации, требуется обстоятельно изучить моделируемый объект. Нередко естественное стремление ускорить разработку модели уводит исследователя от данного этапа непосредственно к решению формальных вопросов. В результате построенная без достаточного содержательного базиса модель оказывается непригодной к использованию. На этом этапе моделирования широко применяются качественные методы описания систем, знаковые и языковые модели. 2. Формализация операций. Формализация сводится в общих чертах к следующему. На основе содержательного описания определяется исходное множество характеристик системы. Для выделения существенных характеристик необходим хотя бы приближенный анализ каждой из них. При проведении анализа опираются на постановку задачи и понимание природы исследуемой системы. После исключения несущественных характеристик выделяют управляемые и неуправляемые параметры и производят символизацию. Затем определяется система ограничений на значения управляемых параметров. Если ограничения не носят принципиальный характер, то ими пренебрегают. Дальнейшие действия связаны с формированием целевой функции модели. В соответствии с известными положениями выбираются показатели исхода операции и определяется примерный вид функции полезности на исходах. Если функция полезности близка к пороговой (или монотонной), то оценка эффективности решений возможна непосредственно по показателям исхода операции. В этом случае необходимо выбрать способ свертки показателей (способ перехода от множества показателей к одному обобщенному показателю) и произвести саму свертку. По свертке показателей формируются критерий эффективности и целевая функция. Если при качественном анализе вида функции полезности окажется, что ее нельзя считать пороговой (монотонной), прямая оценка эффективности решений через показатели исхода операции неправомочна. Необходимо определять функцию полезности и уже на ее основе вести формирование критерия эффективности и целевой функции. В целом замена содержательного описания формальным — это итеративный процесс. 3. Проверка адекватности модели. Требование адекватности находится в противоречии с требованием простоты, и это нужно учитывать при проверке модели на адекватность. Исходный вариант модели предварительно проверяется по следующим основным аспектам: o Все ли существенные параметры включены в модель? o Нет ли в модели несущественных параметров? o Правильно ли отражены функциональные связи между параметрами? o Правильно ли определены ограничения на значения параметров? Для проверки рекомендуется привлекать специалистов, которые не принимали участия в разработке модели. Они могут более объективно рассмотреть модель и заметить ее слабые стороны, чем ее разработчики. Такая предварительная проверка модели позволяет выявить грубые ошибки. После этого приступают к реализации модели и проведению исследований. Полученные результаты моделирования подвергаются анализу на соответствие известным свойствам исследуемого объекта. Для установления соответствия создаваемой модели оригиналу используются следующие пути: o сравнение результатов моделирования с отдельными экспериментальными результатами, полученными при одинаковых условиях; o использование других близких моделей; сопоставление структуры и функционирования модели с прототипом. Главным путем проверки адекватности модели исследуемому объекту выступает практика. Однако она требует накопления статистики, которая далеко не всегда бывает достаточной для получения надежных данных. Для многих моделей первые два приемлемы в меньшей степени. В этом случае остается один путь: заключение о подобии модели и прототипа делать на основе сопоставления их структур и реализуемых функций. Такие заключения не носят формального характера, поскольку основываются на опыте и интуиции исследователя. По результатам проверки модели на адекватность принимается решение о возможности ее практического использования или о проведении корректировки. 4. Корректировка модели. При корректировке модели могут уточняться существенные параметры, ограничения на значения управляемых параметров, показатели исхода операции, связи показателей исхода операции с существенными параметрами, критерий эффективности. После внесения изменений в модель вновь выполняется оценка адекватности. 5. Оптимизация модели. Сущность оптимизации моделей состоит в их упрощении при заданном уровне адекватности. Основными показателями, по которым возможна оптимизация модели, выступают время и затраты средств для проведения исследований на ней. В основе оптимизации лежит возможность преобразования моделей из одной формы в другую. Преобразование может выполняться либо с использованием математических методов, либо эвристическим путем. o ЛЕКЦИЯ 4. Методы математического моделирования Математические модели в научных исследованиях Математические модели биологии, экономике, в статистической механике. . Вопросы научного поиска, связанные с возникновением нового знания, волновали ученых на протяжении всей истории развития науки. Сегодня в сферу научно-исследовательской деятельности вовлечены сотни тысяч людей во всем мире, результаты их исследований используются в развитии общества. У начинающих исследователей, приступающих к научной работе, всегда возникает ряд вопросов, связанных с методологическими проблемами осуществления научно-исследовательской деятельности. Научное исследование – это длительный и непрерывный процесс получения новых научных знаний, один из видов познавательной деятельности. Научное исследование может носить прикладной характер, направленный на достижение конкретных частных целей, а может иметь фундаментальный характер, означающий производство новых знаний независимо от перспектив его применения. Еще важнее, с точки зрения простого студента, понять, каким образом возникают такие объекты, как «дифференциал», «определенный интеграл», «дифференциальное уравнение», и многие другие. Другой важной проблемой является применение этих понятий в практической деятельности. Многие эти моменты удается объединить в одно целое с помощью понятия «математическая модель». Данное понятие включает в себя постановку задачи, алгоритм решения, а также непосредственное представление результата в различных понятных нам видах: аналитическом, табличном, графическом. Процесс решения задачи исходит из гипотезы, то есть научного предположения, истинное значение которого пока неопределенно. Далее следуют теоретический анализ гипотезы и накопление материала для проверки ее обоснованности. Этот процесс описывается формулами, и с помощью исходных данных, полученных в результате опытов, решается вполне конкретная практическая задача. При этом иногда удается понять различный смысл вложенных понятий, таких как геометрический смысл, физический смысл, биологический смысл и т. д. Конечной точкой научного исследования является получение нового научного знания, к важнейшим критериям которого можно отнести объективность, доказательность, системность, проверяемость. ЛЕКЦИЯ 5 Методы математического моделирования Математические модели в научных исследованиях Модели динамических систем. Особые точки. Бифуркации. Динамический хаос. Эргодичность и перемешивание. Понятие о самоорганизации. Диссипативные структуры. Режимы с обострением. При рассмотрении любой системы обнаруживается, что ее целостность и обособленность, отображенные в модели черного ящика, выступают как внешние свойства. Внутренность же «ящика» оказывается неоднородной, что позволяет различать составные части самой системы. При более детальном рассмотрении некоторые части системы могут быть, в свою очередь, разбиты на составные части и т.д. Те части системы, которые мы рассматриваем как неделимые, называются элементами. Части системы, состоящие более чем из одного элемента, называют подсистемами. При необходимости можно ввести обозначения или термины, указывающие на иерархию частей. В результате получается модель состава системы, описывающая из каких подсистем и элементов она состоит (см. рис.5.2). Рис.5.2.(a) — Модель состава системы Совокупность необходимых и достаточных для достижения цели отношений между элементами называется структурой системы. Когда мы рассматриваем некую совокупность объектов как систему, то из всех отношений мы выбираем важные, т.е. существенные для достижения цели. Точнее, в модель структуры (в список отношений) мы включаем только конечное число связей, которые существенны по отношению к рассматриваемой цели. Например, при расчете механизмов не учитываются силы взаимного притяжения его деталей, хотя, согласно закону всемирного тяготения, такие силы объективно существуют. Зато вес деталей учитывается обязательно. Объединяя все изложенное в предыдущих параграфах, можно сформулировать второе определение системы: система есть совокупность взаимосвязанных элементов, обособленная от среды и взаимодействующая с ней как целое. Очевидно, что представленные определения охватывают модели «черного ящика», состава и структуры. Все вместе они образуют еще одну модель, которую будем называть структурной схемой системы. В структурной схеме указываются все элементы системы, все связи между элементами внутри системы и связи определенных элементов с окружающей средой (входы и выходы системы). Рассмотрим систему «синхронизируемые часы». Считаем, что в состав такой системы входят три элемента: датчик, индикатор и эталон времени. Структура часов определяется следующими отношениями между парами элементов: Пара элементов Связь между ними Датчик и индикатор Однозначное соответствие Эталон и датчик Приблизительное соответствие Индикатор и эталон Периодическое сравнение и устранение расхождения Описанные связи указаны стрелками 1-3 между элементами на рис.5.3. Вход 4 изображает поступление энергии извне, вход 5 соответствует регулировки индикатора, вход 6 — показанию часов. Рис.5.3 — Структурная схема системы синхронизируемые часы Все структурные схемы имеют нечто общее и это побудило математиков рассматривать их как объект математических исследований. Для этого пришлось абстрагироваться от содержательной стороны структурных схем. В результате получилась схема, в которой обозначается только наличие элементов и связей между ними. Такая схема называется графом. Граф состоит из обозначений элементов произвольной природы, называемых вершинами, и обозначений связей между ними, называемых ребрами (либо дугами). На рис.5.4 изображен граф: вершины обозначены в виде кружков, ребра в виде линий. Рис.5.4 — Пример графа Если направления связей не обозначаются, то граф называется неориентированным, при наличии стрелок — ориентированным. Данная пара вершин может быть соединена любым количеством ребер; вершина может быть соединена сама с собой (тогда ребро называется петлей). Если в графе требуется отразить другие различия между элементами или связями, то либо приписывают ребрам различные веса (взвешенные графы), либо раскрашивают вершины или ребра (раскрашенные графы). Для графов построена интересная и содержательная теория, имеющая многочисленные приложения. Разнообразные задачи этой теории связаны с различными преобразованиями графов, а также с возможностью рассмотрения различных отношений на графах: весов, рангов, цветов, вероятностных характеристик (стохастические графы) и т.д. Поскольку множества вершин и ребер формально можно поменять местами, получается два разных представления системы в виде вершинного или реберного графа. Графы могут изображать любые структуры, если не накладывать ограничений на пересекаемость ребер. Некоторые типы структур имеют особенности, важные для практики, они выделены из других и получили специальные названия. Так, в организационных системах часто встречаются (см.рис.5.5) линейные, древовидные (иерархические) и матричные структуры; в технических системах чаще встречаются сетевые структуры; особое место в теории систем занимают структуры с обратными связями, которые соответствуют кольцевым путям в ориентированных графах. Структурная схема системы является наиболее подробной и полной моделью любой системы на данном этапе нашего познания. При этом всегда остается актуальным вопрос об адекватности этой модели, разрешаемый только на практике. Рис. 5.5 — Линейные, древовидные, матричные и сетевые структуры До сих пор основное внимание было уделено понятию системы, ее составу и устройству. Были рассмотрены модели, которые являются как бы «фотографиями» системы, отображают ее в некоторый момент времени. В этом смысле рассмотренные варианты моделей могут быть названы статическими моделями. Следующий шаг в исследовании систем состоит в том, чтобы понять и описать, как система «работает», что происходит с ней самой и окружающей средой в ходе реализации поставленной цели. Системы, в которых происходят какие бы то ни было изменения со временем называются динамическими, а модели, отображающие эти изменения, — динамическими моделями систем. Для разных объектов и систем разработано большое количество динамических моделей, описывающих процессы с различной степенью детализации. Однако всегда развитие моделей происходит в той же последовательности, как это было изложено выше: от «черного ящика» к «белому». Общая математическая модель динамики Уже на этапе «черного ящика» различают два типа динамики системы: функционирование и развитие. Под функционированием подразумевают процессы, которые происходят в системе, стабильно реализующей фиксированную цель. Функционируют, например, часы, городской транспорт, радиоприемник и т.д. Развитием называют то, что происходит с системой при изменении ее целей. Характерной чертой развития является тот факт, что существующая структура перестает соответствовать новой цели. Для обеспечения новой функции приходится изменять структуру, а иногда и состав системы, т.е. перестраивать всю систему. Возможны и такие системы, для функционирования которых какие-то ее подсистемы должны быть постоянно в развитии. Типы динамических моделей. При математическом моделировании некоторого процесса его конкретная реализация описывается в виде соответствия между элементами множества входов системы X «возможных значений» x и элементов упорядоченного множества T «моментов времени» t, т.е. в виде отображения: T → X: x(t) ∈ XT, t ∈ T. С помощью этих понятий строятся математические модели систем. Рассматривая выход y(t) системы как ее реакцию на входы x(t)= u(t),v(t) (управляемые u(t) и управляемые v(t)), можно представить модель «черного ящика» как совокупность двух процессов (см. рис.3.6): XT = {x(t)} и YT = {y(t)}, t ∈ T Рис.5.6 — Динамическая модель «черного ящика»: задание процесса на входах и выходах системы Если даже считать y(t) результатом некоторого преобразования Ф процесса x(t), т.е. y(t)=Ф[x(t)], то модель «черного ящика» предполагает, что это преобразование неизвестно. В том случае, когда имеем модель «белого ящика» соотношение между входом и выходом должно быть описано. Способ описания зависит от того, что нам известно и в какой форме можно использовать эти знания. На практике наблюдая входы и выходы системы можно восстановить функцию y=Ф(x). По существу это задача о переходе от модели «черного ящика» к модели «белого ящика» по наблюдениям входов и выходов при условии безинерционности системы. Класс систем, которые можно считать безинерционными, весьма узок. Необходимо строить математические модели систем, выход которых определяется не только значением входа в данный момент времени, но и теми значениями, которые были на входе в предыдущие моменты. В наиболее общей модели это достигается введением понятия состояния системы как некоторой внутренней характеристики, значение которой в настоящий момент времени определяет текущее значение выходной величины. Обозначим это состояние через z(t). Сказанное выше означает существование такого отображения η: Z × T → Y, что y(t) = η[t, z(t)] Явная зависимость от t введена для учета возможности изменения зависимости выхода от состояния с течением времени. Это отображение называется отображением выхода. Для завершения построения модели нужно описать связь между входом и состоянием, т.е. ввести параметрическое семейство отображений µα: Z × X() → Z, заданных для всех значений параметров t ∈ T, τ ∈T и τ ≤ t Это означает принятие аксиомы о том, что состояние в любой момент t однозначно определяется состоянием z и отрезком реализации входа х( ) z(t) = µα[Zτ, X()] = σ[t, τ, Zτ, X()]. Такое отображение называется переходным отображением. Итак, математическая модель системы, соответствующая уровню «белого ящика», — это задание множества входов, состояний и выходов, и связей между ними: X →σ Z →η Y Конкретизируя множества X, Z и Y и отображения можно перейти к содержательным моделям различных систем. Говорят о дискретных или непрерывных по времени системах в зависимости от того, дискретно или непрерывно множество Т. Далее, если множества X, Z и Y дискретной по времени системы имеет конечное число элементов, то такую систему называют конечным автоматом. Это довольно простой класс систем в том смысле, что для исследования конечных автоматов необходимы лишь методы логики и алгебры. В то же время это широкий и практически важный класс, так как в него входят все дискретные (цифровые) измерительные, управляющие и вычислительные устройства. Если X, Z и Y — линейные пространства, а есть- линейные операторы, то и система называется линейной. Если к линейной системе предъявить дополнительные требования, состоящие в том, чтобы пространства имели топологическую структуру, а отображения были непрерывны в этой топологии, то мы приходим к гладким системам. Не вдаваясь в математические подробности, отметим, что задание топологической структуры множества позволяет строго определить основные понятия анализа на этом множестве, например сходимость последовательностей на нем, а так же вводить метрику (меру близости между элементами пространства). ЛЕКЦИЯ 5 Компьютерные технологии Численные методы Интерполяция и аппроксимация функциональных зависимостей. Численное дифференцирование и интегрирование. Интерполяция и аппроксимация функциональных зависимостей Интерполяция, экстраполяция и аппроксимация Вычисление многих функций, особенно специальных, требует больших затрат времени. Поэтому до сих пор широко применяются таблицы таких функций. Достаточно отметить знаменитые на весь мир таблицы в книге "Справочник по специальным функциям с формулами, графиками и таблицами" под редакцией М. Абрамовица и И. Стиган. Если некоторая зависимость у(х) представлена рядом табличных отсчетов y(x), то интерполяцией принято называть вычисление значений у(х) при заданном х, расположенном в интервале между отсчетами. За пределами общего интервала определения функции [а,b], то есть при х < а и х > b, вычисление у(х) называют экстраполяцией (или иногда предсказанием значений функции). В данном случае речь идет об одномерной интерполяции, но возможны двумерная интерполяция функций двух переменных z(x, у) и даже многомерная интерполяция для функций многих переменных. Интерполяция и экстраполяция часто выполняются по некоторой скрытой, но подразумеваемой зависимости. Например, если узловые точки функции соединить отрезками прямых, то будем иметь многоинтервальную линейную интерполяцию данных. Если использовать отрезки параболы, то интерполяция будет параболической. Особое значение имеет многоинтервальная сплайн-интерполяция, области применения которой уже сейчас весьма обширны и непрерывно расширяются. Интерполяция рядом Фурье (набором синусоидальных функций) также достаточно хорошо известна; она эффективна при интерполяции периодических функций. Аппроксимацией в системах компьютерной математики обычно называют получение приближенных значений какого-либо выражения. Однако под аппроксимацией функций подразумевается получение некоторой конкретной функции, вычисленные значения которой с некоторой точностью аналогичны аппроксимируемой зависимости. Обычно предпочитают найти одну зависимость, приближающую заданный ряд узловых точек. Часто для этого используют степенные многочлены – полиномы. Здесь мы будем рассматривать такие виды аппроксимации, которые дают точные значения функции у(х) в узловых точках в пределах погрешности вычислений по умолчанию. Если аппроксимирующая зависимость выбирается из условия наименьшей среднеквадратической погрешности в узловых точках (метод наименьших квадратов), то мы имеем регрессию или приближение функций по методу наименьших квадратов. ЛЕКЦИЯ 6 Компьютерные технологии Численные методы Численные методы поиска экстремума. Вычислительные методы линейной алгебры. Численные методы решения систем дифференциальных уравнений. Однопараметрическая оптимизация (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных. 1. Метод дихотомии. Рассмотрим простейший однопараметрический метод безусловной оптимизации – метод дихотомии. Этот метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции. 2. Метод Фибоначчи. Метод "золотого сечения" Одним из методов однопараметрической оптимизации является метод Фибоначчи. Предположим, что нужно определить минимум как можно точнее, т.е. с наименьшим возможным интервалом неопределенности, но при этом можно выполнить только n вычислений функции. Как следует выбрать n точек, в которых вычисляется функция? С первого взгляда кажется ясным, что не следует искать решение для всех точек, получаемых в результате эксперимента. Напротив, надо попытаться сделать так, чтобы значения функции, полученные в предыдущих экспериментах, определяли положение последующих точек. Действительно, зная значения функции, мы тем самым имеем информацию о самой функции и положении ее минимума и используем эту информацию в дальнейшем поиске. Следующий из методов одномерной оптимизаци называется методом "золотого сечения". Не всегда можно заранее определить, сколько раз придется вычислять функцию. В методе Фибоначчи это нужно знать для определения L2, т.е. положения начальной точки. Метод "золотого сечения" почти столь же эффективен, как и метод Фибоначчи, однако при этом не требуется знать n - количество вычислений функции, определяемое вначале. 3. Метод Ньютона Следующий из рассматриваемых методов однопараметрической оптимизации является градиентным методом второго порядка. В нем при поиске экстремума целевой функции используется ее первые и вторые производные. Этот метод носит название метода Ньютона. 4. Численные методы решения систем дифференциальных уравнений. Системой дифференциальных уравнений называется система вида где x - независимый аргумент, yi - зависимая функция, , yi|x=x0 =yi0 - начальные условия. Функции yi(x), при подстановке которой система уравнений обращается в тождество, называется решением системой дифференциальных уравнений. Численные методы решения систем дифференциальных уравнений. 1. Метод Эйлера. yij+1=yij+hfi(xi,y1j y2j..ynj) j - номер шага. xj+1=xj+h 2. Модифицированный метод Эйлера. ki1=h*fi(xj,y1j..ynj) ki1=h*fi(xj+h,y1j+ki1..ynj+ki2) yij+1=yij+(ki1+ki2)/2 xj+1=xj+h 3. Метод Рунге-Кутта четвертого порядка. ki1=hfi(xj,y1j..ynj) ki2=hfi(xj+h/2,y2j+ki1/2,..,ynj+kn1/2) ki3=hfi(xj+h/2,y2j+ki2/2,..,ynj+kn2/2) ki4=hfi(xj+h,y1j+ki2,..,ynj+kn3) yij+1=yij+(ki1+2ki2+2ki3+ki4)/6 xj+1=xj+h Дифференциальным уравнением второго порядка называется уравнение вида y"=f(x,y,y'). (2) Функция y(x), при подстановке которой уравнение обращается в тождество, называется решением дифференциального уравнения. Численно ищется частное решение уравнения (2), которое удовлетворяет заданным начальным условиям, то есть решается задача Коши. Для численного решения дифференциальное уравнение второго порядка преобразуется в систему двух дифференциальных уравнений первого порядка и приводится к машинному виду (3). Для этого вводится новая неизвестная функция , слева в каждом уравнении системы оставляют только первые производные неизвестных функций, а в правых частях производных быть не должно (3) . Функция f2(x, y1, y) в систему (3) введена формально для того, чтобы методы, которые будут показаны ниже, могли быть использованы для решения произвольной системы дифференциальных уравнений первого порядка. Рассмотрим несколько численных методов решения системы (3). Расчетные зависимости для i+1 шага интегрирования имеют следующий вид. Для решения системы из n уравнений расчетные формулы приведены выше. Для решения системы из двух уравнений расчетные формулы удобно записать без двойных индексов в следующем виде: 1. Метод Эйлера. у1,i+1=у1,i+hf1(xi, y1,i, yi), уi+1=уi+hf2(xi, y1,i, yi), xi+1=xi+h. 2. Метод Рунге-Кутта четвертого порядка. у1,i+1=у1,i+(m1+2m2+2m3+m4)/6, уi+1=уi+(k1+2k2+2k3+k4)/6, m1=hf1(xi, y1,i, yi), k1=hf2(xi, y1,i, yi), m2=hf1(xi+h/2, y1,i+m1/2, yi+k1/2), k2=hf2(xi+h/2, y1,i+m1/2, yi+k1/2), m3=hf1(xi+h/2, y1,i+m2/2, yi+k2/2), k3=hf2(xi+h/2, y1,i+m2/2, yi+k2/2), m4=hf1(xi+h, y1,i+m3, yi+k3), k4=hf2(xi+h, y1,i+m3, yi+k3), xi+1=xi+h, где h - шаг интегрирования. Начальные условия при численном интегрировании учитываются на нулевом шаге: i=0, x=x0, y1=y10, y=y0. ЛЕКЦИЯ 8. Компьютерные технологии Численные методы Сплайн-аппроксимация, интерполяция, метод конечных элементов. Преобразования Фурье, Лапласа, Хаара и др. Численные методы Сплайн - кусочный многочлен степени K с непрерывной производной степени K - 1 в точках соединения сегментов. При сплайновой интерполяции обычно используются локальные полиномы не выше третьей степени. Так, например, кубические сплайны проходят через три смежные узловые точки (текущие опорные точки вычислений), при этом в граничных точках совпадают как значения полинома и функции, так и значения их первых и вторых производных. Коэффициенты полиномов, проходящих через три узловые точки, рассчитываются так, чтобы непрерывными были их первая и вторая производные. Линия, которую описывает сплайн-функция, напоминает по форме гибкую линейку, закреплённую в узловых точках. Это создает высокую плавность сплайнового полинома по сравнению с другими методами аппроксимации и наглядно видно на рис. 8.1. Полиномы более высоких порядков чрезмерно громоздки для практики. Рис. 8.1. Сплайновая интерполяция и интерполяция по Лагранжу. Сплайновая аппроксимация может применяться для достаточно быстро изменяющихся функций, не имеющих разрывов функции и ее производных. Основной недостаток сплайнов – отсутствие единого аналитического выражения для описания функции. Заметим также, что результаты экстраполяции функций существенно зависят от метода аппроксимации, и, соответственно, к их достоверности нужно подходить достаточно осторожно. Сплайновая интерполяция обычно применяется в составе математических пакетов по определенной технологии. Так, в системе Mathcad при выполнении сплайновой интерполяции по узловым точкам функции (векторам X и Y) сначала вычисляется вектор (обозначим его индексом S) вторых производных входной функции y(x) по одной из программ: S:= cspline(X,Y) – возвращает вектор S вторых производных при приближении в опорных точках к кубическому полиному; S:= pspline(X,Y) – возвращает вектор S при приближении в опорных точках к параболической кривой; S:= lspline(X,Y) – возвращает вектор S при приближении в опорных точках к прямой. По значениям вектора S функцией interp(S,X,Y,x) вычисляются значения аппроксимирующей функции по аргументам х. На рис. 8.2 приведен пример кубической сплайновой интерполяции двумерных цифровых данных с одновременным повышением узловой сетки цифровых данных в 4 раза. Рис. 8.2. Сплайн - интерполяция двумерных данных. Интерполя́ция, интерполи́рование — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. В функциональном анализе интерполяция линейных операторов представляет собой раздел, рассматривающий банаховы пространства как элементы некоторой категории. Многим из тех, кто сталкивается с научными и инженерными расчётами, часто приходится оперировать наборами значений, полученных опытным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных. Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах. Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ. — операция, сопоставляющая Преобразование Фурье (ℱ) одной функции вещественной переменной другую функцию, также вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Преобразование Фурье функции вещественной переменной является интегральным и задаётся следующей формулой: Разные источники могут давать определения, отличающиеся от приведённого выше выбором коэффициента перед интегралом, а также знака «−» в показателе экспоненты. Но все свойства будут те же, хотя вид некоторых формул может измениться. Преобразование Лапласа - интегральное преобразование, связывающее функцию F(p) комплексного переменного (изображение) с функцией f(x) действительного переменного (оригинал). Преобразованием Лапласа от функции f(x) (оргигинала) называется функция: f(x) называют оригиналом преобразования Лапласа, а F(p) - изображением преобразования Лапласа. f(x) и F(p)однозначно определяются друг относительно друга, тоесть если Вы знаете f(x), то всегда можете узнать F(p), и наоборот, если знаете F(p), то всегда можете получить f(x). Преобразование Лапласа является одним из самых мощных инструментов для решения очень многих задач в области математики, экономики, радиотехники, геометрии, теории управления, микропроцессоров, теории вероятности, теории массового обслуживания и много другого. Часто для решения задачи достаточно получить преобразование Лапласа от искомой функции (именно здесь и пригодится таблица преобразований Лапласа). Также преобразование Лапласа используют при решении задачи Коши для линейного дифференциального уравнения с постоянными коэффициентами, для решения интегральных уравнений, вычисления несобственных интегралов, для представления сигнала в спектральной области и многого другого! Преобразование Хаара на практике используется для отображения поддиапазона частот. Вейвлет-преобразование (англ. Wavelet transform) — интегральное преобразование, которое представляет собой свертку вейвлет-функции с сигналом. Способ преобразования функции (или сигнала) в форму, которая или делает некоторые величины исходного сигнала более поддающимися изучению, или позволяет сжать исходный набор данных. Вейвлетное преобразование сигналов является обобщением спектрального анализа. Термин (англ. wavelet) в переводе с английского означает «маленькая волна». Вейвлеты — это обобщённое название математических функций определенной формы, которые локальны во времени и по частоте и в которых все функции получаются из одной базовой, изменяя её (сдвигая, растягивая). Вейвлет Хаа́ра — один из первых и наиболее простых вейвлетов. Он был предложен венгерским математиком Альфредом Хааром в 1909 году. Вейвлеты Хаара ортогональны, обладают компактным носителем, хорошо локализованы в пространстве, но не являются гладкими. Впоследствии Ингрид Добеши стала развивать теорию ортогональных вейвлетов и предложила использовать функции, вычисляемые итерационным путем, названные вейвлетами Добеши. ЛЕКЦИЯ 9 Компьютерные технологии Вычислительный эксперимент Принципы проведения вычислительного алгоритм, программа. эксперимента. Модель, В настоящее время основным способом исследования ММ и проверки ее качественных показателей служит вычислительный эксперимент. Вычислительным экспериментом называется методология и технология исследований, основанные на применении прикладной математики и ЭВМ как технической базы при использовании ММ. Вычислительный эксперимент основывается на создании ММ изучаемых объектов, которые формируются с помощью некоторой особой математической структуры, способной отражать свойства объекта, проявляемые им в различных экспериментальных условиях, и включает в себя следующие этапы. 1. Для исследуемого объекта строится модель, обычно сначала физическая, фиксирующая разделение всех действующих в рассматриваемом явлении факторов на главные и второстепенные, которые на данном этапе исследования отбрасываются; одновременно формулируются допущения и условия применимости модели, границы, в которых будут справедливы полученные результаты; модель записывается в математических, терминах, как правило, в виде дифференциальных или интегро-дифференциальных уравнений; создание ММ проводится специалистами, хорошо знающими данную область естествознания или техники, а также математиками, представляющими себе возможности решения математической задачи . 2. Разрабатывается метод решения сформулированной математической задачи. Эта задача представляется в виде совокупности алгебраических формул, по которым должны вестись вычисления и условия, показывающие последовательность применения этих формул; набор этих формул и условий носит название вычислительного алгоритма. Вычислительный эксперимент имеет многовариантный характер, так как решения поставленных задач часто зависят от многочисленных входных параметров. Тем не менее, каждый конкретный расчет в вычислительном эксперименте проводится при фиксированных значениях всех параметров. Между тем в результате такого эксперимента часто ставится задача определения оптимального набора параметров. Поэтому при создании оптимальной установки приходится проводить большое число расчетов однотипных вариантов задачи, отличающихся значением некоторых параметров. В связи с этим при организации вычислительного эксперимента можно использовать эффективные численные методы. 3. Разрабатываются алгоритм и программа решения задачи на ЭВМ. Программирование решений определяется теперь не только искусством и опытом исполнителя, а перерастает в самостоятельную науку со своими принципиальными подходами. 4. Проведение расчетов на ЭВМ. Результат получается в виде некоторой цифровой информации, которую далее необходимо будет расшифровать. Точность информации определяется при вычислительном эксперименте достоверностью модели, положенной в основу эксперимента, правильностью алгоритмов и программ (проводятся предварительные «тестовые» испытания). 5. Обработка результатов расчетов, их анализ и выводы. На этом этапе могут возникнуть необходимость уточнения ММ (усложнения или, наоборот, упрощения), предложения по созданию упрощенных инженерных способов решения и формул, дающих возможности получить необходимую информацию более простым способом. Вычислительный эксперимент приобретает исключительное значение в тех случаях, когда натурные эксперименты и построение физической модели оказываются невозможными. Особенно ярко можно проиллюстрировать значение вычислительного эксперимента при исследовании влияния городской застройки на параметры распространения радиосигнала. В связи с интенсивным развитием систем мобильной связи данная задача в настоящее время является особенно актуальной. С целью снижения затрат при частотно-территориальном планировании производится оптимизация частотно-территориального плана с учетом таких факторов как рельеф местности, конфигурация городской застройки, атмосферные воздействия. Кроме этого, с учетом динамичности развития города необходимо постоянное уточнение соответствующих моделей. То, что принято называть уровнем сигнала (средняя напряженность электромагнитного поля) представляет собой результат сложного взаимодействия физических процессов, протекающих при распространении сигнала: прохождение сигнала сквозь здания и сооружения; воздействие на сигнал помех искусственного и естественного происхождения; атмосферная рефракция сигнала; отражения сигнала от зданий и от земной поверхности; потери энергии сигнала в осадках и др. В данном случае окружающую среду можно исследовать, строя соответствующую ММ, которая должна позволять предсказывать уровень сигнала при заданной конфигурации застройки, рельефе местности, погодных условиях и т. п. Масштабы среды распространения сигнала настолько грандиозны, что эксперимент даже в одном каком-то регионе требует существенных затрат. Таким образом, глобальный эксперимент по исследованию распространения сигнала возможен, но не натурный, а вычислительный, проводящий исследования не реальной системы (окружающей среды), а ее ММ. В науке и технике известно немало областей, в которых вычислительный эксперимент оказывается единственно возможным при исследовании сложных систем. Пригодность ММ для решения задач исследования характеризуется тем, в какой степени она обладает так называемыми целевыми свойствами, основными из которых являются адекватность, устойчивость и чувствительность, которые можно отнести к принципам При проведении вычислительного эксперимента каждый этап вносит свои ограничения. Как всегда, математическая формулировка представляет собой лишь приближённое описание физического явления. Поэтому учёныйвычислитель должен знать, какие упрощающие предположения сделаны, чтобы определить те случаи, когда справедливы эти уравнения, а следовательно, и его вычислительная модель. Более строгие ограничения возникают на этапе перехода к дискретной алгебраической аппроксимации, на котором непрерывные дифференциальные или интегральные уравнения математической модели заменяются алгебраическими аппроксимациями для того, чтобы сделать возможным численное решение на компьютере. На этом этапе возникают вопросы о влиянии конечного временного шага, дискретных пространственных сеток и, в случае моделей частиц, конечного числа частиц. Метод дискретизации зависит от каждой конкретной задачи. Он должен учитывать все основные особенности точного решения математической модели, при минимальных вычислительных затратах. В результате дискретизации возникают алгебраические системы уравнений (линейные или нелинейные), вид которых зависит от способа дискретизации. Хотя объём информации, который можно обработать с помощью компьютеров, велик, он тем не менее ограничен. Поэтому этот фактор должен всегда учитываться при построении вычислительных моделей. В настоящее время существует множество надёжных численных алгоритмов для решения систем уравнений. Во многих случаях можно воспользоваться библиотеками стандартных программ. Необходимо только 28 выбрать соответствующую процедуру с учётом свойств и структуры решаемой системы. После того, как все вопросы, связанные с построением алгоритма решены, можно строить “прибор” – программу моделирования. При этом необходимо уделить достаточно внимания созданию правильно функционирующей программы. Качественно разработанная программа должна быть удобочитаемой, несложной в использовании и легко модифицируемой. Она должна иметь модульную структуру и встроенную диагностику и должна собираться только из проверенных программных компонентов. Полная программа должна быть испытана на известных задачах как для проверки алгоритма и кода, так и для определения параметров дискретизации, которые обеспечивают компромисс между качеством численного решения и вычислительными затратами. Только когда испытания и “калибровка” завершены, “установку” можно считать готовой для проведения вычислительных экспериментов. ЛЕКЦИЯ 10 Компьютерные технологии Алгоритмические языки Представление о языках программирования высокого уровня. Пакеты прикладных программ Языки программирования - это формальные языки специально созданные для общения человека с компьютером. Каждый язык программирования, равно как и «естественный» язык (русский, английский и т.д.), имеет алфавит, словарный запас, свои грамматику и синтаксис, а также семантику. Алфавит - фиксированный для данного языка набор основных символов, допускаемых для составления текста программы на этом языке. Синтаксис - система правил, определяющих допустимые конструкции языка программирования из букв алфавита. Семантика - система правил однозначного толкования отдельных языковых конструкций, позволяющих воспроизвести процесс обработки данных. При описании языка и его применении используют понятия языка. Понятие подразумевает некоторую синтаксическую конструкцию и определяемые ею свойства программных объектов или процесса обработки данных. Взаимодействие синтаксических и семантических правил определяют те или иные понятия языка, например, операторы, идентификаторы, переменные, функции и процедуры, модули и т.д. В отличие от естественных языков правила грамматики и семантики для языков программирования, как и для всех формальных языков, должны быть явно, однозначно и четко сформулированы. Языки программирования, имитирующие естественные языки, обладающие укрупненными командами, ориентированными на решение прикладных содержательных задач, называют языками «высокого уровня». В настоящее время насчитывается несколько сотен таких языков, а если считать и их диалекты, то это число возрастет до нескольких тысяч. Языки программирования высокого уровня существенно отличаются от машинноориентированных (низкого уровня) языков. Во-первых, машинная программа в конечном счете записывается с помощью лишь двух символов 0 и 1. Вовторых, каждая ЭВМ имеет ограниченный набор машинных операций, ориентированных на структуру процессора. Как правило, этот набор состоит из сравнительно небольшого числа простейших операций, типа: переслать число в ячейку; считать число из ячейки; увеличить содержимое ячейки на +1 и т.п. Команда на машинном языке содержит очень ограниченный объем информации, поэтому она обычно определяет простейший обмен содержимого ячеек памяти, элементарные арифметические и логические операции. Команда содержит код и адреса ячеек, с содержимым которой выполняется закодированное действие. Языки программирования высокого уровня имеют следующие достоинства: • алфавит языка значительно шире машинного, что делает его гораздо более выразительным и существенно повышает наглядность и понятность текста; • набор операций, допустимых для использования, не зависит от набора машинных операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса; • конструкции команд (операторов) отражают содержательные виды обработки данных и задаются в удобном для человека виде; • используется аппарат переменных и действия с ними; • поддерживается широкий набор типов данных. Таким образом, языки программирования высокого уровня являются машинно-независимыми и требуют использования соответствующих программ-переводчиков (трансляторов) для представления программы на языке машины, на которой она будет исполняться Пакеты прикладных программ (ППП) — это комплекс взаимосвязанных прикладных программ и средств системного обеспечения (программных и языковых), предназначенных для автоматизации решения определенного класса задач. В зависимости от характера решаемых задач различают следующие разновидности ППП: пакеты для решения типовых инженерных, планово-экономических, общенаучных задач - MathCAD; пакеты системных программ – Norton Utilities; пакеты для обеспечения систем автоматизированного проектирования и систем автоматизации научных исследований – AutoCAD, Oracle CASE Designer/2000, Rational Rose от Rational Software Corporation; пакеты педагогических программных средств и другие. Оформление прикладной системы в виде ППП, а не в виде монолитной программы, обусловлено следующими причинами: − различные информационные потребности пользователей и необходимость гибкой настройки под конкретные задачи предметной области; − необходимость экономии и оптимального (рационального) использования ресурсов дискового пространства; − последовательный характер задач и возможность их декомпозиции. С развитием средств ВТ и расширением возможностей компьютеров по хранению и обработке информации, степень влияния этих причин, а также подходы к интеграции программных продуктов, изменяются. Так, например, использование ОС Windiows 95/NT зачастую позволяет отказаться от разработки интегрированной оболочки для ППП и использовать средства самой ОС для интегрирования прикладных программ в единую систему. Монолитные программы за счет использования механизмов DLL, plug-in-ов приобретают возможности по гибкому изменению состава модулей и конфигурированию, характерные ранее для ППП. Каждый ППП обладает обычно рядом возможностей по методам обработки данных и формам их представления, полноте диагностики, что дает возможность пользователю выбрать подходящий для конкретных условий вариант. Чтобы пользователь мог применить ППП для решения конкретной задачи, пакет должен обладать средствами настройки (иногда путём введения некоторых дополнений). Часто пакеты прикладных программ располагают базами данных для хранения данных и передачи их прикладным программам. ППП обеспечивают значительное снижение требований к уровню профессиональной подготовки пользователей в области программирования, вплоть до возможности эксплуатации пакета без программиста. В значительной степени это достигается за счет применения в рамках каждого ППП унифицированного интерфейса, который обеспечивает общий для всех входящих в пакет программ метод взаимодействия пользователя с программой, что предусматривает: - единообразное использование экрана при выводе текстовой и графической информации; - единообразное использование управляющих клавиш клавиатуры - единую кодировку символьной информации и порядок подстановок специальных кодовых таблиц; - единый способ оформления и выдачи подсказок; - единый способ вывода и использования управляющих меню; - стандартный способ оформления схем диалога. Часто ППП имеют оболочку, которая объединяет входящие в его состав программы в единое целое и обеспечивает унифицированное средство доступа к ним, и называются интегрированными пакетами. Интегрированные пакеты, как правило, содержат некоторое ядро, обеспечивающее возможность тесного взаимодействия между составляющими, когда результаты работы одних программ используются как исходные данные других для формирования окончательного результата (как правило, документа сложной структуры). Например, интегрированный пакет для написания книг, содержащих иллюстрации, должен содержать: − текстовый редактор; − орфографический корректор (программу обнаружения орфографических ошибок); − программу слияния текстов; − программу формирования оглавлений и составления указателей; − автоматический поиск и замену слов и фраз; − средства телекоммуникации; − электронную таблицу; − систему управления базами данных; − модули графического оформления; − графический редактор; − возможность печати сотнями разных шрифтов и т.д. Результаты, полученные отдельными подпрограммами, могут быть объединены в окончательный документ, содержащий табличный, графический и текстовый материал. Наиболее развитые из ИП офисного назначения включают в себя текстовый редактор, органайзер, электронную таблицу, СУБД, средства поддержки электронной почты, программу создания презентационной графики. Наиболее известные офисные интегрированные пакеты: Microsoft Office – более подробно рассмотрим позднее. Microsoft Works — это очень простой и удобный пакет, объединяющий в себе текстовый редактор, электронные таблицы и базы данных, а также телекоммуникационные средства для соединения с другими компьютерами по телефонным линиям. Пакет ориентирован на людей, не имеющих времени осваивать сложные продукты, на начинающих пользователей, а также на домашних пользователей. Интегрированные пакеты для разработки программного обеспечения (например, IDE Broland Delphi или Microsoft Visual Studio) включают в свой состав текстовый редактор, компилятор, отладчик, программу для построения и отладки запросов к базам данных, средства управления проектами и многое другое. Пакеты программ для автоматизации проектирования информационных систем (систем баз данных) Oracle CASE Designer/2000, Rational Rose и другие включают программы для анализа, проектирования и генерации программных модулей и объектов хранения данных, а именно: − программы моделирования бизнес-процессов, − программы построения ERD-диаграмм, − программы построения диаграмм иерархии функций, − программы трансформации моделей, − программы генерации объектов баз данных (таблиц, индексов, ключей, ограничений), − средства генерации программного кода, − средства реинжиниринга бизнес-процессов и информационных систем, − средства администрирования - управления проектами, пользователями, объектами. ЛЕКЦИЯ 11 Информационные технологии Принятие решений Общая проблема решения. Функция потерь. Байесовский минимаксный подходы. Метод последовательного принятия решения. и 1. Этапы процесса принятия решений 1) Предварительный анализ проблемы. 1. Главные цели 2. Элементы и структуры системы, уровни рассмотрения 3. Подсистемы, используемые ими ресурсы и критерии качества функционирования систем. 4. Основные противоречия, узкие места и ограничения 2) Постановка задачи 1. Формулирование задачи 2. Определение типа 3. Определение множества вариантов и основных критериев для выбора 4. Выбор метода решения задач 3) Получение исходных данных. Устанавливаются способы измерения альтернатив и комплексной оценки. При этом возможно 3 способа проведения комплексной характеристики: 1. Статистическая оценка 2. Метод математического (или имитационного) моделирования 3. Метод экспертной оценки 4) Решение задачи принятия решений с привлечением необходимых методических (?) методов, вычислительной техники, экспертов и ЛПР. Обработка исходных данных и решения может проводиться с одной стороны итеративно, а с другой – с привлечением нескольких методов. 5) Анализ и интерпретация полученных результатов Статические ЗПР Динамические Статические ЗПР не требуют многократного решения через короткий промежуток, а динамические ЗПР требуют частого регулярного решения. 2. Классификация задач принятия решений Любая ЗПР представляется в виде: , где T – постановка задачи, A – множество допустимых альтернатив, K – множество критериев выбора (способов оценки эффективности вариантов решения), X – множество методов измерения отношения между вариантами F – отображение множества допустимых вариантов на множество критериальных оценок, G – система предпочтений экспертов, D – решающее правило, отражающее эту систему предпочтения. Каждый из элементов этого набора может служить классификационным признаком. Традиционно рассматривается следующая классификация: 1) По виду отображения F F: A * K Может иметь детерминированный, вероятностный и неопределенный вид. В связи с этим выделяются следующие задачи: - в условиях определенности (если имеется достаточное и достоверное количество информации, пример – задачи оптимизации) - в условиях риска. Возникает, когда возможные исходы можно описать с помощью некоторого вероятностного распределения. Такое описание может быт получено либо статистическими, либо экспертными методами. - в условиях неопределенности. Все остальные задачи. Информация о задаче неполная, неточная. Форм. методы либо отсутствуют, либо слишком сложны. 2) По мощности множества К. Задачи могут быть однокритериальные и многокритериальные. 3) По типу системы предпочтения экспертов (G) - системы предпочтения одного ЛПР (задачи индивидуального принятия решений) - коллективная ЗПР - 3. Основные принципы принятия решений. К настоящему времени сложилось несколько общих принципов, которые позволяют обоснованно и ясно формулировать критерии отбора альтернатив, а также сузить множество поиска. 1) Принцип Парето (принцип единогласия). Оптимальным по Парето решением является такое решение X, что для решения Z, если кто-либо (хотя бы один участник коллектива) считает, что Z лучше X, то обязательно найдется кто-то другой, считающий, что X лучше Z. Принцип Парето означает, что поиск решения надо вести до тех пор, пока все единогласно не скажут, что X – оптимально. Для любого другого решения Z будет хотя бы один голос против. 2) Принцип равновесия Нэша. Определение принципа: существует ситуация, при которой принятие решения индивидуально отдельным ЛПР неэффективно для любого участника коллектива или сложившейся ситуации. 3) Принцип гарантированного результата (принцип минимакса). Принцип, используемый участниками, которые не хотят рисковать, а желают получить гарантированный результат. Т.е. при любом ходе, при любом варианте надо получить гарантированный результат независимо от действий другого игрока. Оптимальное решение(ния): e* =maxi minj eij Сначала для гарантии соглашаемся с наименьшим результатом, но затем от части компенсируем это, выбирая решение, для которого гарантированный результат максимален. 4) Принцип Байеса предполагает, что игроку известно распределение вероятностей появления реакций системы. Знание распределения должно приводить к более объективному критерию выбора для данных условий. Наиболее объективной оценкой значения выигрыша для каждого варианта действий будет мат. ожидание. Применив это действие ко всем строкам, получим набор значений мат ожиданий, выбираем наибольшее из них: е = maxi ∑j eijqj . 5) Принцип ограниченной рациональности. Опр. Существуют пределы способности человека описывать и правильно передавать информацию о сложных ситуациях, осмысливать эту информацию, одновременно продумывать несколько вариантов поведения и выбирать из каких-то разумных соображений только один. Следствием данного принципа является то, что на практике ЛПР склонен находить и использовать не оптимальное решение, а временно удовлетворительные, т.к. не в состоянии оптимизировать их. Реализация этого принципа привела к тому, что появились такие системы, как системы поддержки решений. При этом они реализованы как в виде специального коллектива, так и в автоматизированной среде (программа на ЭВМ). В соответствии с этим принципом основным видом решения является компромисс. Функция потерь (этот термин был впервые использован в работе Wald, 1939) - это функция, которая минимизируется в процессе подгонке модели. Она представляет выбранную меру несогласия наблюдаемых данных и данных, "предсказываемых" подогнанной функцией. Например, в большинстве традиционных методов построения общих линейных моделей, функция потерь (часто называемая наименьшими квадратами) вычисляется как сумма квадратов отклонений от подогнанной линии или плоскости. Одним из свойств (которое обычно рассматривается как недостаток) этой распространенной функции потерь является высокая чувствительность к наличию выбросов. Распространенной альтернативой минимизации функции потерь наименьших квадратов (см. выше) является максимизация функции правдоподобия или логарифма функции правдоподобия (или минимизация функции правдоподобия со знаком минус; термин максимум правдоподобия был впервые использован в работе Fisher, 1922a). Эти функции обычно используются для подгонки нелинейных моделей. В общих словах функция правдоподобия определяется как: L=F(Y,Модель)=ni=1 { p[yi , Параметры модели(xi)]} Таким образом, можем вычислить вероятность (обозначенную как L, от слова likelihood - правдоподобие) появления конкретных значений зависимой переменной в выборке при заданной регрессионной модели. Байесовский подход к вероятности В основе вышеописанного объективного (частотного) подхода лежит предположение о наличии объективной неопределенности, присущей изучаемым явлениям. В альтернативном байесовском подходе неопределенность трактуется субъективно — как мера нашего незнания. В рамках байесовского подхода под вероятностью понимается степень уверенности в истинности суждения — субъективная вероятность. Идея байесовского подхода заключается в переходе от априорных знаний к апостерирорным с учетом наблюдаемых явлений. Суть байесовского подхода следует из описанной выше формулы Байеса. Пусть имеются полный набор гипотез , причем из априорных соображений оценены вероятности справедливости этих гипотез (степень уверенности в них). Полнота набора означает, что хотя бы одна из этих гипотез верна и сумма априорных вероятностей равна 1. Также для изучаемого события из априорных соображений известны вероятности — вероятности наступления события , при условии справедливости гипотезы . Тогда с помощью формулы Байеса можно определить апостериорные вероятности — то есть степень уверенности в справедливости гипотезы после того, как событие произошло. Собственно, процедуру можно повторить принимая новые вероятности за априорные и снова делая испытание, тем самым итеративно уточняя апостериорные вероятности гипотез. В частности в отличие от базового подхода к оценке распределений случайных величин, где предполагается, что на основе наблюдений оцениваются значения неизвестных параметров распределений, в байесовском подходе предполагается что параметры — тоже случайные величины (с точки зрения нашего незнания их значений). В качестве гипотез выступают те или иные возможные значения параметров и предполагаются данными некоторые априорные плотности неизвестных параметров . В качестве оценки неизвестных параметров выступает апостериорное распределение. Пусть в результате наблюдений получены некоторые значения изучаемой случайной величины. Тогда для значений данной выборки предполагая известным правдоподобие — вероятность (плотность) получения данной выборки при данных значениях параметров , по формуле Байеса (в данном случае непрерывный аналог этой формулы, где вместо вероятностей участвуют плотности, а суммирование заменено интегрированием) получим апостериорную вероятность (плотность) параметров при данной выборке. Статистический последовательный анализ — раздел математической статистики, изучающий статистические методы, основанные на последовательной выборке, формируемой в ходе статистического эксперимента. Наблюдения производятся по одному (или, более общим образом, группами) и анализируются в ходе самого эксперимента с тем, чтобы на каждом этапе решить, требуются ли ещё наблюдения (решение о продолжении эксперимента) или наблюдений уже достаточно (решение об остановке эксперимента). Когда эксперимент остановлен, заключительное статистическое решение принимается на основе всех наблюденных в эксперименте данных. Таким образом, объём последовательной выборки (общее число наблюдений, используемое для принятия статистического решения) является случайной величиной, вследствие чего, помимо обычных характеристик качества статистического вывода (вероятностей ошибки в проверке гипотез, среднеквадратической ошибки в точечном оценивании и т. п.) последовательная статистическая процедура имеет ещё одну характеристику: средний объём выборки. Поскольку (традиционные) статистические процедуры, основанные на простой случайной выборке фиксированного объёма, являются частным случаем последовательных процедур, последовательные методы предоставляют большую гибкость в проведении статистического эксперимента, и потому во многих случаях более эффективны, чем традиционные статистические процедуры, с точки зрения среднего объёма наблюдений. Широко известным примером эффективного последовательного метода является последовательный критерий отношения вероятностей (критерий Вальда) в проверке гипотез. Лекция 12 Информационные технологии Исследование операций и задачи искусственного интеллекта Искусственный интеллект. Распознавание образов. Исследование операций — применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция — всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели. Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) — всякий определённый набор зависящих от человека параметров. Оптимальное — решение, которое по тем или другим признакам предпочтительнее других. Цель исследования операций — предварительное количественное обоснование оптимальных решений с опорой на показатель эффективности. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения — параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные («дисциплинирующие») условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формируетмножество возможных решений.[1] Искусственный интеллект (artificial intelligence) – ИИ (AI) обычно толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий. Деятельность мозга, направленную на решение интеллектуальных задач, будем называть мышлением, или интеллектуальной деятельностью. Интеллект и мышление органически связаны с решением таких задач, как доказательство теорем, логический анализ, распознавание ситуаций, планирование поведения, игры и управление в условиях неопределенности. Характерными чертами интеллекта, проявляющимися в процессе решения задач, являются способность к обучению, обобщению, накоплению опыта (знаний и навыков) и адаптации к изменяющимся условиям в процессе решения задач. Благодаря этим качествам интеллекта мозг может решать разнообразные задачи, а также легко перестраиваться с решения одной задачи на другую. Таким образом, мозг, наделенный интеллектом, является универсальным средством решения широкого круга задач (в том числе неформализованных) для которых нет стандартных, заранее известных методов решения. Представляется совершенно естественным исключить из класса интеллектуальных такие задачи, для которых существуют стандартные методы решения. Примерами таких задач могут служить чисто вычислительные задачи: решение системы линейных алгебраических уравнений, численное интегрирование дифференциальных уравнений и т.д. Для решения подобного рода задач имеются стандартные алгоритмы, представляющие собой определенную последовательность элементарных операций, которая может быть легко реализована в виде программы для компьютера. В противоположность этому для широкого класса интеллектуальных задач, таких, как распознавание образов, игра в шахматы, доказательство теорем и т.п., напротив, это формальное разбиение процесса поиска решения на отдельные элементарные шаги часто оказывается весьма затруднительным, даже если само их решение несложно. Методы искусственного интеллекта Можно выделить две научные школы с разными подходами к проблеме ИИ: конвенционный ИИ и вычислительный ИИ. В конвенционном ИИ главным образом используются методы машинного самообучения, основанные на формализме и статистическом анализе. Вычислительный ИИ подразумевает итеративную разработку и обучение. Обучение основано на эмпирических данных и ассоциируется с не-символьным ИИ и нечеткими системами. Методы конвенционного ИИ реализуются в следующих подходах и системах: • Экспертные системы: программы, которые, действуя по определенным правилам, обрабатывают большое количество информации, и в результате выдают заключение или рекомендацию на ее основе. • Рассуждение по аналогии (Case-based reasoning). • Байесовские сети доверия: вероятностные модели, представляющие собой систему из множества переменных и их вероятностных зависимостей. • Поведенческий подход: модульный метод построения систем ИИ, при котором система разбивается на несколько сравнительно автономных программ поведения, которые запускаются в зависимости от изменений внешней среды Основные методы вычислительного ИИ: • Нейронные сети: коннекционистские модели нервной системы, демонстрирующие, в частности, высокие способности к распознаванию образов. • Нечеткие системы: методики для рассуждения в условиях неопределенности. • Эволюционные вычисления: модели, использующие понятие естественного отбора, обеспечивающего отсеивание наименее оптимальных согласно заданному критерию решений. В этой группе методов выделяют генетические алгоритмы и т.н. муравьиный алгоритм. Разберем подробней перечисленные методы. Экспертные системы Экспертная система (ЭС) – компьютерная программа, способная заменить специалиста-эксперта в решении проблемной ситуации. ЭС начали разрабатываться исследователями ИИ в 1970-х годах, а в 1980-х получили коммерческое подкрепление. Главным элементом экспертной системы является база знаний (БЗ), состоящая из правил анализа информации от пользователя по конкретной проблеме. Решатель, называемый также блоком логического вывода, представляет собой программу, моделирующую ход рассуждений эксперта на основании знаний, содержащихся в БЗ. Подсистема объяснений – программа, позволяющая пользователю получать ответы на вопросы: «Как была получена та или иная рекомендация?» и «Почему система приняла то или иное решение?» Ответ на вопрос «как» – это трассировка всего процесса получения решения с указанием использованных фрагментов БЗ, т.е. всех шагов цепи умозаключений. Ответ на вопрос «почему» – ссылка на умозаключение, непосредственно предшествовавшее полученному решению, т.е. отход на один шаг назад. ЭС создается при помощи инженеров по знаниям (аналитиков), которые разрабатывают ядро ЭС и, зная организацию базы знаний, заполняют ее при помощи эксперта по специальности. Байесовские сети доверия Байесовская сеть – это вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Например, байесовская сеть может быть использована для вычисления вероятности того, чем болен пациент по наличию или отсутствию ряда симптомов, основываясь на данных о зависимости между симптомами и болезнями. Существуют эффективные методы, которые используются для вычислений и обучения байесовских сетей. Байесовские сети используются для моделирования в биоинформатике (генетические сети, структура белков), медицине, классификации документов, обработке изображений, обработке данных и системах принятия решений. Нейронные сети Нейронная сеть (НС) – это распределенный параллельный процессор, состоящий из элементарных единиц обработки информации, накапливающих экспериментальные знания и предоставляющих их для последующей обработки. Она представляет собой действующую модель нервной системы и сходна с мозгом с двух точек зрения: Знания поступают в нейронную сеть из окружающей среды и используются в процессе обучения. Для накопления знаний применяются связи между нейронами, называемые синаптическими весами. • Нелинейность. Это качество нейронной сети особенно важно в том случае, если сам физический механизм, отвечающий за формирование входного сигнала, сам является нелинейным (например, человеческая речь). • Адаптивность. Нейронные сети обладают способностью адаптировать свои синаптические веса к изменениям окружающей среды. Для работы в нестационарной среде могут быть созданы нейронные сети, изменяющие синаптические веса в реальном времени. • Контекстная информация. Знания представляются в самой структуре нейронной сети. Каждый нейрон сети потенциально может быть подвержен влиянию всех остальных ее нейронов. • Отказоустойчивость. Аппаратно реализованные нейронные сети потенциально отказоустойчивы. Это значит, что при неблагоприятных условиях их производительность падает незначительно. Например, если поврежден какой-то нейрон или его связи, извлечение запомненной информации затрудняется. Однако, принимая в расчет распределенный характер хранения информации в нейронной сети, можно утверждать, что только серьезные повреждения структуры нейронной сети существенно повлияют на ее работоспособность. Представим некоторые проблемы, решаемые применением нейронных сетей: • Классификация образов. Задача состоит в указании принадлежности входного образа, представленного набором признаков, одному или нескольким предварительно определенным классам. К известным приложениям относятся распознавание букв, распознавание речи, классификация сигнала электрокардиограммы и т.п. • Кластеризация/категоризация. Кластеризация основана на подобии образов: НС размещает близкие образы в один кластер. Известны случаи применения кластеризации для извлечения знаний, сжатия данных и исследования свойств данных. • Аппроксимация функций. Задача аппроксимации состоит в нахождении оценки некоторой искаженной шумом функции, генерирующей обучающую выборку. • Предсказание/прогноз. Задача прогнозирования состоит в предсказании некоторого значения для заданного момента времени на основании ряда значений, соответствующим другим моментам времени. • Оптимизация. Задачей оптимизации является нахождение решения, которое удовлетворяет системе ограничений и максимизирует или минимизирует целевую функцию. • Ассоциативная память. Данная сфера применения НС состоит в организации памяти, адресуемой по содержанию, позволяющей извлекать содержимое по частичному или искаженному образцу. Дальнейшее повышение производительности компьютеров все в большей степени связывают с НС, в частности, с нейрокомпьютерами, основу которых также составляют аппаратно реализованные нейронные сети.