Schlüsseltechnologie

STP029: Algorithmische Komplexität

Listen Later

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:

                  • Bacon-Zahl
                  • Erdős-Zahl
                  • How large is 52 factorial?
                    • ...more
                    View all episodesView all episodes
                    Download on the App Store
                    SchlüsseltechnologieBy Xyrillian Noises

                    More shows like Schlüsseltechnologie

                    View all
                    Freak Show by Metaebene Personal Media - Tim Pritlove

                    Freak Show

                    11 Listeners

                    Methodisch inkorrekt! by Methodisch inkorrekt!

                    Methodisch inkorrekt!

                    15 Listeners

                    Lage der Nation - der Politik-Podcast aus Berlin by Philip Banse & Ulf Buermeyer

                    Lage der Nation - der Politik-Podcast aus Berlin

                    228 Listeners

                    c’t uplink - der IT-Podcast aus Nerdistan by c’t Magazin

                    c’t uplink - der IT-Podcast aus Nerdistan

                    9 Listeners

                    Chaosradio by Chaos Computer Club Berlin

                    Chaosradio

                    7 Listeners

                    heiseshow by heise online

                    heiseshow

                    3 Listeners

                    Logbuch:Netzpolitik by Metaebene Personal Media - Tim Pritlove

                    Logbuch:Netzpolitik

                    7 Listeners

                    Jung & Naiv by Tilo Jung

                    Jung & Naiv

                    45 Listeners

                    Holger ruft an by Übermedien

                    Holger ruft an

                    2 Listeners

                    Die Wochendämmerung - Der stabile Wochenrückblick by Katrin Rönicke und Holger Klein (hauseins)

                    Die Wochendämmerung - Der stabile Wochenrückblick

                    14 Listeners

                    Sicherheitshalber by Der Podcast zur sicherheitspolitischen Lage in Deutschland, Europa und der Welt.

                    Sicherheitshalber

                    46 Listeners

                    Bit-Rauschen: Der Prozessor-Podcast von c’t by c't Magazin

                    Bit-Rauschen: Der Prozessor-Podcast von c’t

                    0 Listeners

                    Legion by rbb | NDR | Undone

                    Legion

                    7 Listeners

                    Haken dran – das Social-Media-Update der c't by Gavin Karlmeier

                    Haken dran – das Social-Media-Update der c't

                    2 Listeners

                    Passwort - der Podcast von heise security by Dr. Christopher Kunz, Sylvester Tremmel

                    Passwort - der Podcast von heise security

                    3 Listeners