Schlüsseltechnologie

Schlüsseltechnologie

By Xyrillian NoisesTechnology
Download on the App Store

Schlüsseltechnologie episodes

  • STP038: Software-Tests

    Nach der Episode über die Fehler, spechen wir heute darüber, wie man sie vermeidet. Wie nicht anders zu erwarten, ist auch dies ein Thema, bei dem reichhaltige Meinungsdiskurse geführt werden.

    Shownotes

    • Warum testen? -> siehe STP037

    • Anforderungen an Tests

      • reproduzierbar: nicht abhängig von unerwarteten äußeren Einflüssen oder menschlicher Intervention
      • fokussiert: im Fehlerfall soll möglichst klar sein, wo das Problem liegt
      • schnell: damit man beim Ändern des Systems schnelles Feedback bekommt (siehe auch XKCD 303)
      • realitätsnah: überprüft eine Funktion, die der Benutzer so tatsächlich benötigt

      • manuelle Tests

        • kostenintensiv: Online-Shooter braucht(e) 200 Tester (das Spiel erlaubt Matches mit bis zu 60 Teilnehmern)
        • erfüllt von den obigen Anforderungen nur die Realitätsnähe
        • wenn's geht, lieber automatisieren
        • gängige Strategie: manuelle Tests zur Fehlersuche, im Zweifelsfall durch die Kunden ;) – dann Nachstellung des gefundenen Problems

        • automatisierte Tests am Beispiel der Testpyramide

          • Unit Tests: Überprüfung einer einzelnen Komponente in Isolation
            • besonders wertvoll, wenn die Komponenten auf besonders reproduzierbare Weise arbeiten (zum Beispiel pure Berechnungen; Vorgänge, die nicht Netzwerkzugriff/Festplattenzugriff/etc. erfolgen)
            • Problem: es reicht nicht, wenn jede Komponente für sich genommen funktioniert, aber sie nicht zusammen passen
            • Bewertung: reproduzierbar, fokussiert, schnell, aber nicht realitätsnah
            • Integration Tests: Überprüfung des Zusammenspiels mehrerer Komponenten eines Gesamtsystems
              • nach Möglichkeit Eingrenzung äußerer Faktoren, z.B. statt Kommunikation mehrerer Komponenten über ein reales Netzwerk Simulation einer Netzwerkstruktur im Programm oder mittels Containern/VMs (siehe STP023)
              • Bewertung: tendenziell weniger reproduzierbar, etwas langsamer, weniger fokussiert, aber realitätsnäher
              • End-to-End-Tests (E2E): Überprüfung des Verhaltens eines Gesamtsystems
                • analog zu den manuellen Tests, aber nach festem Algorithmus
                • höchster Aufwand in der Umsetzung, siehe insbesondere UI-Tests mittels Headless Browser etc.
                • Bewertung: am wenigsten reproduzierbar (aufgrund der Vielzahl an Variablen), am unfokussiertesten, am langsamsten, aber am nächsten an der Realität
                • allgemeine Empfehlung: ganz viele kleine Unit Tests und einige mittelgroße Integrationstests für die schnelle Feedbackschleife, dazu einige wenige große E2E-Tests für den Abgleich mit der Realität

                • alternative Teilung: Blackbox-Tests vs. Whitebox-Tests

                  • Blackbox: Umsetzung eines Tests ohne innere Kenntnis der Struktur des Systems, z.B. anhand einer Spezifikation
                  • Vorteil: ein Blackbox-Test durch ein anderes Team kann Missverständnisse des ursprünglichen Teams aufdecken
                  • Nachteil: kann nur E2E sein

                  • die reine Lehre: Test Driven Development (Testgetriebene Entwicklung)

                    • neue Funktionalität darf man nur bauen, wenn es Testabdeckung dafür gibt
                    • erst fehlschlagenden Test schreiben; dann Funktionalität einbauen, sodass der Test erfolgreich durchläuft; dann aufräumen
                    • Xyrill macht lieber "Data Driven Development" und hat Bedenken

                    • Kann man die Qualität eines Tests bewerten? -> Idee: Code Coverage

                      • Welcher Anteil des Programmcodes wird von meinem Test tatsächlich abgedeckt?
                      • Was heißt eigentlich "Anteil"?
                        • Beispiel: if (a or b or c) { return "Kredit abgelehnt" } (einfach bei Zeilenabdeckung, schwierig bei Bedingungsabdeckung)
                        • Beispiel: "Kommt ein Software-Tester in eine Bar."
                        • Problem: Goodharts Gesetz, "Sobald eine Metrik zu einem Ziel wird, hört sie auf, eine gute Metrik zu sein."
                        • Problem: für manche Zeilen sind Tests wichtiger als andere (wichtig für vertrackte Logik, weniger wichtig für Sofortabbruch bei unerwarteten Fehlern)

                        • Tests muss man trotzdem noch schreiben. Kann man das wegautomatisieren?

                          • Statische Analyse: automatische Suche nach bedenklichen Mustern (z.B. Datei wurde zum Schreiben geöffnet, wird aber am Ende nicht geschlossen -> Risiko des Datenverlusts; z.B. Verwendung veralteter kryptografischer Primitiven)
                          • Fuzzing: anstatt eines Tests mit festen Werten ("bei Eingabe X wird Ausgabe Y erwartet") nur Vorgabe einer Struktur ("wenn hier ein Text reingesteckt wird, kommt da eine Zahl raus"), dann automatische Suche nach Absturzbedingungen

                          • Machen Tests die Sache immer besser?

                            • Heisenbug: "ein Softwarefehler, der zu verschwinden oder sein Verhalten zu verändern scheint, wenn man versucht, ihn zu untersuchen"

                            • im Gespräch erwähnt:

                              • ISO9001
                              • FG034 zu Werner Heisenberg
                                • 1 hr 23 min
                              • STP037: Berühmte Softwarefehler

                                Wir alle machen Fehler. So gut, so trivial. Wenn allerdings Elektronenrechner im Spiel sind, kann das durchaus kritisch werden. In manchen Fällen sogar tödlich.

                                ShownotesErrata zu STP034 von Thomas aus Berlin:

                                Am Ende der Folge wundert sich ttimeless darüber, warum sin(pi) auf dem Taschenrechner immer ein Ergebnis von 0,0548... produziert. Du versuchst, das dann mit möglichen Ungenauigkeiten der Abbildung von pi zu erklären.

                                Ich glaube, die Antwort ist viel einfacher: In der normalen Einstellung DEG erwartet der Taschenrechner die Eingabe in Grad und sin(pi°) = 0,0548... ist damit auch korrekt. Stellt man den Taschenrechner auf RAD (Radiant), dann rechnet der Taschenrechner auch korrekt sin(pi) = 0.

                                • "Off by One" ("um eins daneben")

                                  • Diese Folge ist Nr. 37 und somit die 38. Folge dieses Podcasts!
                                  • häufige Konvention in der IT: Nummerierung fängt bei Null an
                                    • In einer Liste mit 10 Elementen das vorderste den Index 0 und das hinterste den Index 9.
                                    • formal plausibel, da Null die erste natürliche Zahl ist (ansonsten ist ℕ unter Addition keine Gruppe; siehe EWD831)
                                    • technisch plausibel, da die Speicheradresse einer Liste für gewöhnlich die Speicheradresse des vordersten Elementes ist; dieses hat also einen Abstand von 0 zum Beginn der Liste
                                    • siehe auch Zaunpfahlfehler
                                    • Thema heute: Wie katastrophal können die Auswirkungen solcher kleinen Fehler sein?

                                    • mechanische Fehler: "First actual case of bug being found."

                                    • Überlauf: Ariane-Flug V88 (1996)

                                      • erster Flug der Ariane 5
                                      • Steuerungssoftware war von der Ariane 4 übernommen und nicht auf derart große Horizontalgeschwindigkeiten ausgelegt
                                      • Überlauf bei Konvertierung von float64 in int16; aber bei dieser konkreten Variable keine Überlaufprüfung wegen Ressourcenknappheit
                                      • größeres Motiv laut Untersuchungsbericht: in der Gefahrenabschätzung wurde nicht hinreichend berücksichtigt, dass die Software (und nicht nur die Hardware) fehlerhaft sein könnte
                                      • Folge: erster großflächiger Einsatz von Fehlersuche mittels statischer Code-Analyse

                                      • Überlauf: Y2K Bug -> siehe STP016

                                      • Überlauf: Heartbleed (2014)

                                      • Drift: Dhahran Missile Incident (1991), siehe auch

                                        • Hintergrund: 28 Amerikaner getötet durch Raketenbeschuss auf eine US-Basis in Saudi Arabien während des 1. Golfkriegs
                                        • Fehler im Raketenabwehrsystem: aufgrund Rundungsfehler driftet die interne Uhr um einen Faktor von 0,00000095
                                        • nach 100 Stunden Dauerbetrieb ist die Drift bei 0,34 Sekunden; entspricht bei Raketen mit Mach 4 einer Distanz von etwa 500 Metern

                                        • Spezifikation falsch gelesen (oder Kommunikationsproblem): Mars Climate Orbiter (1999)

                                          • NASA hatte metrische Einheiten verwendet (Impuls in Newtonsekunden), die Navigationssoftware von Lockheed Martin hingegen imperiale Einheiten (Impuls in Pound-Force-Sekunden)

                                          • Clusterfuck: Therac-25 (1985-1987), unter anderem:

                                            • verteiltes verstreutes System: fehlerhafte Synchronisation zwischen einem Messprozess und einem parallel arbeitenden Steuerprozess
                                            • Benutzerführung: in bestimmten Situationen wurde nach der Eingabe neuer Daten der alte Datensatz weiterverwendet, obwohl die Benutzeroberfläche den neuen Datensatz anzeigte
                                            • Überlauf: 8-Bit-Flag für die Anzeige der Notwendigkeit einer Sicherheitsprüfung konnte von 255 auf 0 überlaufen und dadurch die Prüfung überspringen

                                            • überfordert von Komplexität: Corrupted Blood (2005)

                                              • vor COVID-19 eines der wichtigsten Studienobjekte für das Verbreitungsmuster einer Pandemie, inklusive Tiervektoren und asymptomatisch infektiösen Patienten
                                              • ein bestimmter Bosskampf in "World of Warcraft" versieht Spielercharaktere mit einem negativen Statuseffekt, der sie langsam tötet und der auf naheliegende Charaktere ansteckend wirkt
                                              • Spieler sollten mit diesem Statuseffekt den Bosskampf nicht verlassen können, aber die Reittiere der Spieler konnten es!

                                              • analog zu Copy-Paste-Fehler: Mariner 1 (1962)

                                                • Programmcode wurde auf Papier geschrieben, dort wurde fehlerhafterweise mit "R" statt mit dem korrekten "R̅" (R mit Überstrich) gerechnet

                                                • Copy-Paste-Fehler: Pentium-FDIV-Bug

                                                  • Division von Fließkommazahlen (siehe STP009) beim Pentium verwendet einen Algorithmus, der zur Beschleunigung eine Tabelle von vorberechneten Werten verwendet
                                                  • fünf Einträge in dieser Tabelle wurden nicht richtig in das finale Chip-Design übernommen
                                                  • Ergebnis: bestimmte Divisionen liegen um einen Bruchteil eines ‰ daneben
                                                  • Rückrufaktion im Wert von über 400 Millionen $
                                                  • "Wie viele Intel-Mitarbeiter braucht man, um eine Glühbirne zu wechseln? 1,9999983256"
                                                  • im Gespräch erwähnt: Fast Inverse Square Root
                                                    • 1 hr 6 min
                                                  • STP036: LaTeX

                                                    Diesmal ist für ttimeless ein echtes Herzensthema an der Reihe. Dafür tritt man auch mal zum zweiten Aufnahmeversuch an. All das, um euch ein Textsatzpogramm nahezubringen, das im Kern 37 Jahre alt ist.

                                                    ShownotesZu dieser Sendung liegt ein Begleitdokument mit zugehörigen Quelldateien vor.

                                                    • Ein Mann, der nicht den Regeln folgt: Donald Knuth

                                                      • The Art of Computer Programming – szenische Lesung des ersten Unterabschnittes
                                                      • Knuth vs. Email
                                                        • "Email is a wonderful thing for people whose role in life is to be on top of things. But not for me; my role is to be on the bottom of things."

                                                        • Textsatz: "in einer Druckerei, einem Verlag o. Ä. der Arbeitsschritt, der durch ein technisches Verfahren aus einer Vorlage (einem Text, Grafiken, Bildern usw.) eine drucktaugliche Form herstellt"

                                                          • unter anderem unser Interesse: Formelsatz
                                                          • Blütezeit Anfang der 1900er Jahre parallel zur Formalisierung der Mathematik
                                                          • Tiefpunkt ab 1925 wegen rein auf Schreibmaschinen gesetzter Arbeiten
                                                          • "Dieser Entwicklung hat Donald Knuth ab 1977 mit der Entwicklung von TeX Einhalt geboten. Ab etwa 1994 gilt es als schlechter Stil, mathematische Texte nicht mit TeX zu setzen."

                                                          • TeX und LaTeX

                                                            • Beispieldokument
                                                            • Kein WYSIWYG (What You See Is What You Get), stattdessen Beschreibung des Dokumentes durch Quelltext, dadurch sehr kompakt und leicht versionierbar
                                                            • Logische Auszeichnung ("Kapitelüberschrift" statt "Arial, fett, 24 Punkt"), dadurch Maschinenlesbarkeit (z.B. automatische Erstellung von Inhaltsverzeichnissen)
                                                            • Rechnerunabhängigkeit (heute gang und gäbe, damals revolutionär) sowohl der Software als auch der resultierenden Dokumente (ursprünglich DVI, heutzutage PDF)
                                                            • Rückwärtskompatibilität
                                                            • Open Source
                                                            • Anpassbarkeit, Programmierbarkeit (z.B. AMSLaTeX, MusicTeX, TikZ, Beamer)
                                                            • professionelles Aussehen entsprechend den Grundsätzen der Typografie (KOMA-Script!)

                                                            • im Gespräch erwähnt:

                                                              • dinbrief.cls
                                                              • Museum für Druckkunst Leipzig
                                                              • CRE zu TeX/LaTeX
                                                              • CRE zu Typografie
                                                              • Videobeweis von Xyrills Formelsatz-Lesefähigkeiten (ab 01:31:00)
                                                              • Xyrills Physik-Diplomarbeit und Informatik-Bachelorarbeit
                                                                • 1 hr 1 min
                                                              • STP035: Aprilscherz-RFCs

                                                                April, April! Ha, erwischt. Hier eine Sonderfolge mit vergnüglichen RFCs, die einen niederschwelligen Einblick in technische Spezifikationen bieten.

                                                                Viel Spass beim Hören und passt auf, ihr werdet alle gehirngewaschen.

                                                                Shownotes

                                                                • vollständige Liste siehe Wikipedia

                                                                  • wir präsentieren hier nur eine kleine Auswahl

                                                                  • RFC 1097 (von 1989): TELNET-Option "Unterschwellige Botschaft"

                                                                    • zu TELNET siehe STP022
                                                                    • "Die Nutzung von Hinweisbannern und Newslettern ist oft nicht ausreichend, um widerspenstige Nutzer zum Upgrade auf die neueste Telnet-Version zu bewegen. Manche Nutzer werden die selben veralteten Versionen noch Jahre weiterverwenden. [...] Diese Nutzer müssen auf sanfte Weise 'überredet' werden."
                                                                    • Kontext: Wikipedia zu unterschwelligen Botschaften im Fernsehen

                                                                    • RFC 1149 (von 1990): IP-Übertragungen via Brieftaube

                                                                      • gute Illustration des Netzwerk-Schichtenmodells (siehe STP005)
                                                                      • 2001: Praxisversuch durch die Linux User Group im norwegischen Bergen

                                                                      • RFC 2100 (von 1997): "The naming of hosts"

                                                                        • ein Gedicht zur Frage, was gute Namen für Computer sind
                                                                        • siehe auch RFC 1178: "Choosing a name for your computer"

                                                                        • RFC 2324 (von 1998): Hyper Text Coffee Pot Control Protocol (HTCPCP/1.0)

                                                                          • ein früher Beitrag zur Heimautomatisierung aber für "Kaffee-mit-Milch-Trinker" eventuell mit Problemen behaftet

                                                                          • RFC 3514 (von 2003): "The Security Flag in the IPv4 Header"

                                                                            -böswillige Teilnehmer des Internets werden aufgefordert ein ensprechendes Bit im Header zu setzen

                                                                          • RFC 5514 (von 2009): "IPv6 over Social Networks"

                                                                            • schon wieder das Netzwerk-Schichtenmodell: wenn etwas Bytes übertragen kann, kann es IP-Pakete übertragen

                                                                            • RFC 6919 (von 2013): Neue definierte Schlüsselwörter für Standard-Texte

                                                                              • nimmt satirischen Bezug auf die Begriffsdefinitionen in RFC 2119

                                                                              • RFC 7168 (von 2014): Update für RFC2324 zur Zubereitung von Tee

                                                                                • geht in besonderem Maße auch auf verschiedene Teesorten und feste Zuschlagstoffe ein

                                                                                • RFC 7511 (von 2015): Malerische Routen für IP-Pakete

                                                                                  • nimmt satirischen Bezug auf Routenplanungsoptionen in Navigationssystemen ("schnelle" vs. "spritsparende" vs. "malerische" Route)
                                                                                  • "In Zeiten von Green IT wird großer Aufwand getrieben, um den Energieverbrauch von Netzwerkgeräten und Computern zu reduzieren und damit die Umwelt zu schützen. Dieses Dokument beleuchtet Green IT aus einem anderen Winkel"

                                                                                  • RFC 8140 (von 2017): Eine Galerie mit ASCII Art

                                                                                    • "Johannes Gutenberg entdeckte und patentierte ASCII und die dazu passende Schriftart 'Courier New' mit ihrer nunmehr berühmten "Zehn-Punkt"-Größe. Seither haben sich Kunsthandwerker darum bemüht, ihre Sicht der Welt in gedruckter Form abzubilden."

                                                                                    • RFC 9225 (von 2022): "Software Defects Considered Harmful"

                                                                                      • "Handlungsempfehlungen: 1. Software-Autoren DÜRFEN KEINE Fehler einbauen. 2. Wenn Fehler eingebaut werden, MÜSSEN sie klar dokumentiert werden. [...] 5. Nehmen Sie an, dass externe Eingaben das Ergebnis von Fehlern sind. [...] 6. Genau genommen sollten sie auch annehmen, dass interne Eingaben das Ergebnis von Fehlern sind."
                                                                                      • Kontext: "Goto Considered Harmful" von 1968
                                                                                      • "Considered Harmful" ist ein Snowclone

                                                                                      • Im Gespäch erwähnt:

                                                                                        • RFC-Podcast Episode 011
                                                                                          • 1 hr 4 min
                                                                                        • STP034: Compilerbau

                                                                                          In dieser Episode soll es detaillierter um Compiler gehen. Jene Programmme, die dafür zuständig sind, andere Programme zu erzeugen. Um es mit C3PO zu sagen: "... Wie pervers." :)

                                                                                          Shownotes

                                                                                          • Compiler: wandelt eine Programmiersprache (siehe STP033) in eine andere Programmiersprache oder Maschinensprache (siehe STP011)

                                                                                            • insb. Erkennung und Abweisung fehlerhafter Konstrukte (z.B. 42 + 5 ist okay, aber 42 + "Test" nicht)

                                                                                            • Unterbegriffe zu "Compiler"

                                                                                              • Interpreter: anstatt Erzeugung eines Zielcodes direkte Ausführung
                                                                                              • REPL: Interpreter für die interaktive Verwendung ("Read Evaluate Print Loop")
                                                                                              • JIT-Compiler: direkte Ausführung wie ein Interpreter, aber es wird echter Maschinencode erzeugt ("Just In Time")
                                                                                              • z.B. portable Programme: Compiler erzeugt Maschinencode für ein virtuelles Maschinenmodell, Laufzeitumgebung ist ein Interpreter oder JIT-Compiler für diesen Maschinencode -> analog dazu Frontend/Backend-Aufteilung innerhalb eines Compilers

                                                                                              • Frontend: Umformen der Texteingabe in eine Datenstruktur, Prüfung dieser Struktur auf inhaltliche Korrektheit (maschinenunabhängig, aber sprachabhängig)

                                                                                                • lexikalische Analyse: Zerteilen des Eingabetextes in eine Folge von Tokens mittels regulärer Ausdrücke (siehe STP021; diese Vorstufe ist eine Optimierung, weil reguläre Ausdrücke schneller ausgewertet werden können)
                                                                                                • syntaktische Analyse: Umformen der Tokenliste in einen Syntaxbaum mittels eines kontextfreien Parsers (siehe Beispiel bei Wikipedia)
                                                                                                • semantische Analyse: Prüfen des Syntaxbaums auf inhaltliche Korrektheit, meist mittels Markierungen an jedem Knoten des Baums (z.B. Welchen Typ hat der hier berechnete Wert? Passen die Werte des Elternknotens bzw. des Kindknotens dazu? etc.)
                                                                                                • IR-Erzeugung: Umformung des Syntaxbaums in eine Intermediate Representation (IR), die sich für maschinenunabhängige Optimierung eignet

                                                                                                • Fortsetzung des Beispiels aus Wikipedia (aber mit einer Eingabevariable y und Ausgabevariable x): mögliche IR für den Ausdruck x = y + (2 + 2) - sin(pi)

                                                                                                  $1 = 2
                                                                                                  $2 = $1 + $1
                                                                                                  $3 = load %y
                                                                                                  $4 = $3 + $2
                                                                                                  $5 = pi
                                                                                                  $6 = call sin($5)
                                                                                                  $7 = $4 - $6
                                                                                                  store %x, $7

                                                                                                  • Middleend: Optimierungsläufe auf IR (Auswahl)

                                                                                                    • Statische Formelauswertung: z.B. oben statt $2 = $1 + $1 direkt $2 = 4
                                                                                                    • Löschung von unerreichbarem Code: sehr einfach bei IR mit Static Single Assignment (SSA) wie im Beispiel
                                                                                                    • Invariantenextraktion aus Schleifen: wenn z.B. für verschiedene Werte von x der Ausdruck sin(x) + cos(y) berechnet wird, so kann man cos(y) vor der Schleife ein einziges Mal berechnen und das Zwischenergebnis wiederverwenden
                                                                                                    • Inlining: ist eine Funktion sehr kurz, kann es effizienter sein, einen Funktionsaufruf durch eine Kopie der Funktion zu ersetzen (insb. wenn dann weitere Optimierungen möglich werden)

                                                                                                    • Beispiel: optimierte Variante der IR von oben

                                                                                                      $3 = load %y
                                                                                                      $7 = $3 + 4
                                                                                                      store %x, $7
                                                                                                      • Backend: Umwandlung der maschinenunabhängigen IR in tatsächlichen Maschinencode
                                                                                                        • Codeauswahl: für die einzelnen Operationen Auswahl der besten Maschinenbefehle
                                                                                                          • je nach Optimierungsziel: Geschwindigkeit, Speicherverbrauch, Energieverbrauch, etc. (z.B. x * 3 kann je nach Maschinenarchitektur gewinnbringend durch x + x + x ersetzt werden)
                                                                                                          • schwieriger als gedacht wegen komplexen Befehlen (z.B. SIMD: Single Instruction Multiple Data)
                                                                                                          • Registerzuweisung: nummerierte Register aus der IR ersetzen durch die tatsächlich in der Maschine verfügbaren Register
                                                                                                            • reduzierbar auf ein Graphenfärbungsproblem: Knoten = IR-Register, Kanten = gemeinsame Verwendung in Berechnungen, Farben = echte Register
                                                                                                            • Scheduling: optimale Sortierung der einzelnen Maschinenbefehle (soweit umordenbar)
                                                                                                              • z.B. parallele Ausnutzung verschiedener Recheneinheiten in der CPU (für Ganzzahl- und Fließkommazahl-Operationen)
                                                                                                              • maschinenabhängige Optimierungen (aus Zeitgründen hier nicht)
                                                                                                                • 1 hr 10 min
                                                                                                              • STP033: Programmiersprachen

                                                                                                                In dieser Episode wird die Antwort auf die Frage geliefert, warum wir Dinge wie Programmiersprachen brauchen, und vor allem, warum so viele. Es werden mal wieder starke Meinungen geäußert und es gibt einen zweiten Prolog in der Mitte der Episode. :)

                                                                                                                Außerdem dabei: Linguisten, automatisierte Textilbearbeitung und unsichtbarer Programmcode.

                                                                                                                Shownotes

                                                                                                                • Einordnung in das Sprachenuniversum

                                                                                                                  • Programmiersprachen sind formale Sprachen (d.h. ein Algorithmus kann in endlicher Zeit eindeutig entscheiden, ob ein gegebener Text Teil der Sprache ist) -> Rückbezug zu STP021
                                                                                                                  • Programmiersprachen sind kein Maschinencode (d.h. Programme in Bytefolgen, den ein Prozessor direkt ausführen kann) -> Rückbezug zu STP011
                                                                                                                  • Abwägung zwischen Lesbarkeit für den Menschen und Lesbarkeit für den Computer
                                                                                                                  • einfachste Form von Programmiersprachen: Maschinensprachen (stellen Maschinencode direkt lesbar dar)

                                                                                                                  • Beispiel anhand einer frühen Anwendung von Programmierbarkeit: Weben/Stricken/Häkeln

                                                                                                                    • Maschinensprache: so etwas wie "zwei links, zwei rechts, zwei fallen lassen"
                                                                                                                    • Maschinencode = Lochkarten-Kette für einen Jacquard-Webstuhl

                                                                                                                    • darstellendes Beispiel für moderne Maschinensprachen und Programmiersprachen: Fibonacci-Funktion

                                                                                                                      • interaktiv bei Godbolt
                                                                                                                      • reine Textform nachfolgend
                                                                                                                        • unsigned int fibonacci(unsigned int x) {
                                                                                                                        if (x == 0 || x == 1) {
                                                                                                                        return x;
                                                                                                                        }
                                                                                                                        return fibonacci(x - 1) + fibonacci(x - 2);
                                                                                                                        }
                                                                                                                        fibonacci(unsigned int):
                                                                                                                        push rbp
                                                                                                                        mov rbp, rsp
                                                                                                                        push rbx
                                                                                                                        sub rsp, 24
                                                                                                                        mov DWORD PTR [rbp-20], edi
                                                                                                                        cmp DWORD PTR [rbp-20], 0
                                                                                                                        je .L2
                                                                                                                        cmp DWORD PTR [rbp-20], 1
                                                                                                                        jne .L3
                                                                                                                        .L2:
                                                                                                                        mov eax, DWORD PTR [rbp-20]
                                                                                                                        jmp .L4
                                                                                                                        .L3:
                                                                                                                        mov eax, DWORD PTR [rbp-20]
                                                                                                                        sub eax, 1
                                                                                                                        mov edi, eax
                                                                                                                        call fibonacci(unsigned int)
                                                                                                                        mov ebx, eax
                                                                                                                        mov eax, DWORD PTR [rbp-20]
                                                                                                                        sub eax, 2
                                                                                                                        mov edi, eax
                                                                                                                        call fibonacci(unsigned int)
                                                                                                                        add eax, ebx
                                                                                                                        .L4:
                                                                                                                        mov rbx, QWORD PTR [rbp-8]
                                                                                                                        leave
                                                                                                                        ret

                                                                                                                        • Was unterscheidet hier die Programmiersprache von der Maschinensprache?

                                                                                                                          • Verwendung von benannten Variablen, um Werte zu halten
                                                                                                                            • Maschinensprache: nur Speicheradressen und CPU-Register
                                                                                                                            • Variablen können feste Datentypen haben
                                                                                                                              • Maschinensprache: alles nur Nullen und Einsen :)
                                                                                                                              • Kontrollfluss-Strukturen (Subprozeduren, Abzweigungen, Schleifen)
                                                                                                                                • Maschinensprache: nur lineare Ausführung und Sprungbefehle
                                                                                                                                • allgemein:
                                                                                                                                  • bessere Lesbarkeit (immerhin kann Maschinensprache heutzutage auch Freitext-Kommentare)
                                                                                                                                  • Portabilität (Unabhängigkeit von Details einer bestimmten Maschinen-Architektur)
                                                                                                                                  • formale Strukturen, die Fehler vermeiden (z.B. Typprüfungen, Kollisionsvermeidung bei nebenläufigen Programmen)

                                                                                                                                  • Arten von Programmiersprachen ("Paradigma")

                                                                                                                                    • imperative Programmierung: Programme als Folgen von Befehlen
                                                                                                                                    • strukturierte Programmierung: Programme als ineinander verschachtelte Blöcke von Befehlsfolgen
                                                                                                                                    • modulare Programmierung: Programme als Verbund logischer Einheiten aus Prozeduren und Datenstrukturen
                                                                                                                                    • objektorientierte Programmierung: Programme als Verbund von datenhaltenden Objekten, die miteinander interagieren
                                                                                                                                    • logische Programmierung: Programme als Verbund von logischen Aussagen und Ableitungsregeln (Beispiele in der Sprache Prolog; Xyrill hat eine Anekdote zu Prolog)
                                                                                                                                    • funktionale Programmierung: Programme als Verbund von mathematischen Funktionen (insbesondere von Funktionen, die andere Funktionen als Werte nehmen)
                                                                                                                                      • Beispiel unten: Berechnung sämtlicher Primzahlen in der Sprache Haskell
                                                                                                                                      • reaktive Programmierung: Programme als voneinander abhängige Berechnungen (Beispiel: Tabellenkalkulation, Webanwendungen mit React)
                                                                                                                                        • module Primes where
                                                                                                                                        isPrime :: Int -> Bool
                                                                                                                                        isPrime x = all (\y -> mod x y /= 0) $ takeWhile (\y -> y * y <= x) primes
                                                                                                                                        primes :: [Int]
                                                                                                                                        primes = 2 : filter isPrime [3..]

                                                                                                                                        • Exkurs: esoterische Programmiersprachen

                                                                                                                                          • Brainfuck: eine der minimalsten turing-vollständigen Programmiersprache; nur 8 verschiedene Befehle
                                                                                                                                          • Befunge: anschauliches Beispiel für das Konzept einer "virtuellen Maschine" im Kontext von Programmiersprachen
                                                                                                                                          • Chef: viele esoterische Programmiersprachen sind vor allem clevere Textersetzung

                                                                                                                                          • Im Gespräch erwähnt

                                                                                                                                            • Pentaradio 2022-12 zu Komplexität
                                                                                                                                              • 1 hr 38 min
                                                                                                                                            • STP032: Hochverfügbarer Softwarebetrieb

                                                                                                                                              Die heutige Episode beschäftigt sich neben dem offensichtlichen Hauptthema auch mit Prozenten, deren Bedeutung bedacht sein sollte, und dem Verhalten guter Manager.

                                                                                                                                              Deshalb sei hiermit eine Politik-Triggerwarnung ausgesprochen... aber nur eine kleine.

                                                                                                                                              Shownotes

                                                                                                                                              • Schlagwort: Site Reliability Engineering (SRE)

                                                                                                                                                • Hauptziel: "Schaffung skalierbarer und hochzuverlässiger Softwaresysteme"

                                                                                                                                                • Grundkonzept: Service Level

                                                                                                                                                  • SLO (Service Level Objective): selbstgewählter Indikator soll bis zu einem bestimmten Grad an 100% herangeführt werden (z.B. Zeiten, zu denen der Dienst erreichbar ist; Anteil der Anfragen, die in weniger als 1 Sekunde beantwortet werden; Anteil der Anfragen, die erfolgreich beantwortet werden)
                                                                                                                                                  • SLA (Service Level Agreement): SLO, der mit dem Kunden vertraglich vereinbart ist
                                                                                                                                                  • Beispiel: 99% Verfügbarkeit = bis zu 3,65 Tage Ausfall; 99,9% = bis zu 8,77 Stunden; 99,99% = bis zu 52 Minuten; 99,999% = bis zu 5,2 Minuten

                                                                                                                                                  • Problem: die Unbekannten in der Gleichung

                                                                                                                                                    • Known Unknowns (bekanntes Unwissen): ich weiß, dass ich etwas nicht weiß (z.B. wann meine Festplatte ausfallen wird)
                                                                                                                                                    • Unknown Unknowns (unbekanntes Unwissen): ich weiß nicht mal, dass da etwas ist, was ich nicht weiß (z.B. dass meine angebliche 30-TB-Festplatte in Wahrheit nur eine 32-GB-Speicherkarte in einem großen Gehäuse ist)
                                                                                                                                                    • siehe auch: zur Wortherkunft der Begriffsgruppe "(un)known (un)knowns"

                                                                                                                                                    • strukturierter Einblick in Applikationen mittels Instrumentierung

                                                                                                                                                      • Logging: Ereignisse innerhalb der Applikation werden als textförmiger Bericht (Log) aus der Applikation ausgeleitet und in einem Log-System durchsuchbar gemacht
                                                                                                                                                      • Monitoring: Zustand der Applikation wird in Form von Messdaten quantifiziert, in einer Zeitseriendatenbank abgelegt und in Dashboards aufbereitet (Beispielbild); Messdaten entweder direkt aus der Applikation selbst oder durch ein Extraprogramm von außen erhoben
                                                                                                                                                      • Alarmierung: Menschen werden benachrichtigt, wenn ein bestimmter Messwert eine bestimmte Schwelle überschreitet (oder eine Überschreitung projiziert ist, z.B. "die Festplatte läuft gerade voll und in einer Stunde ist sie komplett voll")

                                                                                                                                                      • strukturierte Herangehensweisen beim Durchführen von Änderungen

                                                                                                                                                        • Configuration as Code: Änderungen werden möglichst nie manuell vorgenommen, sondern es wird ein Programm geschrieben (bzw. die Konfiguration für jenes Program angepasst), das die Änderungen vornimmt; bei Problemen ist ein Zurückrollen auf den letzten funktionierenden Zustand möglich
                                                                                                                                                        • Continuous Integration (CI): Änderungen an Code und Konfiguration fließen in ein System, das automatisch standardisierte Tests ausführt, um die Änderung auf Fehler zu prüfen; bei Erfolg automatische Übernahme der vorgeschlagenen Änderung in den veröffentlichten Code-Stand
                                                                                                                                                        • Continuous Delivery (CD): automatisches oder stark automatisiertes Ausrollen von Änderungen an Code und Konfiguration von Testsystemen in Verifikationssysteme in Produktivsysteme
                                                                                                                                                        • Rolling Upgrade: bei Systemen mit mehreren gleichartigen Komponenten werden die Komponenten nacheinander durch die neue Version ersetzt, damit das Ausrollen für den Kunden unsichtbar ist und bei Fehlern frühzeitig gestopppt werden kann
                                                                                                                                                        • Canary Deployment: Ausrollen einer Änderung zunächst nur in einem kleinen Teil des Systems; bei Problemen ist nur der kleine Teil betroffen (siehe auch Ankündigungen der Form "diese Funktion ist zurzeit nur für ausgewählte Kunden verfügbar")

                                                                                                                                                        • strukturierter Umgang mit Alarmen/Fehlern

                                                                                                                                                          • standardisierte Abläufe ("Playbooks") für Alarme
                                                                                                                                                          • Postmortem-Analyse mindestens nach signifikanten Fehlern (Was ist passiert? Was war der tatsächliche Grund? Was ist bei der Bekämpfung des Problems gut/schlecht gelaufen? Was können wir besser machen?)
                                                                                                                                                          • Fehlerkultur: Das Hauptziel soll nicht sein, einen Schuldigen zu finden, sondern das Problem möglichst schnell zu beheben und dann dafür zu sorgen, dass das Problem nie wieder auftritt.
                                                                                                                                                          • Parallelen zum Toyota-Produktionssystem

                                                                                                                                                          • im Gespräch erwähnt (im Kontext des Gesetzesvorhabens zur Chatkontrolle):

                                                                                                                                                            • Pentaradio vom Mai 2022 und ganz aktuell vom Januar 2023
                                                                                                                                                            • LNP429: Endlich sind wir am Anfang angekommen
                                                                                                                                                            • LNP430: Die größte Koalition aller Zeiten
                                                                                                                                                              • 1 hr 16 min
                                                                                                                                                            • STP031: Festplatten und Dateisysteme

                                                                                                                                                              Mit dieser Episode kehrt STP zum Ursprung zurück, denn das initiale Ereignis hatte ebenfalls mit Dateisystemen zu tun.

                                                                                                                                                              Hier sprechen wir aber über deutlich mehr und auch andere Sachen. Darunter: Dinge, von denen Xyrill wenig bis keine Ahnung hat (physikalische Anschlüsse) und Dinge, von denen Xyrill deutlich mehr Ahnung hat (die Software dahinter und deren Verwendung). ttimeless raschelt derweil mit einer dicken Winterjacke.

                                                                                                                                                              Shownotes

                                                                                                                                                              • blockbasierter Speicher ("Block Storage")

                                                                                                                                                                • Festplatten handeln immer nur in festen Einheiten (Blöcken)
                                                                                                                                                                • traditionellerweise 512 Byte, heutzutage 4 KiB

                                                                                                                                                                • kurzer Überblick zur physikalischen Anbindungen blockbasierter Speicher

                                                                                                                                                                  • USB (Universal Serial Bus): für externe Festplatten, CD-Laufwerke, *räusper* Mini-Raketenwerfer *räusper*, etc.
                                                                                                                                                                  • SATA (Serial AT Attachment): für interne Festplatten, kabelgebundene Punkt-zu-Punkt-Verbindungen
                                                                                                                                                                  • SAS (Serial Attached SCSI): für interne Festplatten, kabelgebundene Verbindungen auch mit Switching (mehrere Festplatten an einem Verteiler)
                                                                                                                                                                  • NVMe (Non-Volatile Memory Express): für interne Festplatten, direkte Steckverbindung via PCI Express
                                                                                                                                                                  • Warum alles immer seriell? Höhere Geschwindigkeiten = Synchronisierung immer schwieriger. Parallele Leitungen = Übersprechen/Interferenz = komplexe Kompensation notwendig bzw. bei flexiblen Systemen wie Kabeln nicht möglich.

                                                                                                                                                                  • Rückbezug zu STP012: "Dateisysteme sind eine besondere Form von Key-Value-Datenbank"; keine Datenbank im engeren Sinne:

                                                                                                                                                                    • keine widerspruchsfreie Speicherung, da keine Beziehungen zwischen verschiedenen Dateien möglich
                                                                                                                                                                    • keine Unterstützung für bedarfsgerechte Darstellungsformen; jede Datei hat genau ein Format

                                                                                                                                                                    • alternative Perspektive als Vergleich zum blockbasierten Speicher

                                                                                                                                                                      • jede Datei ist ihr eigener "kleiner Massenspeicher"
                                                                                                                                                                      • zusätzlich noch Metadaten (Dateiname, Erstelldatum, Zugriffsrechte, etc.)
                                                                                                                                                                      • Dateisystem kümmert sich um die Zuteilung des tatsächlichen blockbasierten Speichers an die einzelnen Dateien
                                                                                                                                                                      • Praxisbeispiel zur Zuteilung von Speicherplatz: Unix-Befehl du -h ("disk usage")

                                                                                                                                                                      • Dateisystem-Struktur unter unixoiden Betriebssystemen: mittels Inodes

                                                                                                                                                                        • ein Inode enthält alle Metadaten zu einem bestimmten Dateisystemeintrag (einer Datei, einem Verzeichnis, einer Verknüpfung, etc.) sowie (bei normalen Dateien) einen Verweis auf den Speicherort der tatsächlichen Daten
                                                                                                                                                                        • Größe eines Inodes: immer ein Vielfaches der Blockgröße (4 KiB, 8 KiB, etc.)
                                                                                                                                                                        • bei sehr kleinen Dateien mitunter direktes Ablegen des Dateiinhaltes im Inode
                                                                                                                                                                        • bei großen Dateien meist fragmentierter Inhalt: Ablage in mehreren separaten Stücken (wegen späterer Umschreibung oder wegen Platzmangel)
                                                                                                                                                                        • Verzeichnisse: Inode mit einer Liste von Einträgen (Name + Inode-Verweis)
                                                                                                                                                                        • Dateisystem = Inode-Liste + Dateiinhalte + Übersicht über noch freie Festplattenbereiche

                                                                                                                                                                        • "aktuelle" Entwicklungen in Dateisystemen

                                                                                                                                                                          • Journaling (in NTFS seit 1993, in ext3 seit 2001): Transaktionen werden in einem separaten Festplattenbereich vorgemerkt, bevor sie tatsächlich ausgeführt werden; ermöglicht Abgeschlossenheit und Dauerhaftigkeit analog zum Write-Ahead-Log bei Datenbanken (siehe STP012), außerdem schnelleren Start nach Systemausfall (keine Komplettprüfung des Dateisystems nötig)
                                                                                                                                                                          • Online-Defragmentierung bzw. optimierte Speicherzuteilung zur Vermeidung von Fragmentierung (aber: aktives Defragmentieren = mehr Schreibzyklen = mehr Abnutzung)

                                                                                                                                                                          • antiintuitive Schlussfolgerungen aus dieser Struktur

                                                                                                                                                                            • "sicheres Löschen": einfaches Löschen einer Datei löscht nur den Inode, aber überschreibt nicht den Inhalt (selbst Überschreiben der Datei hilft nicht unbedingt, weil die neuen Daten vielleicht an einer anderen Stelle landen, oder weil die alten Daten trotzdem noch im Journal liegen)
                                                                                                                                                                            • Löschen von im Verbrauch befindlichen Dateien: kein Problem, eine "geöffnete Datei" ist nur ein Verweis auf einen Inode; "Löschen der Datei" löscht nur den Verzeichnis-Eintrag; der Inode bleibt noch so lang bestehen, wie ein Prozess einen Verweis auf den Inode hält
                                                                                                                                                                            • anders bei Windows: Verweis auf eine offene Datei blockiert das Löschen -> Konsequenzen für System-Updates

                                                                                                                                                                            • Exkurs 1: virtuelles Dateisystem

                                                                                                                                                                              • bis hier: physikalische Perspektive (Welche Bits stehen tatsächlich auf der Platte?)
                                                                                                                                                                              • jetzt: logische Perspektive (Was zeigt das Betriebssystem den Programmen?)
                                                                                                                                                                              • Unix: ein einziger Verzeichnisbaum, in das die verschiedenen Dateisysteme eingehängt werden können; anders als das System mit Laufwerksbuchstaben unter Windows
                                                                                                                                                                              • "Datei" und "Verzeichnis" als abstrakte Konzepte, die u.a. durch echte Dateisysteme abgebildet werden können, oder auch durch was anderes (vgl. "Everything is a file.")
                                                                                                                                                                              • Beispiel: procfs
                                                                                                                                                                              • Beispiel: sshfs
                                                                                                                                                                              • Beispiel: transparente Behandlung von Zip-Archiven im Windows Explorer
                                                                                                                                                                              • Beispiel: /dev/random etc.

                                                                                                                                                                              • Exkurs 2: Festplattenverschlüsselung

                                                                                                                                                                                • Option 1: auf der Ebene des Dateisystems (einzelne Dateien oder Verzeichnisse werden verschlüsselt)
                                                                                                                                                                                • Option 2: auf der Ebene des blockbasierten Speichers -> Dateisystem sieht als Speichermedium einen virtuellen blockbasierten Speicher, der die Verschlüsselung vornimmt und erst dann auf den tatsächlichen blockbasierten Speicher schreibt -> schöne Arbeitsteilung
                                                                                                                                                                                • andere Anwendungsfälle für virtuelle blockbasierte Speicher: Netzwerklaufwerke, Dateisysteme innerhalb von Dateien
                                                                                                                                                                                  • 1 hr 43 min
                                                                                                                                                                                • STP030: Arbeitsalltag in der IT

                                                                                                                                                                                  In dieser etwas länger geratenen Episode sricht Xyrill über seinen Alltag und den seiner Kollegen, Unterstellten und Vorgesetzten.

                                                                                                                                                                                  Derweil darf ttimeless darf derweil munter drauflosraten, womit diese Leute denn so ihren Alltag verbringen (zumindest den professionellen).

                                                                                                                                                                                  Shownotes

                                                                                                                                                                                  • Ausgangsfrage: "Ist Programmieren eigentlich ein Handwerk, eine Kunst oder eine Wissenschaft?"

                                                                                                                                                                                    • vgl. Artes mechanicae und Artes liberales
                                                                                                                                                                                    • im Gespräch erwähnt: xkcd 1205
                                                                                                                                                                                    • Vergleich: Industrie (effiziente Massenfertigung) vs. Handwerk (Nutzer der Industrieprodukte, Lieferant der Industrieanlagen) -> These: Programmieren als Manufakturbetrieb
                                                                                                                                                                                    • Berufskrankheit: Hochstapler-Syndrom
                                                                                                                                                                                      • These: Internet verschafft den fähigsten Leuten sehr viel Sichtbarkeit und schafft Gelegenheit, sich relativ dazu inadäquat zu fühlen
                                                                                                                                                                                      • These: Grund ist die Abwesenheit festgelegter Berufsbilder und Ausbildungsgänge (vgl. Lehre und Meisterschule im Handwerk, Studium im Ingenieurwesen, Staatsexamen in Jura/Medizin)

                                                                                                                                                                                      • grundsätzliche Gewerke in der IT

                                                                                                                                                                                        • technische Disziplinen
                                                                                                                                                                                          • Software-Entwickler*in
                                                                                                                                                                                          • Software-Architekt*in
                                                                                                                                                                                          • Tester*in
                                                                                                                                                                                            • im Gespräch erwähnt: Pentaradio zu Resilienz
                                                                                                                                                                                            • Systemadministrator*in: siehe auch DevOps
                                                                                                                                                                                            • Kundendienst: Level 1/2/3
                                                                                                                                                                                              • im Gespräch erwähnt: xkcd 806
                                                                                                                                                                                              • Übersetzer*in (siehe STP017)
                                                                                                                                                                                              • Designdisziplinen
                                                                                                                                                                                                • bei fast allen Applikationen: UI-Designer*in
                                                                                                                                                                                                • in der Spieleentwicklung: Spieldesign, Leveldesign, Assetdesign
                                                                                                                                                                                                • Management-Disziplinen
                                                                                                                                                                                                  • Projekt-Manager*in
                                                                                                                                                                                                  • Release-Manager*in
                                                                                                                                                                                                  • Scrum Master*in

                                                                                                                                                                                                  • "Gesetze" der Softwareentwicklung

                                                                                                                                                                                                    • Conway's Law: "Any organization that designs a system will produce a design whose structure is a copy of the organization's communication structure."
                                                                                                                                                                                                    • Brooks's Law: "Adding manpower to a late software project makes it later."
                                                                                                                                                                                                    • Zawinski's Law: "Every program attempts to expand until it can send mail. Those programs which cannot so expand are replaced by ones which can." (heute wahrscheinlich eher "until it contains a web server")
                                                                                                                                                                                                    • Parkinson's Law: "Work expands so as to fill the time available for its completion."
                                                                                                                                                                                                    • Pareto's Fallacy: "When you're 80% done, you think you only have 20% left."
                                                                                                                                                                                                    • Eagleson's Law: "Any code of your own that you haven't looked at for six or more months might as well have been written by someone else."
                                                                                                                                                                                                    • Iceberg Fallacy: "The cost of development of a new software product is the only ~25% of the total cost of ownership management sees and budgets for."
                                                                                                                                                                                                    • The LGTM Dilemma: "If you want to quickly ship a 10 line code change, hide it in a 1500 line pull request."

                                                                                                                                                                                                    • Lesetipp: "Everything Easy is Hard Again"

                                                                                                                                                                                                      • Money Quote: "I wonder if I have twenty years of experience making websites, or if it is really five years of experience, repeated four times."
                                                                                                                                                                                                      • Xyrills Beobachtung: Die Branche (selbst die Universitäten!) rennt viel zu sehr Trends hinterher bzw. steckt zu sehr im selbst propagierten Novelty Bias fest. Wir haben noch nicht hinreichend die unveränderlichen Prinzipien destilliert (bzw. als solche erkannt).
                                                                                                                                                                                                        • 1 hr 42 min
                                                                                                                                                                                                      • STP029: Algorithmische Komplexität

                                                                                                                                                                                                        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?
                                                                                                                                                                                                                          • 1 hr 7 min

                                                                                                                                                                                                                        About Schlüsseltechnologie

                                                                                                                                                                                                                        From the publisher's feed

                                                                                                                                                                                                                        Die IT hat unser Leben in den letzten Jahrzehnten von Grund auf verändert. Aber wie funktioniert sie wirklich? Das möchte ttimeless mal erklärt bekommen. Zum Glück hat Xyrill Antworten.

                                                                                                                                                                                                                        More shows like Schlüsseltechnologie

                                                                                                                                                                                                                        Freak Show by Metaebene Personal Media - Tim Pritlove

                                                                                                                                                                                                                        Freak Show

                                                                                                                                                                                                                        9 Listeners

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

                                                                                                                                                                                                                        Lage der Nation - der Politik-Podcast aus Berlin

                                                                                                                                                                                                                        219 Listeners

                                                                                                                                                                                                                        Logbuch:Netzpolitik by Metaebene Personal Media - Tim Pritlove

                                                                                                                                                                                                                        Logbuch:Netzpolitik

                                                                                                                                                                                                                        5 Listeners