Дискретна математика

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Дискретна математика — галузь математики, що вивчає властивості дискретних структур. До таких структур можуть бути віднесені скінченні групи, скінченні графи, а також деякі математичні моделі перетворювачів інформації, скінченні автомати, машини Тюринга і так далі. Це приклади структур скінченного характеру. Розділ дискретної математики, що вивчає їх, називається скінченною математикою. Іноді саме це поняття розширюють до дискретної математики. Крім вказаних скінченних структур, дискретна математика вивчає деякі системи алгебри, нескінченні графи, обчислювальні схеми певного вигляду, клітинні автомати і т. д. Як синонім іноді вживається термін «дискретний аналіз».

Історія дискретної математики[ред.ред. код]

Багато досліджень в теорії графів мотивували спроби довести, що всі карти, подібно цьому одному, могли бути кольоровими тільки з чотирма кольорами. Kenneth Appel і Wolfgang Haken остаточно довели це в 1976.[1]

Історія дискретної математики пов'язана з розв'язанням складних проблем, що зосереджувались на розгляді областей в межах площини. В теорії графів багато досліджень було викликано спробами довести теорему чотирьох кольорів, вперше сформульовану в 1852 році, але не доведену до 1976 (Кеннет Аппель і Вольфганг Хакен — довели використовуючи суттєву допомогу комп'ютера).

У логіці прикладом таких задач є друга проблема зі списку Давида Гільберта, який був представлений в 1900 році. В ній йдеться про доведення, що арифметичні аксіоми послідовні. Друга теорема Геделя про неповноту формалізованої арифметики, доведена в 1931 році, показала, що це було неможливо — принаймні, як мінімум не в межах арифметичної послідовності. Десята проблема Гільберта повинна була визначити, чи має дане діофантове рівняння цілі коефіцієнтами та цілі рішення. У 1970 році Юрій Матіясевіч довів, що цього не може бути.

Необхідність розбити німецькі коди Другої світової війни призвело до досягнень в області криптографії та теоретичної інформатики, з першою запрограмованою цифровою електронною обчислювальною машиною, розробленою в Англії. У той же час, військові вимоги мотивували досягнення в галузі дослідження операцій. Холодна війна означала, що криптографія залишалася важливою наукою, з фундаментальними досягненнями, такі як шифрування з відкритим ключем, які розробляються в наступних десятиліттях. Дослідження операцій залишаються важливими в якості інструменту управління бізнесом і проектами. Телекомунікаційна промисловість також мотивувала прогрес у дискретній математиці, особливо в теорії графів і теорії інформації. Формальна перевірка тверджень в логіці була необхідна для розробки програмного забезпечення критичних для безпеки систем.

В даний час одним з найбільш відомих відкритих проблем в теоретичній інформатиці є P = NP проблема, яка включає в себе відношення між класами складності P і NP. Математичний інститут Clay запропонував $ 1 млн. USD приз за перший правильний доказ, поряд з призами для шести інших математичних проблем.

Теоретична інформатика[ред.ред. код]

Теоретична інформатика включає в себе області дискретної математики, що мають відношення до обчислень. В значній мірі це спирається на теорію графів і логіки. Включається в межах теоретичної інформатики — вивчення алгоритмів для обчислення математичних результатів. Прорахованості вивчають, що може бути обчислено в принципі, і мають близькі зв'язки з логікою, поки складність вивчає час, взяте обчисленнями. Теорія автоматів і теорія формальної мови близько пов'язані з прорахованості. Мережі Петрі та алгебри процесу гашені, щоб моделювати обчислювальні системи, і методи від дискретної математики гашені в аналізі електронних кругообігів VLSI. Обчислювальна геометрія застосовує алгоритми до геометричних проблем, поки аналіз комп'ютерного зображення застосовує їх до уявлень зображень. Теоретична інформатика також включає вивчення різних безперервних обчислювальних тем.

Теорія інформації[ред.ред. код]

Теорія інформації — це розділ кібернетики, в якому за допомогою математичних методів вивчаються способи вимірювання інформації та методи її кодування з метою стиснення інформації і надійної передачі каналами зв'язку. При формальному поданні знань кожному досліджуваному об'єкту ставиться у відповідність числовий код, зв'язки між об'єктами так само подаються кодами. Для переведення неформальних даних у формальний цифровий вигляд використовуються спеціальні таблиці кодування. Найпростіший приклад такої таблиці — ASCII (American Standard Code for Information Interchange), що керує символами чисел від 0 до 127. Інформація може бути двох видів: дискретна (цифрова) і неперервна (аналогова). Неперервна інформація — це дані, що одержані при неперервному за часом процесі змінювання деякої випадкової величини і описуються неперервними (аналоговими) функціями. Дискретна інформація — це цифрові дані, одержані у результаті квантування (дискретизації) неперервної величини за часом, рівнем або тим і іншим одночасно. Дискретну інформацію зберігати і обробляти набагато простіше, оскільки вона являє собою послідовність чисел. У двійковій системі числення дискретна інформація являє собою послідовність 0 та 1.

Логіка[ред.ред. код]

Коди ASCII

Математична логіка (теоретична логіка, символічна логіка) — розділ математики, що вивчає докази і питання підстав математики. «Предмет сучасної математичної логіки різноманітний.» [1] Відповідно до визначення П. С. Порецкого, «математична логіка є логіка по предмету, математика за методом». Відповідно до визначення Н. І. Кондакова, "математична логіка — друга, після традиційної логіки, щабель у розвитку формальної логіки, що застосовує математичні методи та спеціальний апарат символів і досліджує мислення за допомогою числень (формалізованих мов). " [2] Це визначення відповідає визначенню С. К. Кліні : математична логіка — це «логіка, що розвивається за допомогою математичних методів». [3] Також А. А. Марков визначає сучасну логіку «точною наукою, яка застосовує математичні методи». [4] Всі ці визначення не суперечать, а доповнюють один одного.

Застосування в логіці математичних методів стає можливим тоді, коли судження формулюються на деякому точному мовою. Такі точні мови мають дві сторони: синтаксис і семантику. Синтаксисом називається сукупність правил побудови об'єктів мови (зазвичай званих формулами). Семантикою називається сукупність угод, що описують наше розуміння формул (або деяких з них) і дозволяють вважати одні формули вірними, а інші — ні.

Важливу роль в математичній логіці мають поняття дедуктивної теорії і обчислення. Обчисленням називається сукупність правил виводу, що дозволяють вважати деякі формули виведеними. Правила виведення поділяються на два класи. Одні з них безпосередньо кваліфікують деякі формули як виведені. Такі правила виведення прийнято називати аксіомами. Інші ж дозволяють вважати виведеними формули A, Синтаксично пов'язані деяким заздалегідь певним способом з кінцевими наборами A_1,...A_n виведених формул. Широко застосовуваним правилом другого типу є правило modus ponens: якщо виведені формули A_i(A \to B) , То виводиться і формула B .

Ставлення числень до семантики виражається поняттями семантичної придатності та семантичної повноти обчислення. Обчислення І називається семантично придатним для мови Я, якщо будь-яка виведена в І формула мови Я є вірною. Аналогічно, обчислення І називається семантично повним в мові Я, якщо будь-яка вірна формула мови Я виведена в І.

Математична логіка вивчає логічні зв'язки і відносини лежать в основі логічного (дедуктивного) виводу з використанням мови математики .

Багато хто з розглянутих в математичній логіці мов мають семантично повними і семантично придатними исчислениями. Зокрема, відомий результат К. Геделя про те, що так зване класичне числення предикатів є семантично повним і семантично придатним для мови класичної логіки предикатів першого порядку. З іншого боку, є чимало мов, для яких побудова семантично повного і семантично придатного обчислення неможливо. У цій області класичним результатом є теорема Геделя про неповноту, яка стверджує неможливість семантично повного і семантично придатного числення для мови формальної арифметики.

Варто зазначити, що на практиці безліч елементарних логічних операцій є обов'язковою частиною набору інструкцій всіх сучасних мікропроцесорів і відповідно входить до мови програмування. Це є одним з найважливіших практичних додатків методів математичної логіки, що вивчаються в сучасних підручниках інформатики.

Теорія множин[ред.ред. код]

Докладніше: Теорія множин

В основі теорії множин лежать первинні поняття: множина та елемент множини. Елемент множини перебуває щодо множини у відношенні бути елементом множини (позначається як x \in A[2] — «x є елемент множини A»). Серед похідних понять найважливішими є наступні:

Над множинами визначені наступні операції:

Для множин визначені наступні бінарні відношення:

Комбінаторика[ред.ред. код]

Комбінато́рика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.

Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття.

Комбінаторика пов'язана з багатьма іншими розділами математики.

Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».

Іноді під комбінаторикою розуміють більш широкий розділ дискретної математики, що включає теорію графів.

Приклади комбінаторних конфігурацій і завдань[ред.ред. код]

Для формулювання і рішення комбінаторних завдань використовують різні моделі комбінаторних конфігурацій. Прикладами комбінаторних конфігурацій є:

Розміщенням з n елементів по k називається упорядкований набір з k різних елементів деякого n-елементного безлічі.

Перестановкою з n елементів (наприклад чисел 1,2, ..., n) називається всякий упорядкований набір з цих елементів. Перестановка також є розміщенням з n елементів по n.

Поєднанням з n по k називається набір k елементів, вибраних з даних n елементів. Набори, що відрізняються тільки порядком проходження елементів (але не складом), вважаються однаковими, цим поєднання відрізняються від розміщень.


Композицією числа n називається всяке уявлення n у вигляді впорядкованої суми цілих позитивних чисел.

Розбивкою числа n називається всяке уявлення n у вигляді невпорядкованою суми цілих позитивних чисел.

Прикладами комбінаторних завдань є:

Скількома способами можна розмістити n предметів в m скриньках так, щоб виконувалися задані обмеження? Скільки існує функцій F з m-елементного безлічі в n-елементне, що задовольняють заданим обмеженням? Скільки існує різних перестановок з 52 гральних карт? Відповідь: 52! (52 факторіал), тобто, 80658175170943878571660636856403766975289505440883277824000000000000 або приблизно 8,0658 × 1067. При грі в кістки кидаються дві кістки, і кількість очок, що випали, складаються; скільки існує комбінацій, таких, що сума очок на верхніх гранях дорівнює дванадцяти? Рішення: Кожен можливий результат відповідає функції (Аргумент функції - це номер кістки, значення - окуляри на верхній грані). Очевидно, що лише 6 +6 дає нам потрібний результат 12. Таким чином існує лише одна функція, яка ставить у відповідність 1 число 6, і 2 число 6. Або, іншими словами, існує лише одна комбінація, така, що сума очок на верхніх гранях дорівнює дванадцяти.

Теорія графів[ред.ред. код]

Граф з шістьма вершинами та сімома ребрами

Теорія графів' - розділ дискретної математики, що вивчає властивості графів. У загальному значенні граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якого рахункового множини, а E - підмножина V V.

Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали і т. п. розглядаються як вершини, а з'єднують їхні дороги, інженерні мережі, лінії електропередачі і т. п. - як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.

Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез:


1)Історія виникнення теорії графів

