STP029: Algorithmische Komplexität

Schlüsseltechnologie

محتوای ارائه شده توسط Stefan Majewsky and Xyrillian Noises. تمام محتوای پادکست شامل قسمت‌ها، گرافیک‌ها و توضیحات پادکست مستقیماً توسط Stefan Majewsky and Xyrillian Noises یا شریک پلتفرم پادکست آن‌ها آپلود و ارائه می‌شوند. اگر فکر می‌کنید شخصی بدون اجازه شما از اثر دارای حق نسخه‌برداری شما استفاده می‌کند، می‌توانید روندی که در اینجا شرح داده شده است را دنبال کنید.https://fa.player.fm/legal

2y ago 1:06:05

OPUS•خانه قسمت

Fetch error

Hmmm there seems to be a problem fetching this series right now. Last successful fetch was on January 02, 2025 14:02 (20d ago)

What now? This series will be checked again in the next day. If you believe it should be working, please verify the publisher's feed link below is valid and includes actual episode links. You can contact support to request the feed be immediately fetched.

In dieser Episode möchte Xyrill gern eine Vorlesung halten über ein Thema, das in der Informatik zu den Grundlagen für das erste Semester gehört. Zwischendurch ist ttimeless etwas schwer von Begriff. Zu hoffen ist, dass ihr trotzdem durchhaltet. Und haltet ein paar Skatkarten bereit!

Shownotes

Komplexität: Ressourcenbedarf eines Algorithmus (Zeitkomplexität, Platzkomplexität; vielleicht auch Kostenkomplexität etc.)
- Forschungsgegenstand der Komplexitätstheorie
- hier hauptsächlich Zeitkomplexität
einfaches Beispielproblem: "Gegeben ist eine sortierte Liste von Wörtern (Schlagwörter im Wörterbuch). Finde ein bestimmtes Wort."
- naive Idee: jedes Wort nacheinander anschauen -> lineare Laufzeit (Verdopplung der Wörtermenge verdoppelt die zu erwartende Suchzeit)
- kluge Idee: Bisektion -> logarithmische Laufzeit (Verdopplung der Wörtermenge erfordert nur einen zusätzlichen Schritt)
Beschreibung von Komplexität: Landau-Symbole
- wichtigste Form: f = O(g) heißt, dass f "nicht wesentlich schneller als g wächst (sprich: f(n)/g(n) bleibt beschränkt, wenn n -> ∞)
- Beispiel: naive Suche über eine Liste von n Elementen hat eine Laufzeit in O(n), Bisektion hat eine Laufzeit in O(log n)
etwas komplexeres Beispiel: Sortieralgorithmen ("Gegeben ist eine Liste von Zahlen/Wörtern/etc. Sortiere diese Liste.")
- Live-Beispiel: Skatkarten mischen und dann sortieren -> Auf welche Art und Weise sortieren wir intuitiv?
- Sortieralgorithmen auf Computern: zwei Grundbausteine
  - Vergleich von zwei Elementen
  - Tauschen von zwei Elementen
- anhand von Skatkarten diskutierbar:
  - Insertionsort: O(n^2)
  - Quicksort: O(n log n)
  - Mergesort: O(n log n)
- wünschenswerte Eigenschaften:
  - Lokalität (Timsort!, siehe STP007)
  - Stabilität (Mergesort!)
  - Codegröße (Quicksort!)
Schauempfehlung (mit Epilepsie-Warnung): Visualisierung verschiedener Sortieralgorithmen
im Gespräch erwähnt:

67 قسمت

#Technologie #Stefan Majewsky #Xyrillian Noises