Matematyka dyskretna - Discrete mathematics
Matematyka dyskretna to nauka o strukturach matematycznych, które są zasadniczo dyskretne, a nie ciągłe . W przeciwieństwie do liczb rzeczywistych, które mają właściwość zmieniania się „gładko”, obiekty badane w matematyce dyskretnej – takie jak liczby całkowite , wykresy i twierdzenia w logice – nie zmieniają się w ten sposób płynnie, lecz mają odrębne, oddzielone wartości. Matematyka dyskretna wyklucza zatem tematy z „matematyki ciągłej”, takie jak rachunek różniczkowy czy geometria euklidesowa . Obiekty dyskretne często mogą być wyliczane za pomocą liczb całkowitych. Bardziej formalnie, dyskretne matematyki scharakteryzowano jako gałąź matematyki dotyczących zestawów policzalnych (zestawów ograniczonych lub zestawy z tego samego liczności jak naturalne liczby). Jednak nie ma dokładnej definicji terminu „matematyka dyskretna”. Rzeczywiście, matematyka dyskretna jest opisana mniej przez to, co jest zawarte, a przez to, co jest wykluczone: stale zmieniające się ilości i powiązane pojęcia.
Zbiór obiektów badanych w matematyce dyskretnej może być skończony lub nieskończony. Termin „ matematyka skończona” jest czasami stosowany do części dziedziny matematyki dyskretnej, która zajmuje się zbiorami skończonymi, szczególnie w obszarach istotnych dla biznesu.
Badania nad matematyką dyskretną nasiliły się w drugiej połowie XX wieku, częściowo dzięki rozwojowi komputerów cyfrowych, które działają w dyskretnych krokach i przechowują dane w dyskretnych bitach. Pojęcia i zapisy z matematyki dyskretnej są przydatne w badaniu i opisywaniu obiektów i problemów w dziedzinach informatyki , takich jak algorytmy komputerowe , języki programowania , kryptografia , automatyczne dowodzenie twierdzeń i tworzenie oprogramowania . I odwrotnie, implementacje komputerowe mają duże znaczenie w zastosowaniu pomysłów z matematyki dyskretnej do rzeczywistych problemów, takich jak badania operacyjne .
Chociaż głównymi przedmiotami badań matematyki dyskretnej są przedmioty dyskretne, często stosuje się również metody analityczne z matematyki ciągłej.
W programach uniwersyteckich „Matematyka dyskretna” pojawiła się w latach 80., początkowo jako kurs wspomagający informatykę; jego zawartość była wówczas nieco chaotyczna. Program nauczania został następnie rozwinięty w połączeniu z wysiłkami ACM i MAA w kurs, który zasadniczo ma na celu rozwijanie dojrzałości matematycznej u studentów pierwszego roku; dlatego jest to obecnie warunek wstępny dla kierunków matematycznych również na niektórych uniwersytetach. Pojawiły się również niektóre podręczniki do matematyki dyskretnej dla szkół średnich. Na tym poziomie matematyka dyskretna jest czasami postrzegana jako kurs przygotowawczy, podobnie jak pod tym względem prerachunek .
Nagroda Fulkerson przyznawana jest za wybitne dokumenty w matematyki dyskretnej.
Wielkie wyzwania, przeszłość i teraźniejszość
Historia matematyki dyskretnej wiąże się z wieloma trudnymi problemami, które skupiają uwagę na obszarach tej dziedziny. W teorii grafów wiele badań było motywowanych próbami udowodnienia twierdzenia o czterech kolorach , po raz pierwszy sformułowanego w 1852 r., ale udowodnionego dopiero w 1976 r. (przez Kennetha Appela i Wolfganga Hakena, przy użyciu znacznej pomocy komputerowej).
W logice The Drugim problemem na David Hilbert listy „s otwartych problemów przedstawionych w 1900 roku było udowodnić, że aksjomaty z arytmetyki są spójne . Drugie twierdzenie Gödla o niezupełności , udowodnione w 1931 roku, pokazało, że nie jest to możliwe – przynajmniej nie w obrębie samej arytmetyki. Dziesiątym problemem Hilberta było ustalenie, czy dane wielomianowe równanie diofantyczne ze współczynnikami całkowitymi ma rozwiązanie całkowite. W 1970 roku Jurij Matiyasevich udowodnił, że nie da się tego zrobić .
Konieczność łamania niemieckich kodów w czasie II wojny światowej doprowadziła do postępów w kryptografii i informatyce teoretycznej , a pierwszy programowalny cyfrowy komputer elektroniczny został opracowany w angielskim Bletchley Park pod kierunkiem Alana Turinga i jego przełomowej pracy O liczbach obliczalnych. Jednocześnie wymagania wojskowe motywowały postęp w badaniach operacyjnych . Zimnej wojny oznaczał, że kryptografia pozostały ważne, z podstawowych osiągnięć, takich jak kryptografia klucza publicznego rozwijany w następnych dziesięcioleciach. Badania operacyjne pozostały ważnym narzędziem w zarządzaniu biznesem i projektami, a metoda ścieżki krytycznej została opracowana w latach 50. XX wieku. Przemysł telekomunikacyjny przyczynił się również do postępów w matematyce dyskretnej, zwłaszcza w teorii grafów i teorii informacji . Formalna weryfikacja twierdzeń logicznych była konieczna do tworzenia oprogramowania systemów krytycznych dla bezpieczeństwa , a postępy w automatycznym dowodzeniu twierdzeń były napędzane tą potrzebą.
Geometria obliczeniowa jest ważną częścią grafiki komputerowej, która jest wykorzystywana w nowoczesnych grach wideo i narzędziach komputerowego wspomagania projektowania .
Kilka dziedzin matematyki dyskretnej, w szczególności informatyka teoretyczna, teoria grafów i kombinatoryka , jest ważnych w rozwiązywaniu trudnych problemów bioinformatycznych związanych ze zrozumieniem drzewa życia .
Obecnie jednym z najbardziej znanych otwartych problemów w informatyce teoretycznej jest problem P = NP , który dotyczy relacji między klasami złożoności P i NP . Clay Mathematics Institute zaoferował $ 1 milion USD nagrodę dla pierwszego prawidłowego dowodu, wraz z nagrodami dla sześciu innych problemów matematycznych .
Tematy w matematyce dyskretnej
Informatyka teoretyczna
Informatyka teoretyczna obejmuje obszary matematyki dyskretnej związane z informatyką. W dużym stopniu czerpie z teorii grafów i logiki matematycznej . W zakres informatyki teoretycznej wchodzi badanie algorytmów i struktur danych. Obliczalność bada to, co można obliczyć w zasadzie i ma bliskie powiązania z logiką, podczas gdy złożoność bada czas, przestrzeń i inne zasoby wykorzystywane przez obliczenia. Teoria automatów i teoria języka formalnego są ściśle związane z obliczalnością. Do modelowania systemów komputerowych wykorzystuje się sieci Petriego i algebry procesów , a do analizy obwodów elektronicznych VLSI stosuje się metody matematyki dyskretnej . Geometria obliczeniowa stosuje algorytmy do problemów geometrycznych, podczas gdy komputerowa analiza obrazu stosuje je do reprezentacji obrazów. Informatyka teoretyczna obejmuje również badanie różnych ciągłych zagadnień obliczeniowych.
Teoria informacji
Teoria informacji obejmuje kwantyfikację informacji . Ściśle powiązana jest teoria kodowania, która służy do projektowania wydajnych i niezawodnych metod transmisji i przechowywania danych. Teoria informacji obejmuje również ciągłe zagadnienia takie jak: sygnały analogowe , analog kodowania , szyfrowania analogowego .
Logika
Logika to nauka o zasadach prawidłowego rozumowania i wnioskowania , jak również o spójności , rzetelności i kompletności . Na przykład w większości systemów logiki (ale nie w logice intuicjonistycznej ) prawo Peirce'a ((( P → Q )→ P )→ P ) jest twierdzeniem. W przypadku logiki klasycznej można to łatwo zweryfikować za pomocą tabeli prawdy . Badanie dowodu matematycznego jest szczególnie ważne w logice i ma zastosowanie do automatycznego dowodzenia twierdzeń i formalnej weryfikacji oprogramowania.
Wzory logiczne są strukturami dyskretnymi, podobnie jak dowody , które tworzą skończone drzewa lub, bardziej ogólnie, skierowane acykliczne struktury grafowe (z każdym krokiem wnioskowania łączącym jedną lub więcej gałęzi przesłanki, aby dać pojedynczy wniosek). Wartości prawdziwości formuł logicznych zwykle tworzą zbiór skończony, na ogół ograniczony do dwóch wartości: prawda i fałsz , ale logika może być również wartością ciągłą, np . logika rozmyta . Badano również pojęcia takie jak nieskończone drzewa dowodowe lub nieskończone drzewa derywacyjne, np . logika nieskończoności .
Teoria mnogości
Teoria mnogości to dział matematyki zajmujący się badaniem zbiorów , które są zbiorami obiektów, takich jak {niebieski, biały, czerwony} lub (nieskończony) zbiór wszystkich liczb pierwszych . Zbiory częściowo uporządkowane i z innymi relacjami mają zastosowanie w kilku obszarach.
W matematyce dyskretnej główny nacisk kładzie się na zbiory policzalne (w tym zbiory skończone ). Początek teorii mnogości jako gałęzi matematyki wyznacza zwykle praca Georga Cantora rozróżniająca różne rodzaje zbiorów nieskończonych , motywowana badaniem szeregów trygonometrycznych , a dalszy rozwój teorii zbiorów nieskończonych wykracza poza zakres dyskretnych . matematyka. Rzeczywiście, współczesne prace nad opisową teorią mnogości szeroko wykorzystują tradycyjną matematykę ciągłą.
Kombinatoryka
Kombinatoryka bada sposób, w jaki dyskretne struktury mogą być łączone lub układane. Kombinatoryka enumeratywna koncentruje się na liczeniu pewnych obiektów kombinatorycznych – np. sposób dwunastokrotny zapewnia ujednoliconą strukturę do liczenia permutacji , kombinacji i podziałów . Kombinatoryka analityczna dotyczy wyliczania (czyli wyznaczania liczby) struktur kombinatorycznych przy użyciu narzędzi analizy zespolonej i teorii prawdopodobieństwa . W przeciwieństwie do kombinatoryki enumeratywnej, która do opisu wyników używa jawnych formuł kombinatorycznych i funkcji generujących , kombinatoryka analityczna ma na celu uzyskanie formuł asymptotycznych . Teoria projektu to nauka o projektach kombinatorycznych , które są zbiorami podzbiorów o określonych właściwościach przecięcia . Teoria partycji zajmuje się różnymi zagadnieniami wyliczeniowymi i asymptotycznymi związanymi z podziałami całkowitymi i jest ściśle powiązana z szeregami q , funkcjami specjalnymi i wielomianami ortogonalnymi . Pierwotnie część teorii i analizy liczb , teoria podziału jest obecnie uważana za część kombinatoryki lub niezależną dziedzinę. Teoria porządku to nauka o zbiorach częściowo uporządkowanych , zarówno skończonych, jak i nieskończonych.
Teoria grafów
Teoria grafów, nauka o grafach i sieciach , jest często uważana za część kombinatoryki, ale rozrosła się na tyle szeroko i wyraźnie, z własnymi problemami, że można ją uważać za przedmiot sam w sobie. Wykresy są jednym z podstawowych przedmiotów badań matematyki dyskretnej. Są jednymi z najbardziej wszechobecnych modeli konstrukcji zarówno naturalnych, jak i stworzonych przez człowieka. Potrafią modelować wiele typów relacji i dynamiki procesów w systemach fizycznych, biologicznych i społecznych. W informatyce mogą reprezentować sieci komunikacyjne, organizację danych, urządzenia obliczeniowe, przepływ obliczeń itp. W matematyce są przydatne w geometrii i niektórych częściach topologii , np . teorii węzłów . Algebraiczna teoria grafów ma ścisłe powiązania z teorią grup. Istnieją również wykresy ciągłe ; jednak w przeważającej części badania nad teorią grafów mieszczą się w dziedzinie matematyki dyskretnej.
Prawdopodobieństwo
Dyskretna teoria prawdopodobieństwa zajmuje się zdarzeniami zachodzącymi w policzalnych przestrzeniach próbek . Na przykład obserwacje liczebne, takie jak liczebność ptaków w stadach, zawierają tylko wartości liczb naturalnych {0, 1, 2, ...}. Z drugiej strony, ciągłe obserwacje, takie jak wagi ptaków, zawierają wartości liczb rzeczywistych i są zazwyczaj modelowane przez ciągły rozkład prawdopodobieństwa, taki jak normalny . Dyskretne rozkłady prawdopodobieństwa mogą być używane do przybliżania ciągłych rozkładów i odwrotnie. W wysoce ograniczonych sytuacjach, takich jak rzucanie kostką lub eksperymenty z taliami kart , obliczanie prawdopodobieństwa zdarzeń jest w zasadzie kombinatoryką enumeratywną .
Teoria liczb
Teoria liczb dotyczy ogólnie własności liczb, w szczególności liczb całkowitych . Ma zastosowanie w kryptografii i kryptoanalizie , szczególnie w odniesieniu do arytmetyki modularnej , równań diofantycznych , kongruencji liniowej i kwadratowej, liczb pierwszych i testowania pierwszości . Inne dyskretne aspekty teorii liczb obejmują geometrię liczb . W analitycznej teorii liczb stosuje się również techniki z matematyki ciągłej. Tematy wykraczające poza obiekty dyskretne obejmują liczby transcendentalne , przybliżenie diofantyczne , analizę p-adyczną i pola funkcyjne .
Struktury algebraiczne
Struktury algebraiczne występują zarówno jako przykłady dyskretne, jak i przykłady ciągłe. Algebry dyskretne obejmują: algebra Boole'a wykorzystywana w bramkach logicznych i programowaniu; algebra relacyjna stosowana w bazach danych ; dyskretne i skończone wersje grup , pierścieni i pól są ważne w algebraicznej teorii kodowania ; W teorii języków formalnych pojawiają się półgrupy i monoidy dyskretne .
Rachunek różnic skończonych, rachunek różnic dyskretnych lub analiza dyskretna
Funkcja określona na przedziale z liczb całkowitych jest zwykle nazywana jest sekwencja . Sekwencja może być skończoną sekwencją ze źródła danych lub nieskończoną sekwencją z dyskretnego systemu dynamicznego . Taka dyskretna funkcja może być zdefiniowana wprost przez listę (jeżeli jej dziedzina jest skończona) lub przez wzór na jej ogólny termin, lub może być dana niejawnie przez relację rekurencyjną lub równanie różnicowe . Równania różnicowe są podobne do równań różniczkowych , ale zastępują różnicowanie , biorąc różnicę między sąsiednimi wyrazami; mogą być używane do przybliżania równań różniczkowych lub (częściej) badane samodzielnie. Wiele pytań i metod dotyczących równań różniczkowych ma odpowiedniki dla równań różnicowych. Na przykład, gdy występują transformacje całkowe w analizie harmonicznej do badania funkcji ciągłych lub sygnałów analogowych, istnieją transformacje dyskretne dla funkcji dyskretnych lub sygnałów cyfrowych. Oprócz metryki dyskretnej istnieją bardziej ogólne dyskretne lub skończone przestrzenie metryczne oraz skończone przestrzenie topologiczne .
Geometria
Geometria dyskretna i geometria kombinatoryczna dotyczą właściwości kombinatorycznych dyskretnych kolekcji obiektów geometrycznych. Od dawna tematem w geometrii dyskretnej jest kafelkowanie płaszczyzny . Geometria obliczeniowa stosuje algorytmy do problemów geometrycznych.
Topologia
Chociaż topologia jest dziedziną matematyki, która formalizuje i uogólnia intuicyjne pojęcie „ciągłej deformacji” obiektów, daje początek wielu odrębnym tematom; można to częściowo przypisać skupieniu się na niezmiennikach topologicznych , które same zwykle przyjmują wartości dyskretne. Patrz kombinatorycznej topologii , topologiczne teorii wykres , kombinatoryki topologiczne , topologii obliczeniowej , przestrzeni dyskretnej topologiczne , skończoną przestrzeń topologiczną , topologii (chemiczne) .
Badania operacyjne
Badania operacyjne dostarczają technik rozwiązywania praktycznych problemów w inżynierii, biznesie i innych dziedzinach — problemów, takich jak alokacja zasobów w celu maksymalizacji zysku i planowanie działań projektowych w celu zminimalizowania ryzyka. Badania operacyjne obejmują techniki programowania liniowego i innych obszarów optymalizacji , teoria kolejek , teorii planowania i teorii sieci . Badania operacyjne obejmują również zagadnienia ciągłe, takie jak ciągły proces Markowa , martyngały czasu ciągłego , optymalizacja procesów oraz teoria sterowania ciągłego i hybrydowego .
Teoria gier, teoria decyzji, teoria użyteczności, teoria wyboru społecznego
| Współpracować | Wada | |
| Współpracować | -1, -1 | -10, 0 |
| Wada | 0, -10 | -5, -5 |
| Macierz wypłat dla dylematu więźnia , typowy przykład w teorii gier . Jeden gracz wybiera rząd, drugi kolumnę; otrzymana para daje im wypłaty | ||
Teoria decyzji zajmuje się identyfikacją wartości, niepewności i innych kwestii istotnych dla danej decyzji, jej racjonalności i wynikającej z niej optymalnej decyzji.
Teoria użyteczności dotyczy mierników względnego zadowolenia ekonomicznego z konsumpcji różnych dóbr i usług.
Teoria wyboru społecznego dotyczy głosowania . Bardziej opartym na łamigłówkach podejściem do głosowania jest teoria głosowania .
Teoria gier dotyczy sytuacji, w których sukces zależy od wyborów innych, co sprawia, że wybór najlepszego sposobu działania jest bardziej złożony. Są nawet gry ciągłe, patrz gra różnicowa . Tematy obejmują teorię aukcji i podział sprawiedliwy .
Dyskretyzacja
Dyskretyzacja dotyczy procesu przenoszenia modeli ciągłych i równań na dyskretne odpowiedniki, często w celu ułatwienia obliczeń za pomocą przybliżeń. Ważnym przykładem jest analiza numeryczna .
Dyskretne analogi matematyki ciągłej
Istnieje wiele koncepcji w sposób ciągły matematyki które wersje dawek, takich jak dyskretną rachunku , dyskretnych rozkładów prawdopodobieństwa , dyskretnych transformat Fouriera , dyskretna geometrii , dyskretnych logarytmów , dyskretnej geometrii różnicowego , dyskretnej zewnętrznej rachunku , dyskretnej teorii Morse , równania różnicowe , oddzielnych systemów dynamicznych , i dyskretne miary wektorowe .
W stosowanych matematyki , dyskretne modelowania jest dyskretnych Analog ciągłego modelowania . W modelowaniu dyskretnym formuły dyskretne są dopasowywane do danych . Powszechną metodą w tej formie modelowania jest użycie relacji rekurencyjnej .
W geometrii algebraicznej , pojęcie krzywej może być przedłużony do dyskretnych geometrii biorąc widm z wielomianu pierścienie ponad pól skończonych być modele przestrzeń afiniczna ponad tej dziedzinie, i pozwalając subvarieties lub widma innymi pierścieniami zapewniają krzywe, które leżą w tę przestrzeń. Chociaż przestrzeń, w której pojawiają się krzywe, ma skończoną liczbę punktów, krzywe są nie tyle zbiorami punktów, co analogami krzywych w ustawieniach ciągłych. Na przykład, każdy punkt w postaci do pola mogą być badane zarówno jako , temperaturę lub jako widmo w lokalnym w pierścieniu (XC) , temperaturę wraz z okolicy wokół niego. Rozmaitości algebraiczne mają również dobrze zdefiniowane pojęcie przestrzeni stycznej zwanej przestrzenią styczną Zariskiego , dzięki czemu wiele cech rachunku różniczkowego można zastosować nawet w skończonych układach.
![V(xc)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![\operatorname {Spec} K[x]/(xc)\cong \operatorname {Spec} K](https://wikimedia.org/api/rest_v1/media/math/render/svg/80cc3220b7c86e6d0862f1bcf3fbac3ffc0191a7)
![\operatorname {Spec} K[x]_{(xc)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e6e66e203e1805ec5b90fa25d9f0c817f28dd7)
Hybrydowa matematyka dyskretna i ciągła
Rachunek skala czasu jest ujednolicenie teorii równania różnicowe z tym z równań różniczkowych , co ma zastosowania w dziedzinach wymagających jednoczesne modelowanie oddzielnych i ciągłych danych. Innym sposobem modelowania takiej sytuacji jest pojęcie hybrydowych układów dynamicznych .
Zobacz też
- Zarys matematyki dyskretnej
- Cyberchase , program, który uczy dzieci matematyki dyskretnej
Bibliografia
Dalsza lektura
- Normana L. Biggsa (2002-12-19). Matematyka dyskretna . Oxford University Press. Numer ISBN 978-0-19-850717-8.
- Johna Dwyera (2010). Wprowadzenie do matematyki dyskretnej dla biznesu i informatyki . Numer ISBN 978-1-907934-00-1.
- Susanna S. Epp (2010-08-04). Matematyka dyskretna z aplikacjami . Thomson Brooks/Cole. Numer ISBN 978-0-495-39132-6.
- Ronald Graham , Donald E. Knuth , Oren Patashnik , Matematyka konkretna .
- Ralph P. Grimaldi (2004). Matematyka dyskretna i kombinatoryczna: wprowadzenie stosowane . Addisona Wesleya. Numer ISBN 978-0-201-72634-3.
- Donalda E. Knutha (03.03.2011). Sztuka programowania komputerowego , tomy 1-4a zestaw pudełkowy . Addison-Wesley Profesjonalista. Numer ISBN 978-0-321-75104-1.
- Jiří Matoušek; Jaroslav Nešetřil (1998). Matematyka dyskretna . Oxford University Press. Numer ISBN 978-0-19-850208-1.
- Obrenic, Bojana (2003-01-29). Ćwicz problemy w matematyce dyskretnej . Sala Prezydencka. Numer ISBN 978-0-13-045803-2.
- Kennetha H. Rosena; Johna G. Michaelsa (2000). Podręcznik matematyki dyskretnej i kombinatorycznej . CRC PressI Sp. Numer ISBN 978-0-8493-0149-0.
- Kennetha H. Rosena (2007). Matematyka dyskretna: i jej zastosowania . McGraw-Hill College. Numer ISBN 978-0-07-288008-3.
- Andrew Simpson (2002). Matematyka dyskretna na przykładzie . Spółka McGraw-Hill. Numer ISBN 978-0-07-709840-7.
Zewnętrzne linki
-
Multimedia związane z matematyką dyskretną w Wikimedia Commons - Matematyka dyskretna w Archiwum Matematyki utk.edu, gdzie znajdują się linki do programów nauczania, samouczków, programów itp.
- Iowa Central: Electrical Technologies Program Matematyka dyskretna dla elektrotechniki .