Родоначальником теорії графів вважається Леонард Ейлер. У 1736 році в одному зі своїх листів він формулює і пропонує рішення завдання про сім Кенигсбергских мостах, що стала згодом однією з класичних задач теорії графів.

2)Термінологія теорії графів

Термінологія теорії графів понині не визначена суворо. Зокрема в монографії Гудман, Хідетніемі, 1981 сказано: "У програмістської світі немає єдиної думки про те, який з двох термінів" граф "або" мережа ". Ми вибрали термін "мережа", так як він, мабуть, частіше зустрічається у прикладних областях ". Аналогічна ситуація для" вершина / точка "


3)Зображення графів на площині

При зображенні графів найчастіше використовується наступна система позначень: кожній вершині зіставляється точка на площині, і якщо між вершинами існує ребро, то відповідні точки з'єднуються відрізком. У разі орієнтованого графа відрізки замінюють стрілками.

Не слід плутати зображення графа із власне графом (абстрактної структурою), оскільки одному графу можна зіставити не одне графічне представлення. Зображення покликане лише показати, які пари вершин з'єднані ребрами, а які - ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа чи ні. Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж інші.

Ймовірності[ред.ред. код]

Ймові́рність (лат. probabilitas, англ. probability) — числова характеристика можливості того, що випадкова подія відбудеться в умовах, які можуть бути відтворені необмежену кількість разів. Імовірність є основним поняттям розділу математики, що називається теорія імовірностей.

