Kurt Mehlhorn

Die Eine-Million-Dollar-Frage

  • PRO
  • 2h 40 min
  • German
  • L'informatique
  • 59
  • avec certificat

Worum geht es im Kurs?

Die Eine-Million-Dollar-Frage oder "Welche Probleme haben effiziente Algorithmen?" oder "Ist das Finden einer Lösung schwerer als das Überprüfen einer Lösung?"

Sie lösen vielleicht manchmal Sudokus. Dabei muss man nach gewissen Regeln die Zahlen 1 bis 9 in ein Spielfeld der Größe 9 mal 9 eintragen. Ich habe schon Stunden mit der Lösung eines Sudokus zugebracht. Jedes Kind in der Grundschule kann überprüfen, ob ein ausgefülltes Sudoku die Regeln erfüllt. Unsere Lebenserfahrung sagt uns, dass bei Sudokus Lösen ganz sicher schwerer ist als Überprüfen.

Die Informatik kennt auch viele Probleme, bei denen man unter einer Vielzahl von Möglichkeiten die richtige finden muss. Denken Sie an ein Logistikunternehmen, das an viele Betriebe liefern soll und die billigste Reihenfolge zum Anfahren der Betriebe bestimmen will. Dieses Problem heißt das Traveling Salesman Problem. Es ist dafür kein effizienter Algorithmus bekannt. Man kann aber für eine Reihenfolge ganz leicht überprüfen, ob sie eine vorgegebene Länge nicht überschreitet. Ob es für das Traveling Salesman Problem einen effizienten Algorithmus gibt, ist eine tiefe Frage, für deren Lösung die Clay-Foundation ein Preisgeld von einer Million Dollar ausgesetzt hat.

Inhalte

  1. Die Ziele von Theorie

  2. Algorithmisch unentscheidbare Probleme

  3. Die Eine-Million-Dollar-Frage

    1. Die Klassen P und NP
    2. Das Erfüllbarkeitsproblem der Aussagenlogik
    3. Weitere Probleme in NP
    4. Genaue Definition der Klasse NP
    5. Der Satz von Cook und Levin: P = NP genau dann, wenn SAT in P
    6. Der Satz von Karp
    7. Eine Reduktion

  4. Was wäre wenn...

    1. ... P ungleich NP wäre und man es beweisen könnte?
    2. ... P gleich NP wäre und man es beweisen könnte?

  5. Ansätze zur Lösung NP-vollständiger Probleme

Bestandteile des Kurses

  1. Videos
  2. Folien
  3. Übungen mit Lösungen
  4. Logbuchaufgaben
  5. Zertifikat

Danksagung

Ich danke meinen (ehemaligen und aktuellen) Mitarbeitern, mit deren Hilfe ich die Vorlesung Ideen und Konzepte der Informatik an der Universität des Saarlandes entwickelt habe:

Dr. Konstantinos Panagiotou, Dr. Adrian Neumann, Dr. Antonios Antoniadis, Dr. Corinna Coupette und Angelina Mansion.

Dieser Kurs und die gesamte Kursreihe bauen auf dieser Vorlesung auf.

Kursinhalt

Chapitre 1
Einführung und Übersicht
Einführung und Übersicht
Chapitre 2
Ein algorithmisch unlösbares Problem: das Haltepr…
Das Halteproblem
Chapitre 3
Die Eine-Million-Dollar-Frage
Effizient lösbare Probleme, die Klasse P
Rucksack, Traveling Salesman, Graphenfärbung
Das Erfüllbarkeitsproblem der Aussagenlogik SAT
NP: Die genaue Definition
Eine Reduktion: Färbung kleiner gleich SAT
Die Eine-Million-Dollar-Frage
Chapitre 4
Was wäre, wenn ...?
Was wäre, wenn ...?
Chapitre 5
Was tun?
Umgang mit NP
Graphenfärbung

Was werden Sie lernen?

  1. Ziele der Theoriebildung
  2. Das Halteproblem und andere unentscheidbare Probleme
  3. Die Klassen P und NP: effizient lösbar versus eine Lösung effizient verifizieren
  4. Das Erfüllbarkeitsproblem der Aussagenlogik
  5. Reduktionen zwischen Problemen
  6. Der Satz von Cook und Levin: SAT ist ein schwerstes Problem in NP
  7. NP-Vollständigkeit
  8. Der Satz von Karp: weitere NP-vollständige Probleme
  9. Was wäre, wenn das Million-Dollar-Problem gelöst wäre?
  10. Approximationsalgorithmen, exakte Algorithmen, Spezialfälle, Heuristiken

An wen richtet sich der Kurs?

Alle, die die Eine-Million-Dollar-Frage verstehen wollen. 

Lehrende

Particuliers

Accès au cours avec certificat

Accédez au contenu du cours et vérifiez votre participation au cours et vos apprentissages avec un document officiel.

59 €*

Organisations & Groupes

Si ce cours vous intéresse en tant qu’organisation, et que vous souhaitez acheter un accès de cours pour plusieurs employés, nous vous informons sur les avantages d’achats en grande quantité.

Nous établissons une offre pour vous et votre équipe.

*Nos prix contiennent la TVA.

Avoir une question?

We are ready to help you!

Support Kite illustration

Avoir une question?

We are ready to help you!

Nous sommes prêts à vous aider!

Pour toute question concernant le contenu du cours, veuillez contacter notre service client