Теория информации. Статистический подход
Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 04.06.2010 |
| Размер файла | 79,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
12
МОСКОВСКИЙ ГУМАНИТАРНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ
Калужский филиал
Юридический факультет
Кафедра гражданско-правовых дисциплин
Контрольная работа
по учебному курсу
"Математические методы анализа и принятия решений"
Выполнил: Титов Е.А.
студент 4-го курса
группа ЮЗВС-08
Руководитель:
Махмудов Н.Р.
Калуга - 2010 г.
План
- Статистический подход к измерению правовой информации
- Графический метод решения задач линейного программирования
- Методика решения задач ЛП графическим методом
- Список используемой литературы
Статистический подход к измерению правовой информации
Статистический подход изучается в разделе кибернетики, называемом теорией информации. Его основоположником считается К. Шеннон, опубликовавший в 1948 году свою математическую теорию связи. Большой вклад в теорию информации до него внесли ученые Найквист и Хартли.
В 1924 и 1928 гг. они опубликовали работы по теории телеграфии и передаче информации. Признаны во всем мире исследования по теории информации российских ученых А.Н. Колмогорова, А.Я. Хинчина, В.А. Котельникова, А.А. Харкевича и др.
К. Шенноном было введено понятие количество информации как меры неопределенности состояния системы, снимаемой при получении информации.
Количественно выраженная неопределенность состояния получила название энтропии по аналогии с подобным понятием в статистической механике.
При получении информации уменьшается неопределенность, т.е. энтропия, системы. Очевидно, что чем больше информации получает наблюдатель, тем больше снимается неопределенность, и энтропия системы уменьшается.
При энтропии, равной нулю, о системе имеется полной информация, и наблюдателю она представляется целиком упорядоченной. Таким образом, получение информации связано с изменением степени неосведомленности получателя о состоянии этой системы.
До получения информации ее получатель мог иметь некоторые предварительные (априорные) сведения о системе Х.
Оставшаяся неосведомленность и является для него мерой неопределенности состояния (энтропией) системы. Обозначим априорную энтропию системы Х.
После получения некоторого сообщения наблюдатель приобрел дополнительную информацию уменьшившую его начальную неосведомленность.
Другими словами, количество информации измеряется уменьшением (изменением) неопределенности состояния системы.
Вероятность p - количественная априорная (т.е. известная до проведения опыта) характеристика одного из исходов (событий) некоторого опыта. Измеряется в пределах от 0 до 1.
Если заранее известны все исходы опыта, сумма их вероятностей равна 1, а сами исходы составляют полную группу событий.
Если все исходы могут свершиться с одинаковой долей вероятности, они называются равновероятными.
Например, пусть опыт состоит в сдаче студентом экзамена по информатике.
Очевидно, у этого опыта всего 4 исхода (по количеству возможных оценок, которые студент может получить на экзамене).
Тогда эти исходы составляют полную группу событий, т.е. сумма их вероятностей равна 1. Если студент учился хорошо в течение семестра, значения вероятностей всех исходов могут быть такими:
p (5) = 0.5; p (4) = 0.3; p (3) = 0.1; p (2) = 0.1, где запись p (j) означает вероятность исхода, когда получена оценка j (j = {2, 3, 4, 5}).
Если студент учился плохо, можно заранее оценить возможные исходы сдачи экзамена, т.е. задать вероятности исходов, например, следующим образом: p (5) = 0.1; p (4) = 0.2; p (3) = 0.4; p (2) = 0.3.
В обоих случаях выполняется условие:
где n - число исходов опыта,
i - номер одного из исходов.
Пусть можно получить n сообщений по результатам некоторого опыта (т.е. у опыта есть n исходов), причем известны вероятности получения каждого сообщения (исхода) - pi.
Тогда в соответствии с идеей Шеннона, количество информации I в сообщении i определяется по формуле:
I = - log2 pi,
где pi - вероятность i-го сообщения (исхода).
Пример 1. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для студента-хорошиста.
Пусть I (j) - количество информации в сообщении о получении оценки j. В соответствии с формулой Шеннона имеем:
I (5) = - log2 0,5 = 1,I (4) = - log2 0,3 = 1,74,I (3) = - log2 0,1 = 3,32
I (2) = - log2 0,1 = 3,32.
Пример 2. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для нерадивого студента:
I (5) = - log2 0,1 = 3,32,I (4) = - log2 0,2 = 2,32,I (3) = - log2 0,4 = 1,32,I (2) = - log2 0,3 = 1,74.
Таким образом, количество получаемой с сообщением информации тем больше, чем неожиданнее данное сообщение. Этот тезис использован при эффективном кодировании кодами переменной длины (т.е. имеющими разную геометрическую меру): исходные символы, имеющие большую частоту (или вероятность), имеют код меньшей длины, т.е. несут меньше информации в геометрической мере, и наоборот.
Формула Шеннона позволяет определять также размер двоичного эффективного кода, требуемого для представления того или иного сообщения, имеющего определенную вероятность появления.
Помимо информационной оценки одного сообщения, Шеннон предложил количественную информационную оценку всех сообщений, которые можно получить по результатам проведения некоторого опыта. Так, среднее количество информации Iср, получаемой со всеми n сообщениями, определяется по формуле:
где pi - вероятность i-го сообщения.
Пример 3. Определить среднее количество информации, получаемое студентом-хорошистом, по всем результатам сдачи экзамена.
В соответствии с приведенной формулой имеем:
Iср = - (0,5*log20,5 + 0,3*log20,3 + 0,1*log20,1 + 0,1*log20,1) = 1,67.
Пример 4. Определить среднее количество информации, получаемое нерадивым студентом, по всем результатам сдачи экзамена.
В соответствии с приведенной формулой имеем:
Iср = - (0,1*log20,1 + 0,2*log20,2 + 0,4*log20,4 + 0,3*log20,3) = 1,73.
Большее количество информации, получаемое во втором случае, объясняется большей непредсказуемостью результатов: в самом деле, у хорошиста два исхода равновероятны.
Пусть у опыта два равновероятных исхода, составляющих полную группу событий, т.е. p1 = p2 = 0,5. Тогда имеем в соответствии с формулой для расчета I ср:
I ср = - (0,5*log20,5 + 0,5*log20,5) = 1.
Эта формула есть аналитическое определение бита по Шеннону: это среднее количество информации, которое содержится в двух равновероятных исходах некоторого опыта, составляющих полную группу событий.
Единица измерения информации при статистическом подходе - бит.
На практике часто вместо вероятностей используются частоты исходов. Это возможно, если опыты проводились ранее и существует определенная статистика их исходов. Так, строго говоря, в построении эффективных кодов участвуют не частоты символов, а их вероятности
Введенная количественная статистическая мера информации широко используется в теории информации для оценки собственной, взаимной, условной и других видов информации.
Графический метод решения задач линейного программирования
Теоретическое введение.
Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость (рис.1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР.). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1) ОДР является пустым множеством.
Все вышесказанное относится и к случаю, когда система ограничений (1) включает равенства, поскольку любое равенство
можно представить в виде системы двух неравенств (см. рис.1)
ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см. рис.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.
Рисунок 1. Геометрическая интерпретация ограничений и ЦФ задачи.
Методика решения задач ЛП графическим методом
В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0; 0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
Построить вектор , который начинается в точке (0; 0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
Задача. Правоохранительные органы разработали 10 программ по борьбе с преступлениями в сфере экономики, причем среди этих программ есть одинаковые: 5 одинаковы по одним свойствам, 3 программы по другим свойствам и 2 программы одинаковы по третьим свойствам. Сколькими способами эти программы могут быть переставлены?
Ответ.5*3*2 =30
Список используемой литературы
1. Аветисян Р.Д., Аветисян Д.В. Теоретические основы информатики. - М.: РГГУ, 1997.
2. Гришкин И.И. Понятие информации. Логико-методологический аспект. - М.: Наука, 1973.
3. Дмитриев В.И. Прикладная теория информации. - М., 1989.
4. Седов Е.А. Эволюция и информация. - М.: Наука, 1976.
5. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов.
6. Кононов В.А. - Исследование операций. Для продвинутых математиков.
7. Чернавский Д.С. Синергетика и информация. - М.: Знание, 1990.
Подобные документы
Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлен 11.12.2011Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Система передачи информации, ее количество и логарифмическая мера. Ансамбль сообщений, виды единиц информации. Свойства количества информации. Энтропия как содержательность и мера неопределенности информации, ее свойства. Понятие избыточности сообщений.
реферат [35,1 K], добавлен 01.08.2009Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011