Випадковою подією називається подія, результат якої не може бути відомий наперед. Навіть у тому разі, коли насправді подія детермінована своїми передумовами, вплив цих передумов може бути настільки складним, що вивести з них наслідок логічно й послідовно, неможливо. Наприклад, при підкидуванні монети, сторона на яку монета впаде визначається положенням руки і монети в руці, швидкістю, обертовим моментом тощо, однак відслідкувати всі ці фактори неможливо, тому результат можна вважати випадковим.

Існують два підходи до означення імовірності: математично-аксіоматичний і Баєсів. Аксіоматичний підхід, строго сформульований Колмогоровим, будується на припущенні, що імовірності елементарних випадкових подій задані, і зосереджується на визначенні ймовірностей складних подій, що є сукупністю елементарних. Так, наприклад, при підкидуванні шестигранного кубика гральної кості, ймовірності випадіння будь-якого числа, вважаються однаковими й рівними 1/6. Виходячи з цієї аксіоми, теорія ймовірності може розрахувати ймовірність того, що сума чисел на двох костях буде, наприклад, 8.

Баєсів підхід не робить припущень про ймовірності елементарних подій, а намагається отримати їх із аналізу попереднього досвіду, спираючись на теорему Баєса і на попередні гіпотези. Баєсів підхід ближчий до того, як визначаються імовірності випадкових подій у природознавстві. Оскільки ці ймовірності наперед невідомі, результати серії дослідів розбиваються на сприятливі й несприятливі, і експериментально визначена ймовірність дорівнює відношенню числа сприятливих подій до числа дослідів, тобто частоті подій.

