Diskrétní matematika - Discrete mathematics

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Diskrétní matematika"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Února 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Grafy takhle patří mezi objekty studované diskrétní matematikou pro jejich zajímavost matematické vlastnosti, jejich užitečnost jako modelů problémů reálného světa a jejich význam při vývoji počítače algoritmy.

Diskrétní matematika je studium matematické struktury které jsou zásadně oddělený spíše než kontinuální. Na rozdíl od reálná čísla které mají vlastnost měnit se "plynule", objekty studované v diskrétní matematice - jako např celá čísla, grafy, a prohlášení v logika^[1] - nemění se tímto způsobem plynule, ale mají odlišné oddělené hodnoty.^[2][3] Diskrétní matematika proto vylučuje témata z „spojité matematiky“ jako např počet nebo Euklidovská geometrie. Diskrétní objekty často mohou být vyjmenovaný podle celých čísel. Diskrétnější matematika byla formálněji charakterizována jako obor matematiky, který se zabývá spočítatelné sady^[4] (konečné množiny nebo množiny se stejným mohutnost jako přirozená čísla). Neexistuje však přesná definice pojmu „diskrétní matematika“.^[5] Diskrétní matematika je ve skutečnosti popsána méně tím, co je zahrnuto, než tím, co je vyloučeno: neustále se měnícími veličinami a souvisejícími pojmy.

Soubor objektů studovaných v diskrétní matematice může být konečný nebo nekonečný. Termín konečná matematika se někdy aplikuje na části oblasti diskrétní matematiky, která se zabývá konečnými množinami, zejména v oblastech souvisejících s obchodem.

Výzkum v diskrétní matematice vzrostl ve druhé polovině dvacátého století částečně kvůli vývoji digitální počítače které pracují v diskrétních krocích a ukládají data do diskrétních bitů. Koncepty a zápisy z diskrétní matematiky jsou užitečné při studiu a popisu objektů a problémů v oborech počítačová věda, jako počítačové algoritmy, programovací jazyky, kryptografie, automatizované dokazování věty, a vývoj softwaru. Naopak, počítačové implementace jsou významné při aplikaci myšlenek z diskrétní matematiky na problémy v reálném světě, například v operační výzkum.

Ačkoli hlavním předmětem studia v diskrétní matematice jsou diskrétní objekty, často se také používají analytické metody z kontinuální matematiky.

V univerzitních osnovách se „diskrétní matematika“ objevila v 80. letech, původně jako kurz podpory informatiky; jeho obsah byl v té době poněkud nahodilý. Učební plán se poté vyvinul ve spojení s úsilím ACM a MAA do kurzu, který je v zásadě určen k rozvoji matematická zralost u studentů prvního ročníku; proto je v dnešní době předpokladem také pro obory matematiky na některých univerzitách.^[6][7] Objevily se také některé učebnice diskrétní matematiky na střední škole.^[8] Na této úrovni je diskrétní matematika někdy považována za přípravný kurz, ne nepodobný precalculus v tomto ohledu.^[9]

The Fulkersonova cena je oceněn za vynikající práce v diskrétní matematice.

Velké výzvy, minulé i současné

Hodně výzkumu v teorie grafů byl motivován pokusy dokázat, že všechny mapy, jako je tato, mohou být barevný použitím pouze čtyři barvy takže žádné oblasti stejné barvy nesdílejí hranu. Kenneth Appel a Wolfgang Haken dokázal to v roce 1976.^[10]

Historie diskrétní matematiky zahrnovala řadu náročných problémů, které zaměřily pozornost v oblastech oboru. V teorii grafů bylo mnoho výzkumů motivováno pokusy dokázat čtyřbarevná věta, který byl poprvé uveden v roce 1852, ale nebyl prokázán až do roku 1976 (Kenneth Appel a Wolfgang Haken, využívající významnou počítačovou pomoc).^[10]

v logika, druhý problém na David Hilbert seznam otevřených problémy v roce 1900 bylo prokázáno, že axiomy z aritmetický jsou konzistentní. Gödelova druhá věta o neúplnosti, prokázáno v roce 1931, ukázalo, že to není možné - alespoň ne v rámci samotné aritmetiky. Hilbertův desátý problém bylo určit, zda daný polynom Diophantine rovnice s celočíselnými koeficienty má celočíselné řešení. V roce 1970 Jurij Matijasevič dokázal, že tohle nemohlo být provedeno.

