Algorithmen zur Annäherung

Sparen Sie mit 40% Rabatt auf 3 Monate Coursera Plus bei den Fähigkeiten, die Sie zum Strahlen bringen. Jetzt sparen

Algorithmen zur Annäherung

Dozent: Mark de Berg

6.893 bereits angemeldet

Bei enthalten

Mehr erfahren

4 Module

Verschaffen Sie sich einen Einblick in ein Thema und lernen Sie die Grundlagen.

33 Bewertungen

Stufe Mittel

Einige einschlägige Kenntnisse erforderlich

2 Wochen zu vervollständigen

unter 10 Stunden pro Woche

Flexibler Zeitplan

In Ihrem eigenen Lerntempo lernen

4 Module

Verschaffen Sie sich einen Einblick in ein Thema und lernen Sie die Grundlagen.

33 Bewertungen

Stufe Mittel

Einige einschlägige Kenntnisse erforderlich

2 Wochen zu vervollständigen

unter 10 Stunden pro Woche

Flexibler Zeitplan

In Ihrem eigenen Lerntempo lernen

Kompetenzen, die Sie erwerben

Kategorie: Graphentheorie
Kategorie: Algorithmen
Kategorie: Kombinatorik
Kategorie: Operations Research
Kategorie: Theoretische Informatik
Kategorie: Angewandte Mathematik
Kategorie: Modell-Optimierung

Wichtige Details

Zertifikat zur Vorlage

Zu Ihrem LinkedIn-Profil hinzufügen

Bewertungen

4 Aufgaben

Unterrichtet in Englisch

Erfahren Sie, wie Mitarbeiter führender Unternehmen gefragte Kompetenzen erwerben.

Weitere Informationen zu Coursera für Unternehmen

Logos von Petrobras, TATA, Danone, Capgemini, P&G und L'Oreal

In diesem Kurs gibt es 4 Module

Viele reale algorithmische Probleme können mit traditionellen algorithmischen Werkzeugen nicht effizient gelöst werden, zum Beispiel weil die Probleme NP-hart sind. Ziel des Kurses Approximationsalgorithmen ist es, sich mit wichtigen algorithmischen Konzepten und Techniken vertraut zu machen, die zur effektiven Bewältigung solcher Probleme erforderlich sind. Diese Techniken kommen zum Einsatz, wenn wir für bestimmte Probleme nicht die optimale Lösung benötigen, sondern eine Annäherung, die der optimalen Lösung nahe kommt. Wir werden sehen, wie man solche Näherungen effizient findet.

Voraussetzungen: Um an diesem Kurs erfolgreich teilnehmen zu können, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier eine kurze Liste dessen, was Sie wissen sollten: - O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert - Grundrechenarten: Manipulation von Summationen, Lösen von Rekursen, Arbeiten mit Logarithmen usw. - Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw. - Grundlegende Datenstrukturen: verknüpfte Listen, Stapel, Warteschlangen, Heaps - (Ausgewogene) binäre Suchbäume - Grundlegende Sortieralgorithmen, z.B. MergeSort, InsertionSort, QuickSort - Graphenterminologie, Darstellungen von Graphen (Adjazenzlisten und Adjazenzmatrix), grundlegende Graphenalgorithmen (BFS, DFS, topologische Sortierung, kürzeste Pfade) Das Material für diesen Kurs basiert auf den Kursnotizen, die Sie unter der Registerkarte Ressourcen finden.

In diesem Modul wird die Motivation für das Studium von Approximationsalgorithmen vermittelt. Wir werden erörtern, was Optimierungsprobleme sind und worin der Unterschied zwischen Heuristiken und Approximationsalgorithmen besteht. Schließlich werden wir das Konzept des Approximationsverhältnisses einführen, das eine zentrale Rolle bei der Analyse der Qualität von Approximationsalgorithmen spielt.

Das ist alles enthalten

1 Video1 Lektüre1 Aufgabe

In diesem Modul werden wir verschiedene Näherungsalgorithmen für das Problem des Lastausgleichs untersuchen. Bei diesem Problem geht es darum, eine gegebene Menge von Aufträgen, die jeweils eine bestimmte Bearbeitungszeit haben, auf eine Reihe von Rechnern zu verteilen. Das Ziel ist es, dies so zu tun, dass alle Aufträge so schnell wie möglich erledigt werden. Wir werden die Qualität der berechneten Lösungen anhand des Konzepts der rho-Approximation analysieren, das wir in der vorherigen Vorlesung kennengelernt haben. Bei dieser Analyse werden wir sehen, dass untere Schranken für die optimale Lösung eine entscheidende Rolle bei der Analyse spielen (oder, bei Maximierungsproblemen: obere Schranken).

Das ist alles enthalten

3 Videos1 Lektüre1 Aufgabe1 Programmieraufgabe

In diesem Modul führen wir die Technik der LP-Relaxation ein, um Approximationsalgorithmen zu entwerfen, und erklären, wie man das Approximationsverhältnis eines auf LP-Relaxation basierenden Algorithmus analysiert. Wir werden dies am Beispiel des (gewichteten) Vertex Cover Problems tun. Bevor wir jedoch die Technik der LP-Relaxation erklären, geben wir zunächst einen einfachen 2-Approximationsalgorithmus für das ungewichtete Vertex-Cover-Problem an.