Надалі в цій статті використовується аксіоматичний математичний підхід.

Означення[ред.ред. код]

Нехай Ω = {ω1, ω2 , … , ωn} — простір елементарних подій. Припустімо, що кожній елементарній події ωk можна поставити у відповідність невід’ємне число pk (імовірність події ωk ), причому \sum_{k=1}^n p_k = 1 .

Якщо  A\, випадкова подія і  A \subset \Omega , то

p(A) = \sum_{\omega_k \in A} p_k ,

де p(A)\, називається імовірністю події  A\, .

Визначення термінів[ред.ред. код]

  • Умовна імовірність P_A(B) — імовірність події B, вирахувана в припущенні, що подія А вже відбулася
  • Несумісні події — дві випадкові події, якщо вони не можуть відбутися одночасно. Якщо події А та В несумісні, то A \cap B = \empty
  • Повна група подій - система випадкових подій така, що в результаті проведеного випадкового експерименту неодмінно станеться одне з них.

Властивості[ред.ред. код]

  • Імовірність достовірної події дорівнює 1.
  • Імовірність неможливої події дорівнює 0.
  • Імовірність випадкової величини є позитивним числом, що міститься між нулем та одиницею
0 \le P(A) \le 1

Теорія чисел[ред.ред. код]

Теорія чисел або вища арифметика - розділ математики, що вивчає цілі числа і подібні об'єкти. Залежно від використовуваних методів теорію чисел поділяють на кілька підтеорій.

1)Елементарна теорія чисел У елементарної теорії чисел цілі числа вивчаються без використання методів інших розділів математики. Такі питання, як подільність цілих чисел, алгоритм Евкліда для обчислення найбільшого загального дільника і найменшого загального кратного, розкладання числа на прості множники, побудова магічних квадратів, вчинені числа, числа Фібоначчі, мала теорема Ферма, теорема Ейлера, завдання про чотири кубах відносяться до цього розділу.