Potřeba přestávka Německé kódy v druhá světová válka vedlo k pokroku v kryptografie a teoretická informatika, s první programovatelný digitální elektronický počítač se vyvíjí v Anglii Bletchley Park s vedením Alan Turing a jeho klíčová práce, O vypočítatelných číslech.^[11] Vojenské požadavky zároveň motivovaly pokrok v roce operační výzkum. The Studená válka znamenalo, že kryptografie zůstala důležitá se základními pokroky, jako je kryptografie veřejného klíče v následujících desetiletích. Provozní výzkum zůstal důležitým nástrojem v obchodním a projektovém řízení s metoda kritické cesty se vyvíjí v 50. letech. The telekomunikace průmysl také motivoval pokroky v diskrétní matematice, zejména v teorii grafů a teorie informace. Formální ověření logických příkazů bylo nutné pro vývoj softwaru z bezpečnostní kritické systémy a zálohy v automatizované dokazování věty byli touto potřebou poháněni.

Výpočetní geometrie byla důležitou součástí počítačová grafika začleněna do moderní videohry a počítačem podporovaný design nástroje.

Několik oblastí diskrétní matematiky, zejména teoretické informatiky, teorie grafů a kombinatorika, jsou důležité při řešení náročných úkolů bioinformatika problémy spojené s porozuměním strom života.^[12]

V současné době je jedním z nejznámějších otevřených problémů teoretické informatiky P = NP problém, což zahrnuje vztah mezi třídy složitosti P a NP. The Hliněný matematický institut nabídl 1 milion dolarů americký dolar cena za první správný důkaz spolu s cenami pro šest dalších matematických úloh.^[13]

Témata diskrétní matematiky

Teoretická informatika

Složitost studuje čas potřebný pro algoritmy, jako je tento rutina třídění.

Teoretická informatika zahrnuje oblasti diskrétní matematiky související s výpočty. Silně čerpá teorie grafů a matematická logika. Součástí teoretické informatiky je studium algoritmů a datových struktur. Vyčíslitelnost studuje to, co lze v zásadě vypočítat, a má úzké vazby na logiku, zatímco složitost studuje čas, prostor a další zdroje získané výpočty. Teorie automatů a formální jazyk teorie úzce souvisí s vypočítatelností. Petriho sítě a zpracovat algebry se používají k modelování počítačových systémů a metody z diskrétní matematiky se používají při analýze VLSI elektronické obvody. Výpočetní geometrie aplikuje algoritmy na geometrické problémy, zatímco počítačová analýza obrazu aplikuje je na reprezentace obrázků. Teoretická informatika také zahrnuje studium různých souvislých výpočetních témat.

Informační teorie

The ASCII kódy pro slovo "Wikipedia", uvedené zde v binární, poskytnout způsob reprezentace slova v teorie informace, jakož i pro zpracování informací algoritmy.

Informační teorie zahrnuje kvantifikaci informace. Úzce souvisí je teorie kódování který se používá k návrhu efektivních a spolehlivých metod přenosu a ukládání dat. Informační teorie zahrnuje také souvislá témata, jako jsou: analogové signály, analogové kódování, analogové šifrování.

Logika

Logika je studium principů platného uvažování a odvození, stejně jako z konzistence, zdravost, a úplnost. Například ve většině logických systémů (ale ne v systému) intuicionistická logika ) Peirceův zákon (((P→Q)→P)→P) je věta. Pro klasickou logiku to lze snadno ověřit pomocí pravdivostní tabulka. Studium matematický důkaz je zvláště důležitý v logice a má aplikace automatizované dokazování věty a formální ověření softwaru.

Logické vzorce jsou diskrétní struktury důkazy, které tvoří konečný stromy^[14] nebo obecněji směrovaný acyklický graf struktur^[15][16] (s každým inferenční krok kombinace jednoho nebo více předpoklad větve dát jediný závěr). The pravdivostní hodnoty logických vzorců obvykle tvoří konečnou množinu, obecně omezenou na dvě hodnoty: skutečný a Nepravdivé, ale logika může být také průběžně oceňována, např. fuzzy logika. Byly také studovány koncepty, jako jsou nekonečné důkazní stromy nebo nekonečné derivační stromy,^[17] např. nekonečná logika.

Teorie množin

