Комбинаторика, статистика и теория вероятностей

Лаплас предложил первую математически обоснованную космогоническую гипотезу образования всех тел Солнечной системы, называемую его именем: гипотеза Лапласа. Он также первый высказал предположение, что некоторые наблюдаемые на небе туманности на самом деле - удалённые галактики, подобные нашему Млечному пути.

Он далеко продвинул теорию возмущений и убедительно показал: все отклонения положения планет от предсказанных законами Ньютона (точнее говоря, предсказанных решением задачи двух тел) объясняются взаимовлиянием планет, которое можно учесть с помощью тех же законов Ньютона. Ещё в 1695 году Галлей обнаружил, что Юпитер в течение нескольких веков постепенно ускоряется и приближается к Солнцу, а Сатурн, наоборот, замедляется и удаляется от Солнца. Некоторые учёные полагали, что в конце концов Юпитер упадёт на Солнце. Лаплас открыл причины этих смещений (неравенств) - взаимовлияние планет, и показал, что это не более чем периодические колебания, и всё возвращается в исходное положение каждые 929 лет [2].

До открытий Лапласа немало учёных пытались объяснить отклонения теории от наблюдений движением эфира, конечной скоростью тяготения и иными неньютоновскими факторами; Лаплас надолго похоронил подобные попытки. Он, как ранее Клеро, провозгласил: в небесной механике нет иных сил, кроме ньютоновских, и аргументированно обосновал этот тезис.

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

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

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

Вычислив условия равновесия кольца Сатурна, Лаплас доказал, что они возможны лишь при быстром вращении планеты около оси, и это действительно было доказано потом наблюдениями Уильяма Гершеля.

Лаплас разработал теорию приливов при помощи двадцатилетних наблюдений уровня океана в Бресте.

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

Первое триумфальное выступление молодого математика относится к 1690 году. Якоб решает задачу Лейбница о форме кривой, по которой тяжелая точка опускается за равные промежутки времени на равные вертикальные отрезки. Лейбниц и Гюйгенс уже установили, что это полукубическая парабола, но лишь Якоб Бернулли опубликовал доказательство средствами нового анализа, выведя и проинтегрировав дифференциальное уравнение. При этом впервые появился в печати термин "интеграл".

Якоб Бернулли внёс огромный вклад в развитие аналитической геометрии и зарождение вариационного исчисления. Его именем названа лемниската Бернулли. Он исследовал также циклоиду, цепную линию, и особенно логарифмическую спираль. Последнюю из перечисленных кривых Якоб завещал нарисовать на своей могиле; по невежеству там изобразили спираль Архимеда, см. фотографию справа. Согласно завещанию, вокруг спирали выгравирована надпись на латыни, "EADEM MUTATA RESURGO" ("изменённая, я вновь воскресаю"), которая отражает свойство логарифмической спирали восстанавливать свою форму после различных преобразований.

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

Он изучил теорию вероятностей по книге Гюйгенса "О расчётах в азартной игре", в которой ещё не было определения и понятия вероятности (её заменяет количество благоприятных случаев). Якоб Бернулли ввёл значительную часть современных понятий теории вероятностей и сформулировал первый вариант закона больших чисел. Якоб Бернулли подготовил монографию в этой области, однако издать её не успел. Она была напечатана посмертно, в 1713 году, его братом Николаем, под названием "Искусство предположений" (Ars conjectandi). Это содержательный трактат по теории вероятностей, статистике и их практическому применении, итог комбинаторики и теории вероятностей XVII века. Имя Якоба носит важное в комбинаторике распределение Бернулли.

Якоб Бернулли издал также работы по различным вопросам арифметики, алгебры, геометрии и физики.

4. Графы

В математической теории графов и информатике граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

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

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

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

Граф, или неориентированный граф - это упорядоченная пара , для которой выполнены следующие условия:

· - это непустое множество вершин или узлов;

· - это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе - порядком, число рёбер - размером графа.

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) - это упорядоченная пара , для которой выполнены следующие условия:

· - это непустое множество вершин или узлов,

· - это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга - это упорядоченная пара вершин , где вершину называют началом, а - концом дуги. Можно сказать, что дуга ведёт от вершины к вершине .

Смешанный граф - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой , где , и определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

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

4.1 Изображение графов на плоскости

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

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие - нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

4.2 Дополнительные характеристики графов

Граф называется:

· связным, если для любых вершин , есть путь из в .

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

· деревом, если он связный и не содержит простых циклов.

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

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

· k-дольным, если его вершины можно разбить на непересекающихся подмножества , , …, так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

· полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.

· планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.

· взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.

· хордальным, если граф не содержит индуцированных циклов с длиной больше трех.

Также бывает:

· k-раскрашиваемым

· k-хроматическим

Обобщение понятия графа. Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку , где и - некоторые множества (вершин и рёбер, соотв.), а - функция инцидентности (или инцидентор), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин и из (его концов). Частными случаями этого понятия являются:

· ориентированные графы (орграфы) - когда всегда является упорядоченной парой вершин;

· неориентированные графы - когда всегда является неупорядоченной парой вершин;

· смешанные графы - в котором встречаются как ориентированные, так и неориентированные рёбра и петли;

· Эйлеровы графы - граф в котором существует циклический эйлеров путь (Эйлеров цикл).

· мультиграфы - графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;

· псевдографы - это мультиграфы, допускающие наличие петель;

· простые графы - не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

· гиперграф - если ребро может соединять более двух вершин.

· ультраграф - если между элементами и существуют бинарные отношения инцидентности.

4.3 Теория графов

Теомрия грамфов - раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E - подмножество VЧV.

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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

4.4 Применение теории графов

· В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия - сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.

· В информатике и программировании (граф-схема алгоритма)

· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

· В экономике

· В логистике

· В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф илигиперграф).

5. Математическая статистика

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

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

5.1 Предмет и метод математической статистики

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

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

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

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

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

Задачи восстановления зависимостей активно изучаются более 200 лет, с момента разработки К. Гауссом в 1794 г. метода наименьших квадратов.

Разработка методов аппроксимации данных и сокращения размерности описания была начата более 100 лет назад, когда К. Пирсон создал метод главных компонент. Позднее были разработаны факторный анализ[2] и многочисленные нелинейные обобщения.

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

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

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

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

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

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

5.2 Связь математической статистики с теорией вероятностей

Связь математической статистики с теорией вероятностей имеет в разных случаях различный характер. Вероятностей теория изучает не любые явления, а явления случайные и именно "вероятностно случайные", то есть такие, для которых имеет смысл говорить о соответствующих им распределениях вероятностей. Тем не менее, теория вероятностей играет определённую роль и при статистическом изучении массовых явлений любой природы, которые могут не относиться к категории вероятностно случайных. Это осуществляется через основанные на теории вероятностей теорию выборочного метода и теорию ошибок измерений. В этих случаях вероятностным закономерностям подчинены не сами изучаемые явления, а приёмы их исследования.

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

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

5.3 Историческая справка

Первые начала математической статистики можно найти уже в сочинениях создателей теории вероятностей - Я. Бернулли (конец 17 - начало 18 веков), П. Лапласа (2-я половина 18 - начало 19 веков) и С. Пуассона (1-я половина 19 века). В России методы математической статистики в применении к демографии и страховому делу развивал на основе теории вероятностей В.Я. Буняковский (1846). Решающее значение для всего дальнейшего развития математической статистики имели работы русской классической школы теории вероятностей 2-й половины 19 - начала 20 веков (П.Л. Чебышев, А.А. Марков, А.М. Ляпунов, С.Н. Бернштейн). Многие вопросы теории статистических оценок были по существу разработаны на основе теории ошибок и метода наименьших квадратов [К. Гаусс (1-я половина 19 века) и А.А. Марков (конец 19 - начало 20 веков)]. Работы А. Кетле (19 век, Бельгия), Ф. Гальтона (19 век, Великобритания) и К. Пирсона (конец 19 - начало 20 веков, Великобритания) имели большое значение, но по уровню использования достижений теории вероятностей отставали от работ русской школы.

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

В создании теории малых выборок, общей теории статистических оценок и проверки гипотез (освобожденной от предположений о наличии априорных распределений), последовательного анализа весьма значительна роль представителей англо-американской школы [Стьюдент (псевдоним У. Госсета), Р. Фишер, Э. Пирсон - Великобритания, Ю. Нейман, А. Вальд - США], деятельность которых началась в 20-х годах 20 века.

В СССР значительные результаты в области математической статистики получены В.И. Романовским, Е.Е. Слуцким, которому принадлежат важные работы по статистике связанных стационарных рядов, Н.В. Смирновым, заложившим основы теории непараметрических методов М. с., Ю.В. Линником, обогатившим аналитический аппарат математической статистики новыми методами.

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

Существует несколько журналов, публикующих работы по математической статистике, в том числе "Annals of Statistics" (до 1973 "Annals of Mathematical Statistics"), "International Statistical Institute Review", "Biometrika", "Journal of the Royal Statistical Society". Имеются научные ассоциации, поддерживающие исследования по математической статистике и её применениям. Важную роль играет Международный статистический институт (ISI) с центром в Амстердаме и созданная при нём Международная ассоциация по статистическим методам в естественых науках (IASPS).

Используемые источники информации

1. http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chPascalTriangle.xhtml

2. http://www.cyberforum.ru/statistics/thread739957.html

3. Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. - 1970. - № 6. - С. 17-25.

4. http://edu.nstu.ru/courses/saod/graph.htm

5. http://ru.wikipedia.org/

6. http://dic.academic.ru/dic.nsf/bse/

7. Вероятность и математическая статистика. Энциклопедия / Гл. ред. Ю.В. Прохоров. - М.: Изд-во "Большая Российская Энциклопедия", 1999.

Размещено на Allbest.ru