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.
Genießen Sie unbegrenztes Wachstum mit einem Jahr Coursera Plus für 199 $ (regulär 399 $). Jetzt sparen.
(45 Bewertungen)
Kompetenzen, die Sie erwerben
- Kategorie: Lineare Algebra
- Kategorie: Theoretische Informatik
- Kategorie: Fortgeschrittene Mathematik
- Kategorie: Kombinatorik
- Kategorie: Mathematische Modellierung
- Kategorie: Wahrscheinlichkeit
- Kategorie: Algorithmen
Wichtige Details
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
Mehr von Algorithmen entdecken
Status: KostenlosÉcole normale supérieure
28DIGITAL
Status: Kostenloser TestzeitraumUniversity of Colorado Boulder
Status: KostenlosPrinceton University
Warum entscheiden sich Menschen für Coursera für ihre Karriere?
Bewertungen von Lernenden
45 Bewertungen
- 5 stars
88,88 %
- 4 stars
6,66 %
- 3 stars
2,22 %
- 2 stars
2,22 %
- 1 star
0 %
Zeigt 3 von 45 an
Geprüft am 27. Okt. 2016
Demanding course with lots of great algorithm concepts based on Linear Programming.
Geprüft am 15. Feb. 2017
Even better than the first! Very good classes (except for the two first of week 3 ...)
Geprüft am 13. März 2016
It is remarkable to note that Professor Claire Mathieu explains such a complex subject in such a elegant and understandable manner.
Häufig gestellte Fragen
Um Zugang zu den Kursmaterialien und Aufgaben zu erhalten und um ein Zertifikat zu erwerben, müssen Sie die Zertifikatserfahrung erwerben, wenn Sie sich für einen Kurs anmelden. Sie können stattdessen eine kostenlose Testversion ausprobieren oder finanzielle Unterstützung beantragen. Der Kurs kann stattdessen die Option "Vollständiger Kurs, kein Zertifikat" anbieten. 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.
Weitere Fragen
Finanzielle Unterstützung verfügbar,
¹ Einige Aufgaben in diesem Kurs werden mit AI bewertet. Für diese Aufgaben werden Ihre Daten in Übereinstimmung mit Datenschutzhinweis von Courseraverwendet.