Teorie množin je obor matematiky, který studuje sady, což jsou sbírky objektů, například {modrá, bílá, červená} nebo (nekonečná) sada všech prvočísla. Částečně objednané sady a sady s jinými vztahy mít aplikace v několika oblastech.

V diskrétní matematice spočítatelné sady (počítaje v to konečné množiny ) jsou hlavním zaměřením. Začátek teorie množin jako odvětví matematiky se obvykle vyznačuje Georg Cantor práce rozlišující mezi různými druhy nekonečná sada, motivovaný studiem trigonometrických řad, a další vývoj teorie nekonečných množin je mimo rámec diskrétní matematiky. Opravdu, současná práce v deskriptivní teorie množin rozsáhle využívá tradiční spojitou matematiku.

Kombinatorika

Combinatorics studuje způsob, jakým lze kombinovat nebo uspořádat jednotlivé struktury.Enumerativní kombinatorika soustředí se na počítání počtu určitých kombinatorických objektů - např. the dvanáctinásobně poskytuje jednotný rámec pro počítání obměny, kombinace a oddíly.Analytická kombinatorika týká se výčtu (tj. určení počtu) kombinatorických struktur pomocí nástrojů od komplexní analýza a teorie pravděpodobnosti. Na rozdíl od enumerativní kombinatoriky, která používá explicitní kombinatorické vzorce a generující funkce k popisu výsledků je cílem analytická kombinatorika asymptotické vzorce.Design theory is a study of kombinatorické vzory, což jsou sbírky podmnožin s určitými průsečík vlastnosti.Teorie rozdělení studuje různé výčty a asymptotické problémy související s celočíselné oddíly, a úzce souvisí s řada q, speciální funkce a ortogonální polynomy. Původně součást teorie čísel a analýza, teorie rozdělení je nyní považována za součást kombinatoriky nebo nezávislé pole.Teorie objednávek je studium částečně objednané sady konečný i nekonečný.

Teorie grafů

Teorie grafů má úzké odkazy na teorie skupin. Tento zkrácený čtyřstěn graf souvisí s střídavá skupina A₄.

Teorie grafů, studium grafy a sítí, je často považována za součást kombinatoriky, ale rozrostla se dostatečně velká a dostatečně odlišná, se svými vlastními druhy problémů, aby mohla být považována za samostatný subjekt.^[18] Grafy jsou jedním z hlavních objektů studia v diskrétní matematice. Patří mezi nejvíce všudypřítomné modely přírodních i člověkem vytvořených struktur. Mohou modelovat mnoho typů vztahů a dynamiky procesů ve fyzických, biologických a sociálních systémech. V počítačové vědě mohou představovat komunikační sítě, organizaci dat, výpočetní zařízení, výpočetní tok atd. V matematice jsou užitečné v geometrii a určitých částech topologie, např. teorie uzlů. Algebraická teorie grafů má úzké vazby na teorii skupin. Jsou tu také spojité grafy; výzkum v teorii grafů však většinou spadá do oblasti diskrétní matematiky.

Pravděpodobnost

Diskrétní teorie pravděpodobnosti se zabývá událostmi, které se vyskytují ve spočetných ukázkové prostory. Například početní pozorování, jako jsou počty ptáků v hejnech, obsahují pouze přirozené hodnoty čísel {0, 1, 2, ...}. Na druhou stranu kontinuální pozorování, jako jsou váhy ptáků, obsahují hodnoty reálných čísel a obvykle by byla modelována kontinuálním rozdělením pravděpodobnosti, jako je normální. Diskrétní rozdělení pravděpodobnosti lze použít k aproximaci spojitých a naopak. Pro velmi omezené situace, jako je házení kostky nebo experimenty s balíčky karet, výpočet pravděpodobnosti událostí je v zásadě enumerativní kombinatorika.

Teorie čísel

The Ulam spirála čísel s černými pixely prvočísla. Tento diagram naznačuje vzory v rozdělení prvočísel.

Teorie čísel se zabývá vlastnostmi čísel obecně, zejména celá čísla. Má aplikace pro kryptografie a dešifrování, zejména s ohledem na modulární aritmetika, diofantické rovnice, lineární a kvadratické kongruence, prvočísla a testování primality. Mezi další diskrétní aspekty teorie čísel patří geometrie čísel. v analytická teorie čísel, používají se také techniky spojité matematiky. Témata, která jdou nad rámec samostatných objektů, zahrnují transcendentální čísla, diofantická aproximace, p-adická analýza a funkční pole.

