Kapitel 12 Epilog

Kapitel 12
Epilog
Liste der 100 wichtigsten mathematischen Sätze
Diskrete Mathematik
Networks and flows
Discrete and computational geometry
Discrete optimization
Kapitel 12 “Epilog” – p. 1/10
Liste der 100 wichtigsten mathematischen Sätze
Auf einer Mathematik-Tagung 1999 wurde eine Liste der 100 wichtigsten mathematischen
Sätze publiziert: http://pirate.shu.edu/~kahlnath/Top100.html. Kriterien: ”the place
the theorem holds in the literature, the quality of the proof, and the unexpectedness of the
result”.
√
1. 2 ist irrational (Kapitel 2 ”Beweistechniken”)
3. Alle rationalen Zahlen Q sind abzählbar unendlich (Cantors erstes Diagonalargument;
Kapitel 3 ”Mengenlehre”)
5. Anzahl Primzahlen kleiner gleich n ist ungefähr n/ ln n (Kapitel 8 ”Zahlentheorie and
Arithmetik”)
10. Euler-Theorem (Kapitel 8 ”Zahlentheorie and Arithmetik”)
11. Es gibt unendlich viele Primzahlen (Kapitel 2 ”Beweistechniken”)
22. Menge [0, 1) ist überabzählbar unendlich (Cantors 2. Diagonalargument; Kapitel 3
”Mengenlehre”)
32. Vierfarbensatz (Kapitel 9 ”Graphentheorie”)
54. Konigsberg Brückenproblem (Kapitel 9 ”Graphentheorie”)
69. Der Euklidische Algorithmus ggT (Kapitel 8 ”Zahlentheorie and Arithmetik”)
74. Das mathematische Induktionsprizip (Kapitel 2 ”Beweistechniken”)
80. Fundamentalsatz der Arithmetik (Kapitel 2 ”Beweistechniken”)
88. Derangement-Zahlen Dn (Kapitel 3 ”Mengenlehre”)
Kapitel 12 “Epilog” – p. 2/10
Diskrete Mathematik
K.H. Rosen, Handbook of Discrete and Combinatorial Mathematics, 2000
Foundations (logic, set theory,
functions and relations, proof
techniques, etc.)
Counting methods
Sequences
Number theory
Coding theory and cryptology
Algebraic structures
Linear algebra
Discrete probability
Networks and flows
Partially ordered sets
Combinatorial designs
Graph theory
Discrete and computational
geometry
Trees
Discrete optimization
Theoretical computer science
Information structures
Kapitel 12 “Epilog” – p. 3/10
Networks and flows
Kürzeste Wege:
Gegeben sind ein (Di)Graph G = (V, E) und eine Gewichtsfunktion w : E → R.
Sei u = v0 , v1 , v2 , . . . , vn = v ein Pfad in G. Die Länge dieses Pfades ist
n−1
X
w(vi , vi+1 )
i=0
d(u, v): Länge eines kürzesten Pfades von u nach v.
Problemstellungen:
Gegeben u, v ∈ V , berechne d(u, v).
Gegeben u ∈ V , berechne für alle v ∈ V die Länge d(u, v) (single
source shortest path).
Berechne für alle (u, v) ∈ V 2 die kürzeste Entfernung d(u, v) (all pairs
shortest path).
Kapitel 12 “Epilog” – p. 4/10
Discrete and computational geometry
Nearest neighbor search:
Let P be a finite set of points in a metric space. A point q ∈ P is a nearest
neighbor of p ∈ P , if no point of P is closer to p than q.
Nearest-Neighbor Klassifikator gehört zu den einfachsten und populärsten Klassifikatoren in der statistischen Mustererkennung. Effiziente Nearest-NeighborSuche bildet die Grundlage dafür.
Kapitel 12 “Epilog” – p. 5/10
Exkurs: Mustererkennung (Musterklassifikation)
Ein unbekanntes Muster einer Klasse Ck aus N möglichen Klassen
Ci , 1 ≤ i ≤ N , zuordnen
Es ist möglich, ein Muster zurückzuweisen, d.h. einer (N + 1)ten Klasse
C0 , der Rückweisungsklasse, zuzuordnen.
W
W
S
S
1
1
4
4
M
ME
E
E
W
S
1
4
M
E
⇓
⇓
⇓
⇓
⇓
⇓
C1
C2
C3
C4
C5
C6
Ist ein Muster nicht zuverlässig klassifizierbar, wird es
entweder zurückgewiesen, d.h. nach C0 klassifiziert,
oder es werden mehrere Alternativen ausgegeben, d.h. nach
{Ck1 , Ck2 , . . .} klassifiziert.
Kapitel 12 “Epilog” – p. 6/10
Exkurs: Mustererkennung (Musterklassifikation)
Anwendungen:
Biometrie (Personenidentifikation und -verifikation)
Gesicht, Fingerabdruck, Unterschrift, Iris, Handgeometrie, Palmprint,
Ohrgeometrie, Gangart, etc.)
Intelligente Benutzer-Schnittstelle (Gestik, Lippenlesen, etc.)
Schrifterkennung (OCR; zählt zu den größten Erfolgen der
Mustererkennung)
Industrielle Qualitätskontrolle
Medizinische Diagnostik
Automatische Auskunftssysteme (Sprachsignale; z.B. Fahrplan,
Musiksuche)
Prognose von Börsenentwicklung
Detektion von Doppelpublikationen, abgeschriebenen Programmen, etc.
Kapitel 12 “Epilog” – p. 7/10
Exkurs: Statistische Mustererkennung
Repräsentation von Mustern im Merkmalsraum F
Intuitive Merkmale
Unterscheidung Äpfel/Orangen (links): Verhältnis von Grün- und
Rot-Komponente (F = ℜ); gilt allerdings nicht für Situation rechts.
Komplexe Merkmale
Kieselalge (diatom), > 15000 Typen (Klassen), Anwendung in Biologie,
Klimaforschung, Gerichtsmedizin. Merkmale: Konturform + Textur.
Kapitel 12 “Epilog” – p. 8/10
Exkurs: Statistische Mustererkennung
Darstellung des Musters:
Merkmalvektor (x1 , . . . , xn ) ∈ ℜn .
Klassifikation:
Annahme: verschiedene Klassen nehmen einen kompakten Teil von ℜn
ein; Klassengrenzen durch Trennfunktionen definiert (Training/Lernen
anhand einer Stichprobe).
Nearest-Neighbor Klassifikator:
Für jede Musterklasse Ci , 1 ≤ i ≤ N , genau ein (repräsentativer) Prototyp Zi
gegeben.
Für ein unbekanntes Muster x gilt die Klassifikationsregel:
k = arg min { d(x, Zi ) | 1 ≤ i ≤ N } =⇒ x ∈ Ck
i
Ordne x der Klasse Ck zu, zu welcher der nächste Nachbar Zk im Merkmalsraum
gehört. Man weist x zurück, falls kein eindeutiges Minimum unter d(x, Zi )
existiert oder das eindeutige Minimum zu groß ist.
Kapitel 12 “Epilog” – p. 9/10
Discrete optimization
Die Lineare Optimierung oder Lineare Programmierung ist eines der Hauptverfahren des
Operations Research und beschäftigt sich mit der Optimierung linearer Zielfunktionen über
einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist.
Bei einem linearen Programm (LP) sind eine Matrix A ∈ Rm,n und zwei Vektoren b ∈ Rm
und c ∈ Rn gegeben. Eine zulässige Lösung ist ein Vektor x ∈ Rn mit nichtnegativen
Einträgen, der die linearen Bedingungen
a11 x1
+...
+a1n xn
a21 x1
.
..
+...
.
..
+a2n xn
.
..
am1 x1
+...
+amn xn
≤
b1
≤
b2
.
..
≤
bm
erfüllt. Ziel ist es, unter allen zulässigen Vektoren x einen zu finden, der das Skalarprodukt
c · x = c1 x1 + . . . + cn xn
minimiert/maximiert. Dieses Optimierungsproblem in der sogenannten Standardform wird
oft abkürzend als
max{c · x | Ax ≤ b, x ≥ 0}
geschrieben, wobei die Bedingungen Ax ≤ b und x ≥ 0 komponentenweise zu verstehen sind.
Kapitel 12 “Epilog” – p. 10/10

Download Report