Algorithmen Und Komplexit�Tstheorie Ebook Tooltip Ebooks kunnen worden gelezen op uw computer en op daarvoor geschikte e-readers.
Afbeeldingen
Artikel vergelijken
Auteur:
Christoph Vogt
Kai Lingemann
- Duits
- E-book
- 9783638112574
- 10 februari 2002
- 178 pagina's
- Adobe ePub
Samenvatting
Dieses Dokument hat das Ziel, den Leser bei der Vorbereitung für die Informatik-Diplomprüfung zu unterstützen.
Dieses Skript basiert auf Literatur und Vorlesungen. Die Vorlesungen wurden an der Universität Bonn von Prof. Dr. Lengauer gehalten. Die Basis für den größten Teil der Vorlesungen bilden dabei ein neues Werk von Mehlhorn und Näher sowie Werke von Reischuk und Papadimitriou.
Inhaltsverzeichnis:
I Algorithmen
1 Graphen
1.1 Grundlegende Notationen
1.2 Speicherung von Graphen
1.3 Graphenisomorphie
1.4 Planarität
1.5 Büme
1.6 Zusammenhang
1.7 Depth-First-Search
1.8 kürzeste Wege in Graphen
1.9 Minimale Spannbäume
1.10 Matching in Graphen
1.11 Netzwerkflüsse
2 Geometrie
2.1 Konvexe Hülle
2.2 Triangulierungen
2.3 Die Delaunay-Triangulierung
2.4 Segmentschnitte
II Komplexitätstheorie
3 Einleitung
4 Turingmaschinen
4.1 Allgemeines
4.2 Turingmaschinen als Algorithmen
4.3 Linearer Speedup
4.4 Aufwand beim Akzeptieren der Palindromsprachen
4.5 Die Registermaschine (Random Access Machine)
4.6 Nichtdeterminismus
5 Unentscheidbarkeit
5.1 Halteproblem
5.2 Abgeschlossenheit
5.3 Rekursive Trennbarkeit
6 Aussagenlogik
6.1 Erfüllbarkeit & Wahrheit
6.2 Logik{Funktionen
7 Logik erster Stufe
7.1 Syntax
7.2 Semantik
7.3 Modelle für die Zahlentheorie
7.4 Gültige Sätze
7.5 Konsistenz der Logik erster Ordnung
8 Unentscheidbarkeit in der Logik
8.1 Berechnung als zahlentheoretisches Konzept
9 Beziehungen zwischen Komplexitätsklassen
9.1 Komplexitätsklassen
9.2 Hierarchiesätze
9.3 Erreichbarkeitsmethode
10 Reduktion und Vollständigkeit
10.1 Reduktion
10.2 Vollständigkeit
10.3 Charakterisierung mittels Logik
11 NP-vollständige Probleme
11.1 Varianten von SAT
11.2 Varianten von 2SAT
11.3 Graphenprobleme
11.4 Zahlenprobleme
12 coNP und Funktionsprobleme
12.1 PRIMES
12.2 Function Problems
13 Randomisierte Berechnungen
13.1 Randomisierte Algorithmen
13.2 Randomisierte Komplexitätsklassen
13.3 Zufallsgeneratoren
13.4 Schaltkreiskomplexität
14 Kryptographie
14.1 Public Key-Kryptographie
14.2 Kryptographie und Komplexität
14.3 Interaktives Beweisen
14.4 Zero Knowledge
15 Approximierbarkeit
15.1 Approximationsalgorithmen
15.2 Polyzeit{Approximationsschema
15.3 Vollständigkeit bei Approximationsalgorithmen
16 P vs. NP
16.1 Was ist zwischen P und NPC?
16.2 Beweise für P!=NP?
17 Parallelität
17.1 Beispiel-Algorithmen
17.2 Prä x-Summen-Berechnung
17.3 Parallele Maschinenmodelle
17.4 Die Klasse NC
18 Logarithmischer Platzverbrauch
18.1 L=NL?
18.2 Alternierung
19 Polynomielle Hierarchie
Dieses Skript basiert auf Literatur und Vorlesungen. Die Vorlesungen wurden an der Universität Bonn von Prof. Dr. Lengauer gehalten. Die Basis für den größten Teil der Vorlesungen bilden dabei ein neues Werk von Mehlhorn und Näher sowie Werke von Reischuk und Papadimitriou.
Inhaltsverzeichnis:
I Algorithmen
1 Graphen
1.1 Grundlegende Notationen
1.2 Speicherung von Graphen
1.3 Graphenisomorphie
1.4 Planarität
1.5 Büme
1.6 Zusammenhang
1.7 Depth-First-Search
1.8 kürzeste Wege in Graphen
1.9 Minimale Spannbäume
1.10 Matching in Graphen
1.11 Netzwerkflüsse
2 Geometrie
2.1 Konvexe Hülle
2.2 Triangulierungen
2.3 Die Delaunay-Triangulierung
2.4 Segmentschnitte
II Komplexitätstheorie
3 Einleitung
4 Turingmaschinen
4.1 Allgemeines
4.2 Turingmaschinen als Algorithmen
4.3 Linearer Speedup
4.4 Aufwand beim Akzeptieren der Palindromsprachen
4.5 Die Registermaschine (Random Access Machine)
4.6 Nichtdeterminismus
5 Unentscheidbarkeit
5.1 Halteproblem
5.2 Abgeschlossenheit
5.3 Rekursive Trennbarkeit
6 Aussagenlogik
6.1 Erfüllbarkeit & Wahrheit
6.2 Logik{Funktionen
7 Logik erster Stufe
7.1 Syntax
7.2 Semantik
7.3 Modelle für die Zahlentheorie
7.4 Gültige Sätze
7.5 Konsistenz der Logik erster Ordnung
8 Unentscheidbarkeit in der Logik
8.1 Berechnung als zahlentheoretisches Konzept
9 Beziehungen zwischen Komplexitätsklassen
9.1 Komplexitätsklassen
9.2 Hierarchiesätze
9.3 Erreichbarkeitsmethode
10 Reduktion und Vollständigkeit
10.1 Reduktion
10.2 Vollständigkeit
10.3 Charakterisierung mittels Logik
11 NP-vollständige Probleme
11.1 Varianten von SAT
11.2 Varianten von 2SAT
11.3 Graphenprobleme
11.4 Zahlenprobleme
12 coNP und Funktionsprobleme
12.1 PRIMES
12.2 Function Problems
13 Randomisierte Berechnungen
13.1 Randomisierte Algorithmen
13.2 Randomisierte Komplexitätsklassen
13.3 Zufallsgeneratoren
13.4 Schaltkreiskomplexität
14 Kryptographie
14.1 Public Key-Kryptographie
14.2 Kryptographie und Komplexität
14.3 Interaktives Beweisen
14.4 Zero Knowledge
15 Approximierbarkeit
15.1 Approximationsalgorithmen
15.2 Polyzeit{Approximationsschema
15.3 Vollständigkeit bei Approximationsalgorithmen
16 P vs. NP
16.1 Was ist zwischen P und NPC?
16.2 Beweise für P!=NP?
17 Parallelität
17.1 Beispiel-Algorithmen
17.2 Prä x-Summen-Berechnung
17.3 Parallele Maschinenmodelle
17.4 Die Klasse NC
18 Logarithmischer Platzverbrauch
18.1 L=NL?
18.2 Alternierung
19 Polynomielle Hierarchie
Productspecificaties
Wij vonden geen specificaties voor jouw zoekopdracht '{SEARCH}'.
Inhoud
- Taal
- de
- Bindwijze
- E-book
- Oorspronkelijke releasedatum
- 10 februari 2002
- Aantal pagina's
- 178
- Ebook Formaat
- Adobe ePub
- Illustraties
- Nee
Betrokkenen
- Hoofdauteur
- Christoph Vogt
- Tweede Auteur
- Kai Lingemann
- Hoofduitgeverij
- Grin Verlag
Lees mogelijkheden
- Lees dit ebook op
- Android (smartphone en tablet) | Kobo e-reader | Desktop (Mac en Windows) | iOS (smartphone en tablet) | Windows (smartphone en tablet)
Overige kenmerken
- Editie
- 1
- Extra groot lettertype
- Nee
- Studieboek
- Ja
EAN
- EAN
- 9783638112574
Je vindt dit artikel in
Kies gewenste uitvoering
Bindwijze
: E-book
Prijsinformatie en bestellen
De prijs van dit product is 32 euro en 99 cent.
Direct beschikbaar
Verkoop door bol
- E-book is direct beschikbaar na aankoop
- E-books lezen is voordelig
- Dag en nacht klantenservice
- Veilig betalen
Houd er rekening mee dat je downloadartikelen niet kunt annuleren of retourneren. Bij nog niet verschenen producten kun je tot de verschijningsdatum annuleren.
Zie ook de retourvoorwaarden
Rapporteer dit artikel
Je wilt melding doen van illegale inhoud over dit artikel:
- Ik wil melding doen als klant
- Ik wil melding doen als autoriteit of trusted flagger
- Ik wil melding doen als partner
- Ik wil melding doen als merkhouder
Geen klant, autoriteit, trusted flagger, merkhouder of partner? Gebruik dan onderstaande link om melding te doen.