Approximationsalgorithmen, Teil 2 Dies ist die Fortsetzung von Approximationsalgorithmen, Teil 1. Hier lernen Sie die Dualität der linearen Programmierung, angewandt auf den Entwurf einiger Approximationsalgorithmen, und die semidefinite Programmierung, angewandt auf Maxcut. Durch die Teilnahme an den beiden Teilen dieses Kurses lernen Sie eine Reihe von Problemen kennen, die zu den Grundlagen der theoretischen Informatik gehören, sowie leistungsstarke Entwurfs- und Analysetechniken. Nach Abschluss des Kurses werden Sie in der Lage sein, bei einem neuen kombinatorischen Optimierungsproblem zu erkennen, ob es einem der wenigen bekannten Grundprobleme nahe kommt, und Sie werden in der Lage sein, Entspannungen der linearen Programmierung zu entwerfen und randomisierte Rundungen zu verwenden, um zu versuchen, Ihr eigenes Problem zu lösen. Der Kursinhalt und insbesondere die Hausaufgaben sind theoretischer Natur und beinhalten keine Programmieraufgaben.
(44 Bewertungen)
Wichtige Details
33 Aufgaben
Erfahren Sie, wie Mitarbeiter führender Unternehmen gefragte Kompetenzen erwerben.
In diesem Kurs gibt es 4 Module
Dieses Modul befasst sich nicht mit einem bestimmten kombinatorischen Optimierungsproblem. Stattdessen wird ein zentrales Merkmal der linearen Programmierung eingeführt, die Dualität.
Das ist alles enthalten
9 Videos11 Lektüren8 Aufgaben1 peer review
In diesem Modul wird die Dualität der linearen Programmierung verwendet, um einen Algorithmus für ein anderes grundlegendes Problem, das Steinersche Waldproblem, zu entwickeln.
Das ist alles enthalten
8 Videos9 Lektüren8 Aufgaben1 peer review
Dieses Modul setzt die Lehre der algorithmischen Anwendungen der Dualität der linearen Programmierung fort, indem es sie auf ein anderes grundlegendes Problem anwendet, nämlich das Problem der Standortwahl von Einrichtungen.
Das ist alles enthalten
9 Videos10 Lektüren8 Aufgaben1 peer review
Wir stellen eine Verallgemeinerung der linearen Programmierung vor, die semidefinite Programmierung, die in diesem Modul verwendet wird, um einen Approximationsalgorithmus für ein anderes grundlegendes Problem zu entwickeln, das Problem des maximalen Schnitts.
Das ist alles enthalten
11 Videos12 Lektüren9 Aufgaben1 peer review
Dozent
Empfohlen, wenn Sie sich für Algorithmen interessieren
École normale supérieure
EIT Digital
University of Colorado Boulder
University of Colorado Boulder
Warum entscheiden sich Menschen für Coursera für ihre Karriere?
Bewertungen von Lernenden
Zeigt 3 von 44
44 Bewertungen
- 5 stars
88,63 %
- 4 stars
6,81 %
- 3 stars
2,27 %
- 2 stars
2,27 %
- 1 star
0 %
Geprüft am 28. Feb. 2018
Geprüft am 27. Okt. 2016
Geprüft am 13. März 2016
Neue Karrieremöglichkeiten mit Coursera Plus
Unbegrenzter Zugang zu über 7.000 erstklassigen Kursen, praktischen Projekten und Zertifikatsprogrammen, die Sie auf den Beruf vorbereiten – alles in Ihrem Abonnement enthalten
Bringen Sie Ihre Karriere mit einem Online-Abschluss voran.
Erwerben Sie einen Abschluss von erstklassigen Universitäten – 100 % online
Schließen Sie sich mehr als 3.400 Unternehmen in aller Welt an, die sich für Coursera for Business entschieden haben.
Schulen Sie Ihre Mitarbeiter*innen, um sich in der digitalen Wirtschaft zu behaupten.
Häufig gestellte Fragen
Der Zugang zu Vorlesungen und Aufgaben hängt von der Art Ihrer Einschreibung ab. Wenn Sie einen Kurs im Prüfungsmodus belegen, können Sie die meisten Kursmaterialien kostenlos einsehen. Um auf benotete Aufgaben zuzugreifen und ein Zertifikat zu erwerben, müssen Sie die Zertifikatserfahrung während oder nach Ihrer Prüfung erwerben. Wenn Sie die Prüfungsoption nicht sehen:
Der Kurs bietet möglicherweise keine Prüfungsoption. Sie können stattdessen eine kostenlose Testversion ausprobieren oder finanzielle Unterstützung beantragen.
Der Kurs bietet möglicherweise stattdessen die Option 'Vollständiger Kurs, kein Zertifikat'. Mit dieser Option können Sie alle Kursmaterialien einsehen, die erforderlichen Bewertungen abgeben und eine Abschlussnote erhalten. Dies bedeutet auch, dass Sie kein Zertifikat erwerben können.