Основы математической обработки информации и прикладная информатика

Комбинаторика

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

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

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

В основе этой теории лежат «правило суммы» и «правило произведения».

Правило суммы

Если в нашем распоряжении m способов выбрать элемент а и (независимо от них) n способов выбрать элемент b, то выбор «или a или b» можно сделать m+n способами.

Правило произведения

Если в нашем распоряжении m способов выбрать элемент а и n способов выбрать элемент b, то пару (a,b) можно выбрать способами. m × n

Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить n1 способами, второе действие - n2 способами, третье действие - n3 способами и так далее, все k действий вместе могут быть выполнены  n1 × n2 × n3 × ... × nk способами.

Установленный в конечном множестве порядок расположения его элементов называется перестановкой. Число перестановок обозначается латинской буквой Р.

Число перестановок из любого количества k элементов можно найти по формуле:

Pk = 1 × 2 × 3 × ... × k . 

Произведение натуральных чисел от 1 до данного натурального числа k называется факториалом числа k и обозначается k! 

AAAAP9=5n

Каждое упорядоченное подмножество множества А называют размещением. Например: сколькими способами можно выбрать четырех человек на различные должности из девяти кандидатов на эти должности. Так как каждый выбор 4 человек из 9 имеющихся должен иметь определенный порядок распределения их на должности, то мы имеем задачу составления размещений из 9 по 4.

4 = 9 × 8 × 7 × 6 = 3024

Число размещений из n элементов по k вычисляется по формуле:

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

 Произвольные неупорядоченные подмножества данного множества называются сочетаниями. Различные сочетания отличаются друг от друга только составом (выбором) элементов. Количество сочетаний (или число сочетаний) обозначается латинской буквой С и соответствующими индексами. Число сочетаний из n элементов по k вычисляется по формуле

При решении комбинаторных задач следует ответить на следующие вопросы:

1. Из какого множества осуществляется выбор (надо найти n)?

2. Что требуется: расставить все  в ряд (перестановки Р), или выбрать  часть (найти k)?

3. Важен ли порядок? Если важен, то применяем правило размещений А, а если нет - правило сочетаний С.

4. Возможны ли повторения?

 

Логика

Логика - это наука о формах и способах мышления.

Основные формы мышления:

1) Понятие;

2) Высказывание;

3) Умозаключение 

Понятие - это форма мышления, фиксирующая основные, существенные признаки объекта. Характеризуется

• Содержанием

• Объемом

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

Высказывание может быть истинно или ложно.

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

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

Истинно =1    Ложно=0

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

Приоритет логических операций

1. Отрицание.

2. Конъюнкция.

3. Дизъюнкция.

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

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

Законы алгебры высказываний – это тавтологии. Иногда эти законы называются теоремами.

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

 Логические законы  и правила преобразования логических  выражений 

• Закон тождества: всякое высказывание тождественно самому себе. А=А

• Закон непротиворечия: высказывание не может быть одновременно истинным и ложным. А & А=1

• Закон исключенного третьего. Высказывание может быть истинным, либо ложным, третьего не дано. Пример: число 123 либо четное, либо нечетное A ∨ A = 1 .

• Закон двойного отрицания: если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание. A = A

Законы де Моргана:

A & B = A ∨ B A ∨ B = A & B

Переместительный (коммутативный) закон

A ∨ B = B ∨ A A & B = B & A

Сочетательный (ассоциативный) закон

( A ∨ B ) ∨ C = A ∨ (B ∨ C ) ( A & B ) & C = A & (B & C ) 

Распределительный (дистрибутивный) закон

( A & B ) ∨ C = ( A ∨ C ) & (B ∨ C ) ( A ∨ B ) & C = ( A & C ) ∨ (B & C )

 Закон идемпотентности (равносильности)

A ∨ A = A A & A = A

 Закон исключения констант 

A ∨ 1 = 1 A ∨ 0 = A

A & 1 = A A & 0 = 0 

Закон противоречия: Невозможно, чтобы противоречащие высказывания были одновременно истинными

A & A = 0

Закон поглощения

A ∨ ( A & B ) = A A & (A ∨ B) = A

 Закон исключения (склеивания)

( A & B ) ∨ (A & B ) = B

( A ∨ B ) & (A ∨ B ) = B

 

Теория вероятностей

 

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

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

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

Классическое определение вероятности основано на понятии равновозможности исходов. В качестве вероятности выступает отношение количества исходов, благоприятствующих данному событию, к общему числу равновозможных исходов. Например, вероятность выпадения «орла» или «решки» при случайном подбрасывании монетки равна 1/2, если предполагается, что только эти две возможности имеют место[3] и они являются равновозможными. Данное классическое «определение» вероятности можно обобщить на случай бесконечного количества возможных значений — например, если некоторое событие может произойти с равной вероятностью в любой точке (количество точек бесконечно) некоторой ограниченной области пространства (плоскости), то вероятность того, что оно произойдет в некоторой части этой допустимой области равна отношению объёма (площади) этой части к объёму (площади) области всех возможных точек.

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

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

Математические способы обработки информации

К математическим методам обработки информации относятся:

1) методы элементарной математики, используемые, в том числе и в традиционных методах обработки информации;

2) классические методы математического анализа, которые применяются не только в рамках других дисциплин, но и отдельно;

3) методы математического программирования;

4) методы экономической кибернетики.

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

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

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

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

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

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