Wartungsankündigung: Wichtig: bitte beachten Sie unsere Wartungsankündigungen für Dienstag, den 02. April 2024 und Freitag, den 05. April 2024 auf der Magazineinstiegseite!
Maintenance announcement: please note our maintenance announcements for Tuesday, 02 April 2024 and Friday, 05 April on the repository page!
Wartungshinweis: wegen wichtigen Wartungsarbeiten an den OpenCast-Servern, bitten wir Sie über das Osterwochenende keine neuen Videos hochzuladen! Die bereits vorhandenen OpenCast-Videos stehen aber wieder zur Verfügung.
Symbol Kurs

2400023 – Parametrisierte Algorithmen

Sehr viele in der Praxis auftretende Probleme sind NP-schwer und damit im Allgemeinen (vermutlich) nicht in polynomieller Zeit lösbar. Dennoch können diese Probleme häufig effizient gelöst werden, da die Eingaben “gutartig” sind. Eine Möglichkeit diese Gutartigkeit der Instanzen formal zu fassen bietet die Betrachtung der parametrisierten Komplexität. Dabei assoziiert man mit jeder Instanz einen Parameter k, der ein Maß für die Komplexität der Eingabe darstellt. Ziel ist es dann, einen Algorithmus zu finden, dessen Laufzeit nur polynomiell von der Eingabegröße n aber ggf. exponentiell von dem Parameter k abhängt. Im Vergleich zur groben Klassifizierung eines Problems als polynomiell lösbar bzw. NP-schwer bietet die parametrisierte Betrachtungsweise eine deutlich differenziertere Sicht auf schwere Probleme. Siehe https://scale.iti.kit.edu/teaching/2021ss/param_algo/start

Zusammenfassung

Sehr viele in der Praxis auftretende Probleme sind NP-schwer und damit im Allgemeinen (vermutlich) nicht in polynomieller Zeit lösbar. Dennoch können diese Probleme häufig effizient gelöst werden, da die Eingaben “gutartig” sind. Eine Möglichkeit diese Gutartigkeit der Instanzen formal zu fassen bietet die Betrachtung der parametrisierten Komplexität. Dabei assoziiert man mit jeder Instanz einen Parameter k, der ein Maß für die Komplexität der Eingabe darstellt. Ziel ist es dann, einen Algorithmus zu finden, dessen Laufzeit nur polynomiell von der Eingabegröße n aber ggf. exponentiell von dem Parameter k abhängt. Im Vergleich zur groben Klassifizierung eines Problems als polynomiell lösbar bzw. NP-schwer bietet die parametrisierte Betrachtungsweise eine deutlich differenziertere Sicht auf schwere Probleme.

Siehe https://scale.iti.kit.edu/teaching/2021ss/param_algo/start

Allgemein

Sprache
Deutsch
Copyright
This work has all rights reserved by the owner.

Verfügbarkeit

Zugriff
Unbegrenzt – wenn online geschaltet
Aufnahmeverfahren
Sie können diesem Kurs direkt beitreten.
Zeitraum für Beitritte
Unbegrenzt

Für Kursadministratoren freigegebene Daten

Daten des Persönlichen Profils
Benutzername
Vorname
Nachname
E-Mail
Matrikelnummer

Zusätzliche Informationen

Objekt-ID
1947236
Link zu dieser Seite