Теоретическая информатика

Информац. системы

Критерии надежности
Задачи
Расчет характеристики
Типовые примеры
Отказы изделия
Аналит. определение
Постоянное резервир.
Резервирование замещением
Расчет надежности
Скользящее резервирование
Расчет показателей
Учебник JAVA
Базовые понятия
Объектно-ориентированное
программирование
Работа со строками и классами
Графические примитивы
Обработка событий в JAVA
Апплеты
Создание сетевых приложений
Сетевые средства в JAVA
Экспертные системы
Учебник Delphi
Компьютерные сети
Топология сетей
Адресация
Структура сети
Сетевые службы
Маршрутизаторы
Технологии ISDN
Протоколы маршрутизации
Модель OSI
Корпоративные сети
Стек протоколов TCP/IP
Коммутация каналов
Коммутация пакетов
Удаленный доступ
Система доменных имен
Моделирование
Основы кодирования
Теория информ. процессов
Обмен информацией
Количество информации
Энтропия
Кодирование
Квантование и дискретизация
Теорема Котельникова
Ошибки дискретизации
Учебник по FrontPage
Информационный подход
SQL язык запросов
Ос новные понятия
Выборка данных

Манипулирование данными

Создание базы данных
Устройство ПК
Архитектура ПК
Классификация элементов
Центральный процессор
Внешние устройства
Программное обеспечение

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

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

Большие системы

Математическая модель - приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики.

Основные виды моделирования систем

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

Аналитическая модель

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

Сложные системы

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

Традиционная схема моделирования и схема системного моделирования

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

Теория математических моделей

Статистическое моделирование систем на ЭВМ

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

Пример решения детерминированной задачи

Пример решения стохастической задачи

Три способа получения случайных чисел Табличный. Предположим, что мы осуществили N независимых опытов, в результате которых получили N случайных цифр e1…eN . Записав эти цифры в порядке появления в таблицу, получим таблицу случайных цифр. Способ употребления такой таблицы очень прост.

Преобразования случайных величин

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

Моделирование непрерывных случайных величин

Пример

Пример.  Случайная точка Q в декартовых координатах (x1,x2)  р.р. в прямоугольнике  Плотность вероятностей точки Q постоянна в П:

Пример. Случайная точка Q(x,h,z), равномерно распределенная в шаре x2+y2+z2<R2 . 

(x,y,z)-декартовы координаты т.Q.

Применение полярных координат

Смоделировать случайную величину

Метод суперпозиции

Пример. Случайная величина x определена на 0<x<1 и имеет функцию распределения  где все Ck³0.

Моделирование биномиальных распределений

Моделирование усеченных распределений

Метод Неймана

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

Простейший метод Монте-Карло

Пример. Пусть надо вычислить интеграл  где k>0.

Частичное аналитическое интегрирование

Интегрирование по части области

Теорема

Пример.

Теория массового обслуживания

Задачи теории массового обслуживания При исследовании операций часто приходится сталкиваться с работой своеобразных систем, называе­мых системами массового обслуживания (СМО). При­мерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, магазины, парикмахерские и т.п.

Классификация СМО Системы массового обслуживания

Терминология ТМО Теория массового обслуживания

Потоки событий. Простейший поток

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

Пуассоновский поток

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

Стационарный режим в СМО

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

Формула Литтла

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

Решение. Номер состояния системы равен числу заявок в системе. Т.к. система с отказами, то число состояний системы равно n+1 (числу каналов в системе + нулевое состояние).

Пример. Имеется станция связи с тремя каналами (n=3), интенсивность потока заявок l= 1,5 (заявки в мину­ту); среднее время обслуживания одной заявки tобсл=2 (мин.), все потоки событий простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q. Pотк , kср .

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

Теоретически число состояний ничем не ограничено

Найдем среднее число заявок в СМО Lсист

Пример. Одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую по­ступает простейший поток составов с интенсивностью l= 2 (состава в час). Обслуживание (расформирова­ние) состава длится случайное показательное время со средним значением tобсл=20(мин). В парке прибы­тия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внеш­них путях.

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

Одноканальная СМО с ограниченной очередью

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

Многоканальная немарковская СМО

Варианты курсовых работ

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

Рассмотрим примеры хорошего и плохого планов эксперимента

Обеспечение точности и достоверности результатов моделирования

Оценка чувствительности модели

Математический анализ, лекции по физике Компьютерные сети