2)Аналітична теорія чисел В аналітичній теорії чисел для виводу і докази тверджень про числа і числових функціях використовується потужний апарат математичного аналізу. Велику роль в аналітичній теорії чисел грає метод тригонометричних сум, що дозволяє оцінювати число рішень тих чи інших рівнянь або систем рівнянь у цілих числах. Основи методу тригонометричних сум розробив і вперше застосував до завдань теорії чисел І. М. Виноградов. Першим успіхом аналітичної теорії чисел було застосування комплексного аналізу в доведенні теореми про розподіл простих чисел. Найбільш відомою і досі не вирішеною проблемою аналітичної теорії чисел є доказ гіпотези Рімана про нулі дзета-функції, яка стверджує, що всі нетривіальні корені рівняння ζ(s)=0 лежать на так званій критичній прямій , Де Re1/2 ζ (s) - дзета-функція Рімана.

3)Алгебраїчна теорія чисел В алгебраїчній теорії чисел поняття числа розширюється, як алгебраїчних чисел розглядають корені многочленів з раціональними коефіцієнтами. При цьому аналогом цілих чисел виступають цілі алгебраїчні числа, тобто коріння унітарних многочленів з цілими коефіцієнтами. На відміну від цілих чисел в кільці цілих алгебраїчних чисел не обов'язково виконується властивість факторіального, тобто, єдиності розкладання на прості множники. Алгебраїчна теорія чисел включає в себе такі розділи, як теорію дівізоров, теорію Галуа, теорію полів класів, дзета- і L-функції Дирихле, когомологий груп і багато іншого. Одним з основних прийомів є вкладення поля алгебраїчних чисел свого поповнення в якийсь із метрик - Архімедова (наприклад, в поле речових або комплексних чисел) або неархімедовой (наприклад, у полі p-адіческіх чисел).

Алгебра[ред.ред. код]

Алгебраїчні структури відбуваються як дискретні приклади, так і неперервні приклади. Дискретна алгебри включають в себе: Булева алгебра використовується в логічних вентилів і програмування; реляційної алгебри, використовувані в базах даних; дискретної і кінцевої версії групи, кільця і поля відіграють важливу роль в алгебраїчній теорії кодування; дискретних напівгруп і моноідов з'являються в теорії формальних мов.

Дискретний аналіз[ред.ред. код]

Дискретний аналіз — це сукупність математичних дисциплін, які можуть вивчатися та розвиватися як самостійні, незалежні теорії (хоча в будь-якому разі ці дисципліни є взаємопроникними та тісно переплітаються навіть при окремому вивченні кожної з них). Незважаючи на це, їх об’єднує дослідження явищ, що мають дискретний характер, або таких, що можуть бути приведені до дискретного виду для спрощення обчислень без втрати актуальності та належного ступеня точності. Необхідність вивчення дискретного аналізу стає більш зрозумілою, якщо врахувати, що практично всі соціально-економічні процеси є дискретними. Навіть якщо такий процес розвивається неперервно, то інформація потрапляє до дослідника дискретно. У даному курсі розглядаються такі дисципліни: теорія множин, математична логіка, комбінаторний аналіз, теорія графів, теорія нечітких підмножин та чисельні методи. 'Обчислення кінцевих різниць.' - Кінцевою різницею функції від однієї або декількох змінних називається приріст функції при даних кінцевих прирости змінних незалежних. Під І. кінцевих різниць розуміють сукупність правил: 1) для визначення змін, яким піддаються функції при кінцевих прирости входять до них змінних, і 2) для визначення первісних функцій, коли змінені їх види відомі (прямий і зворотний способи). При першій появі диференціального обчислення прирощення змінних величин розглядалися як нескінченно малі величини, другими і вищими ступенями яких нехтували, внаслідок чого у багатьох з математиків з'явилося сумнів у строгості самого способу і вірності результатів, одержуваних диференціальним численням. Щоб довести справедливість нового способу, англійський математик Тейлор, у своєму творі «Methodus incrementorum Directa та ін Inversa», виданому в 1715 році, запропонував спосіб І. кінцевих різниць, в якому прирощення змінних розглядалися як кінцеві величини, вищими ступенями яких вже не можна нехтувати. Однак І. кінцевих різниць, що представляє по суті І. рядів, має, як зауважив Лагранж, мало спільного з диференціальним численням, предмет якого є обчислення похідних функцій. Перші сліди І. кінцевих різниць видно в деяких прийомах Фермата, Баррова і Лейбніца, але засновником способу, як самостійного обчислення, слід вважати Тейлора. Пізнішими за тим дослідниками були Ніколь, Кондорсе, Емерсон, Ейлер, Лагранж і Лаплас. Вони удосконалили цю важливу галузь чистого аналізу і показали різні її додатки до інтерполяції і підсумовування рядів, до теорії з'єднань і особливо до теорії ймовірностей.