Algebraické struktury

Algebraické struktury vyskytují se jako diskrétní příklady i spojité příklady. Diskrétní algebry zahrnují: booleovská algebra použito v logické brány a programování; relační algebra použito v databáze; diskrétní a konečné verze skupiny, prsteny a pole jsou důležité v teorie algebraického kódování; oddělený poloskupiny a monoidy se objeví v teorii formální jazyky.

Počet konečných rozdílů, diskrétní počet nebo diskrétní analýza

A funkce definované na intervalu celá čísla se obvykle nazývá a sekvence. Sekvencí může být konečná sekvence ze zdroje dat nebo nekonečná sekvence z a diskrétní dynamický systém. Taková diskrétní funkce může být definována explicitně seznamem (pokud je její doména konečná) nebo vzorcem pro její obecný termín, nebo může být implicitně dána a relace opakování nebo rozdílová rovnice. Rozdílové rovnice jsou podobné diferenciální rovnice, ale vyměnit diferenciace tím, že vezmeme rozdíl mezi sousedními podmínkami; mohou být použity k aproximaci diferenciálních rovnic nebo (častěji) studovány samostatně. Mnoho otázek a metod týkajících se diferenciálních rovnic má protějšky diferenciálních rovnic. Například tam, kde jsou integrální transformace v harmonická analýza pro studium spojitých funkcí nebo analogových signálů existují diskrétní transformace pro diskrétní funkce nebo digitální signály. Stejně jako diskrétní metrika existují obecnější diskrétní nebo konečné metrické prostory a konečné topologické prostory.

Geometrie

Výpočetní geometrie platí počítač algoritmy k reprezentacím geometrický předměty.

Diskrétní geometrie a kombinatorická geometrie jsou o kombinatorických vlastnostech diskrétní sbírky geometrických objektů. Dlouhodobým tématem diskrétní geometrie je obklad letadla. Výpočtová geometrie aplikuje algoritmy na geometrické problémy.

Topologie

Ačkoli topologie je obor matematiky, který formalizuje a zevšeobecňuje intuitivní pojetí „kontinuální deformace“ objektů, vede k mnoha samostatným tématům; to lze částečně připsat zaměření na topologické invarianty, které samy o sobě obvykle mají diskrétní hodnoty. Viz kombinatorická topologie, teorie topologických grafů, topologická kombinatorika, výpočetní topologie, diskrétní topologický prostor, konečný topologický prostor, topologie (chemie).

Operační výzkum

PERT takovéto grafy poskytují techniku ​​řízení projektu založenou na teorie grafů.

Operační výzkum poskytuje techniky pro řešení praktických problémů ve strojírenství, podnikání a dalších oborech - problémy, jako je alokace zdrojů k maximalizaci zisku a plánování projektových činností s cílem minimalizovat riziko. Mezi techniky operačního výzkumu patří lineární programování a další oblasti optimalizace, teorie front, teorie plánování, a teorie sítí. Operační výzkum zahrnuje také souvislá témata jako např Markovův proces v nepřetržitém čase, nepřetržitý čas martingales, optimalizace procesu a kontinuální a hybridní teorie řízení.

Teorie her, teorie rozhodování, teorie užitečnosti, teorie sociální volby

Teorie rozhodování zabývá se identifikací hodnot, nejistot a dalších otázek relevantních v daném rozhodnutí, jeho racionality a výsledného optimálního rozhodnutí.

Teorie užitku jde o míry příbuzného hospodářský spokojenost nebo vhodnost spotřeby různých druhů zboží a služeb.

Teorie sociální volby je o hlasování. Přístup k hlasování je založen na logičtějším řešení teorie hlasování.

Herní teorie zabývá se situacemi, kdy úspěch závisí na volbě ostatních, což komplikuje výběr nejlepšího postupu. Existují dokonce nepřetržité hry, viz diferenciální hra. Témata zahrnují teorie dražby a spravedlivé rozdělení.

Diskretizace

Diskretizace se týká procesu převodu spojitých modelů a rovnic do diskrétních protějšků, často za účelem usnadnění výpočtů pomocí aproximací. Numerická analýza poskytuje důležitý příklad.

Diskrétní analogy spojité matematiky