Das ist alles enthalten

6 Videos2 Lektüren1 Aufgabe

6 VideosInsgesamt 69 Minuten

Das Vertex-Cover-Problem10 Minuten
Ein Näherungsalgorithmus für Vertex-Deckung11 Minuten
Eine kurze Einführung in die lineare Programmierung13 Minuten
Gewichtete Scheitelpunkt-Abdeckung15 Minuten
LP-Relaxation für gewichtete Vertex-Deckung7 Minuten
LP-Entspannung: Analyse des Approximationsverhältnisses13 Minuten

2 LektürenInsgesamt 65 Minuten

Kursnotizen 3.120 Minuten
Kursnotizen 3.245 Minuten

1 AufgabeInsgesamt 30 Minuten

LP-Entspannung30 Minuten

In diesem Modul stellen wir das Konzept der Polynomial-Time Approximation Scheme (PTAS) vor. Dabei handelt es sich um Algorithmen, die einer optimalen Lösung beliebig nahe kommen können. Wir beschreiben eine allgemeine Technik zum Entwurf von PTAS und wenden sie auf das berühmte Knapsack-Problem an. Schließlich werden wir sehen, wie PTAS, die mit der allgemeinen Technik entworfen wurden, analysiert werden können.

Das ist alles enthalten

6 Videos2 Lektüren1 Aufgabe1 Programmieraufgabe

6 VideosInsgesamt 62 Minuten

Polynomialzeit-Approximationsverfahren7 Minuten
Knapsack-Problem6 Minuten
Ein dynamischer Programmierungsalgorithmus für Knapsack16 Minuten
Ein PTAS für Rucksäcke12 Minuten
Analyse des PTAS für Knapsack: Annäherungsrate11 Minuten
Analyse des PTAS für Knapsack: Laufzeit9 Minuten

2 LektürenInsgesamt 90 Minuten

Kursnotizen 4.145 Minuten
Kursnotizen 4.245 Minuten

1 AufgabeInsgesamt 45 Minuten

Polynomialzeit-Approximationsverfahren45 Minuten

1 ProgrammieraufgabeInsgesamt 180 Minuten

PTAS für den Lastausgleich180 Minuten

Dozent

Lehrkraftbewertungen

(11 Bewertungen)

Mark de Berg

28DIGITAL

2 Kurse13.513 Lernende

von

28DIGITAL

Mehr von Algorithmen entdecken

Status: Kostenlos
École normale supérieure
Approximation Algorithms Part I
Kurs
Status: Kostenloser Testzeitraum
University of Colorado Boulder
Approximation Algorithms and Linear Programming
Kurs
Status: Kostenlos
École normale supérieure
Approximation Algorithms Part II
Kurs
Status: Kostenloser Testzeitraum
Packt
Algorithms and Problem Solving with Advanced Techniques
Kurs

Warum entscheiden sich Menschen für Coursera für ihre Karriere?

Felipe M.

Lernender seit 2018

„Es ist eine großartige Erfahrung, in meinem eigenen Tempo zu lernen. Ich kann lernen, wenn ich Zeit und Nerven dazu habe.“

Jennifer J.

Lernender seit 2020

„Bei einem spannenden neuen Projekt konnte ich die neuen Kenntnisse und Kompetenzen aus den Kursen direkt bei der Arbeit anwenden.“

Larry W.

Lernender seit 2021

„Wenn mir Kurse zu Themen fehlen, die meine Universität nicht anbietet, ist Coursera mit die beste Alternative.“

Chaitanya A.

„Man lernt nicht nur, um bei der Arbeit besser zu werden. Es geht noch um viel mehr. Bei Coursera kann ich ohne Grenzen lernen.“

Bewertungen von Lernenden

5 stars
78,78 %
4 stars
15,15 %
3 stars
3,03 %
2 stars
3,03 %
1 star
0 %

Zeigt 3 von 33 an

Geprüft am 10. Okt. 2020

Please try to include some more numeric example like load balancing problem in the vertex cover and rest topics

Geprüft am 24. Feb. 2021

Very good course! A nice introduction to approximation algorithms.

Weitere Bewertungen anzeigen

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.

Wenn Sie sich für den Kurs einschreiben, erhalten Sie Zugang zu allen Kursen der Spezialisierung, und Sie erhalten ein Zertifikat, wenn Sie die Arbeit abgeschlossen haben. Ihr elektronisches Zertifikat wird Ihrer Seite "Leistungen" hinzugefügt - von dort aus können Sie Ihr Zertifikat ausdrucken oder Ihrem LinkedIn-Profil hinzufügen.

Ja. Für ausgewählte Lernprogramme können Sie finanzielle Unterstützung oder ein Stipendium beantragen, wenn Sie die Einschreibegebühr nicht aufbringen können. Wenn für das von Ihnen gewählte Lernprogramm eine finanzielle Unterstützung oder ein Stipendium verfügbar ist, finden Sie auf der Beschreibungsseite einen Link zur Beantragung.