Геометрія[ред.ред. код]

Обчислювальна геометрія

Обчислювальна геометрія (англ. computational geometry) - галузь комп'ютерних наук присвячена вивченню алгоритмів що описуюються в термінах геометрії.

Основним стимулом розвитку обчислювальної геометрії як дисципліни був прогрес у комп'ютерній графіці та системах автоматизованого проектування та автоматизованих систем технологічної підготовки виробництва, проте багато задач обчислювальної геометрії є класичними за своєю природою, і можуть з'являтись при математичній візуалізації.

Іншим важливим застосуванням обчислювальної геометрії є робототехніка (планування руху та задачі розпізнавання образів), геоінформаційні системи (геометричний пошук, планування маршруту), дизайн мікросхем, програмування станків з числовим програмним управлінням.

Основними розділами обчислювальної геометрії є:

  • 1) Комбінаторна обчислювальна геометрія, чи також названа алгоритмічна геометрія, яка розглядає геометричні об'єкти як дискретні сутності.
  • 2) Чисельна обчислювальна геометрія, також названа машинна геометрія чи геометричне моделювання, яка має справу в основному з представленням об'єктів реального світу в формі придатній для подальшої комп'ютерної обробки.

Топологія[ред.ред. код]

Хоча топології область математики, що формалізує та узагальнює інтуїтивне поняття «безперервної деформації" об'єктів, вона дає початок багатьом дискретним темам; це може бути приписано зокрема до центру на топологічних інваріантах, які безпосередньо зазвичай беруть дискретні значення. Подивіться : комбінаторна топологія, топологічна теорія графів, топологічна комбінаторика, обчислювальна топологія, дискретний топологічний простір, обмежений топологічний простір, топологія (хімія).

Дослідження операцій[ред.ред. код]

Дослідження операцій (ДО) — це дисципліна, що займається розробкою й застосуванням методів знаходження оптимальних рішень на основі математичного моделювання у різних областях людської діяльності. ДО тісно пов'язане з системним аналізом, математичним програмуванням, теорією оптимальних рішень.

ДО — застосування математичних, кількісних методів для обгрунтування рішень у всіх галузях цілеспрямованої людської діяльності. ДО починається тоді, коли для обгрунтування рішень використовується той чи інший математичний апарат. [3]

Теорія ігор, теорія рішень, теорія корисності, теорія суспільного вибору[ред.ред. код]

Теорія ігор[ред.ред. код]

Теорія ігор — розділ прикладної математики, який використовується в соціальних науках (найбільше в економіці), біології, політичних науках, комп'ютерних науках (головним чином для штучного інтелекту) і філософії. Теорія ігор намагається математично зафіксувати поведінку в стратегічних ситуаціях, в яких успіх суб'єкта, що робить вибір залежить від вибору інших учасників.

Математичний апарат Теорія ігор широко використовує різноманітні математичні методи і результати теорії ймовірностей, класичного аналізу, функціонального аналізу (особливо важливими є теореми про нерухомі точки), комбінаторної топології, теорії диференціальних та інтегральних рівнянь, та інші. Специфіка теорії ігор сприяє розробці різноманітних математичних напрямів (наприклад, теорія опуклих множин, лінійне програмування, і так далі).