V spojité matematice existuje mnoho konceptů, které mají diskrétní verze, například diskrétní počet, diskrétní rozdělení pravděpodobnosti, diskrétní Fourierovy transformace, diskrétní geometrie, diskrétní logaritmy, diskrétní diferenciální geometrie, diskrétní vnější počet, diskrétní Morseova teorie, rozdílové rovnice, diskrétní dynamické systémy, a diskrétní vektorové míry.

v aplikovaná matematika, diskrétní modelování je diskrétní analog kontinuální modelování. V diskrétním modelování se hodí diskrétní vzorce data. Běžnou metodou v této formě modelování je použití relace opakování.

v algebraická geometrie, koncept křivky lze rozšířit na diskrétní geometrie pomocí spektra z polynomiální kroužky přes konečná pole být modely afinní prostory přes toto pole, a nechat poddruhy nebo spektra jiných prstenů poskytují křivky, které leží v tomto prostoru. Přestože prostor, ve kterém se křivky objevují, má konečný počet bodů, křivky nejsou tolik sad bodů, jako analogie křivek v kontinuálním nastavení. Například každý bod formuláře ${displaystyle V (x-c) podmnožina operatorname {Spec} K [x] = mathbb {A} ^ {1}}$ pro ${displaystyle K}$ obor lze studovat buď jako ${displaystyle operatorname {Spec} K [x] / (x-c) cong operatorname {Spec} K}$, bod, nebo jako spektrum ${displaystyle operatorname {Spec} K [x] _ {(x-c)}}$ z místní kruh v (x-c), bod společně s okolím. Algebraické odrůdy mají také dobře definovaný pojem tečný prostor volal Zariski tečný prostor, díky čemuž je mnoho funkcí počtu použitelných i v konečných nastaveních.

Hybridní diskrétní a spojitá matematika

The kalkul časové stupnice je sjednocení teorie rozdílové rovnice s tím diferenciální rovnice, který má aplikace pro pole vyžadující simultánní modelování diskrétních a spojitých dat. Dalším způsobem modelování takové situace je pojem hybridní dynamické systémy.

Viz také

• Nástin diskrétní matematiky
• Cyberchase, show, která učí diskrétní matematiku pro děti

Reference

Další čtení

• Norman L. Biggs (2002-12-19). Diskrétní matematika. Oxford University Press. ISBN  978-0-19-850717-8.
• John Dwyer (2010). Úvod do diskrétní matematiky pro podnikání a výpočetní techniku. ISBN  978-1-907934-00-1.
• Susanna S. Epp (04.08.2010). Diskrétní matematika s aplikacemi. Thomson Brooks / Cole. ISBN  978-0-495-39132-6.
• Ronald Graham, Donald E. Knuth, Oren Patashnik, Konkrétní matematika.
• Ralph P. Grimaldi (2004). Diskrétní a kombinatorická matematika: Aplikovaný úvod. Addison Wesley. ISBN  978-0-201-72634-3.
• Donald E. Knuth (03.03.2011). Umění počítačového programování, Objemy 1-4a, krabicová sada. Addison-Wesley Professional. ISBN  978-0-321-75104-1.
• Jiří Matoušek; Jaroslav Nešetřil (1998). Diskrétní matematika. Oxford University Press. ISBN  978-0-19-850208-1.
• Obrenic, Bojana (2003-01-29). Procvičování problémů v diskrétní matematice. Prentice Hall. ISBN  978-0-13-045803-2.
• Kenneth H. Rosen; John G. Michaels (2000). Ruční kniha diskrétní a kombinatorické matematiky. CRC PressI LLC. ISBN  978-0-8493-0149-0.
• Kenneth H. Rosen (2007). Diskrétní matematika: a její aplikace. McGraw-Hill College. ISBN  978-0-07-288008-3.
• Andrew Simpson (2002). Diskrétní matematika příkladem. McGraw-Hill Incorporated. ISBN  978-0-07-709840-7.
• Veerarajan, T. (2007), Diskrétní matematika s teorií grafů a kombinatorikou, Tata Mcgraw Hill

externí odkazy

• Média související s Diskrétní matematika na Wikimedia Commons
• Diskrétní matematika v archivu matematiky utk.edu, který poskytuje odkazy na osnovy, výukové programy, programy atd.
• Iowa Central: Program elektrických technologií Diskrétní matematika pro Elektrotechnika.