Теорія рішень[ред.ред. код]

Теорія рішень — царина досліджень, яка математичними методами досліджує закономірності вибору людьми найвигідніших із можливих альтернатив і має застосування в економіці, менеджменті, когнитивній психології, інформатиці та обчислювальній техніці.

Розрізняють нормативну теорію, яка описує раціональний процес вибору та дескриптивну теорію, що стосується практики вирішування.

Основні положення

Теорія рішень базується на шести аксіомах. Лотереєю називається гра з двома виходами: х із ймовірністю р та виходом у з імовірністю 1-р; символьний запис для лотереї:  ~(x,p,y).

Аксіома 1. Виходи х, у, z належать множині виходів.

Аксіома 2. Нехай  ~R означає відношення нестрогої переваги, а  ~I - відношення байдужости (еквівалентности). Виконуються дві умови:

1) зв'язности: xRy \cup yRx;

2) транзитивности: з xRy \cap yRz випливає  ~xRz.

Аксіома 3. Лотереї  ~((x,p,y)q,y) і  ~(x,pq,y) перебувають у відношенні байдужости.

Аксіома 4. Якщо  ~xIy, то  ~(x,p,z)I(y,p,z).

Теорія корисності[ред.ред. код]

Теорія корисності — складова частина економічної теорії, яка прагне пояснити економічну поведінку раціонального індивіда через використання понять «корисність» та «максимізація корисності».

Теорія суспільного вибору[ред.ред. код]

Теорія суспільного вибору - один з розділів економіки, що вивчає різні способи і методи, за допомогою яких люди використовують урядові установи у своїх власних інтересах.

Дискретизація[ред.ред. код]

Ілюстрація дискретизації сигналу. Неперервна функція намальована зеленим кольором, а дискретна послідовність - голубим.

Дискретиза́ція — перетворення функцій неперервних змінних у функції дискретних змінних, за якими початкові неперервні функції можуть бути відновлені із заданою точністю. Роль відліків виконують квантовані значення функцій. Під квантуванням розуміють перетворення неперервної за значеннями величини у величину з дискретною шкалою значень з скінченної множини дозволених, які називають рівнями квантування. Якщо рівні квантування нумеровані, то результатом перетворення є число, яке може бути виражене в будь-якій системі числення.


Дискретні аналоги безперервної математики[ред.ред. код]

Є багато концепцій в безперервній математики, які мають дискретні версії, таких як дискретні обчислення, дискретний розподіл ймовірності, дискретні перетворення , дискретна геометрія, дискретні логарифми, дискрета диференціальна геометрія, дискретне зовнішнє обчислення, дискретні динамічні системи, і дискретних векторних мір.

Примітки[ред.ред. код]

  1. Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 0-691-11533-8. 
  2. Символ \in (від грец. εστι — «бути») введений італійським математиком Джузеппе Пеано.
  3. Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, Главная редакция физико-математической литературы, 1980.

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. Серия: Математика в техническом университете. Изд-во: МГТУ им. Н. Э. Баумана, 2001.- 744 с. ISBN 5-7038-1769-2, 5-7038-1270-4
  • Виленкин Н. Я. Комбинаторика. — М.: 1969.
  • Ерусалимский Я. М. Дискретная математика. — М.: 2000.
  • Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Издательство: Физматлит, 2007. — 408 с. ISBN 978-5-9221-0787-7
  • Капитонова Ю. В., Кривой С. Л., Летичевский А. А., Луцкий Г. М. Лекции по дискретной математике. — СПб.: БХВ-Петербург, 2004. — С. 624. — ISBN 5-94157-546-7
  • Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М.: 1963. — С. 486.
  • МЭС (1995), — М., БРЭ.
  • Новиков Ф.А. Дискретная математика для программистов. — 2-е изд. — СПб.: «Питер», 2005. — С. 364. — ISBN 5-94723-741-5
  • Редькин Н. П. Дискретная математика. Издательство: Лань, 2006. — 96 с. ISBN 5-8114-0522-7
  • Романовский И. В. Дискретный анализ. — 4-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2008. — С. 336.
  • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979. — С. 272.