Überblick

Informatik: was und warum?

Algorithmus und Programm

Zum Algorithmus von Euklid

Sortiernetze

Gliederung dieser VL (Plan)

Quellen

Organisation dieser LV

Hausaufgaben (ohne Wertung)

Hausaufgaben (zur Bewertung in KW 42)

  1. Lesen Sie die angegebene Literatur im Browser, beginnen Sie mit der Suche im Katalog unserer Bibliothek.

    In diesem Buch von Gumm/Sommer werden Eigenschaften für einen durchschnittlich ausgestatteten PC für unter 1000 EUR angegeben, die bei Drucklegung typisch waren.

    Vergleichen Sie mit PCs von heute (für ähnlichen Preis).

    Vergleichen Sie mit entsprechenden Angaben in früheren Ausgaben dieses Buches.

    Vergleichen Sie mit aktuellem Mobiltelefon.

    Vergleichen Sie mit dem Bordcomputer von Apollo 11. Geben Sie für dessen Daten eine verläßliche Quelle an (möglichs eine primäre) (Wikipedia ist niemals Primärquelle, deswegen nicht zitierfähig, kann aber gelegentlich benutzt werden, um eine solche zu finden)

  2. zum Algorithmus von Euklid:

    Das Verfahren vorführen (a) für Eingabe \(30, 12\) (b) für Eingaben, die erst dann in der Ü genannt werden.

    Dabei die Eigenschaften \(\operatorname{\textsf{ggT}}(x_0,y_0)=\operatorname{\textsf{ggT}}(x_i,y_i)\) überprüfen: jeweils die Menge der Teiler von \(x_i\), von \(y_i\), und die gemeinsamen Teiler angeben.

    Warum müssen die Eingaben positiv sein? (Was passiert sonst?)

    Geben Sie Eingaben an, für die größere Zahl in jedem Schritt wechselt \((x_0, y_1, x_2, \dots)\), insgesamt genau 5 Subtraktionen stattfinden und das Resultat 1 ist.

    (Beziehungen zur LV: 1. Analyse von Programmen mit Schleifen, 2. dieser Algorithmus gehört zum Kulturerbe der Menschheit, 3. wird zur Implementierung von Verschlüsselungs- und Signier-Verfahren benutzt: HTTPS, RSA, SSH)

  3. Diskutieren Sie das Netz

    • die Rechnung durchführen für eine Eingabe (a) von Ihnen gewählt, (b) von mir gewählt.

    • warum ist das kein Sortiernetz? (eine Eingabe zeigen, für die die Ausgabe nicht monoton ist)

    • das Netz reparieren durch Hinzufügen eines Komparators (die vorhandenen nicht ändern), die Korrektheit der Reparatur begründen (mit Methode aus der VL: wo sind min und max?)

    • verallgemeinern auf Breite 6, 8, …\(2n\). Wieviele Komparatoren?

      (Die Form läßt sich leicht verallgemeinern, der Korrektheitsbeweis ist aber schwierig—müssen Sie nicht unbedingt führen)

Die Überwachungswirtschaft

Überblick

Datenvermeidung beim Browsen

Sogenannte Content-Plattformen

Information und Daten

Überblick

Zahlendarstellungen

Überblick

Darstellung natürlicher Zahlen

Rechnen in Positionssystemen

Maschinenzahlen (Binärzahlen fester Breite)

Ganze Zahlen als Maschinenzahlen

Vorzeichenwechsel

Darstellung rationaler Zahlen

Darstellbare rationale Zahlen

Bestimmung der Gleitkomma-Darstellung

Fehlerquellen bei Gleitkomma-Rechnungen

Zusammenfassung Zahlendarstellungen

Hausaufgaben

  1. wieviele Bit (in Text-Dokumenten) werden an der HTWK pro Semester insgesamt im Zusammenhang mit Lehrveranstaltungen erzeugt?

    Was kostet es, diese abzuspeichern (bei aktuellen Preisen für HDD oder SSD)? — Antwort: fast nichts, teuer ist nicht das Abspeichern, sonder das Herstellen (die Arbeitszeit)

    Geben Sie eine begründete Schätzung an, ausgehend von dieser LV. Ergänzen, diskutieren, verwenden Sie diese Schätzungen:

    • 8 Bit (\(=\) 1 Byte) pro Zeichen

    • Zeichen pro Zeile

    • Zeilen pro Folie

    • Folien pro Vorlesung

    • Vorlesungswochen im Semester

    • Vorlesungen je Professor und Semester

    • Professoren je Fakultät

    • Fakultäten

    Bestimmen Sie vernünftige untere und obere Schranken für jeden einzelnen Schätzwert und für das daraus berechnete Resultat.

  2. für Binärzahlen der Breite 6:

    • stellen Sie dar: \(5, 7\)

    • berechnen Sie: \(5+7, 5 \cdot 7\)

    für Binärzahlen der Breite 6 im Zweierkomplement:

    • stellen Sie dar: \(5, 11, 18, -18\),

    • berechnen Sie: \(11+18\) und \(11-18\),

    überprüfen Sie alle Resultate durch Rechnung im Dezimalsystem.

  3. Die Maßzahl einer physikalischen Größe soll mit höchstens 0.5 Prozent relativem Fehler dargestellt werden.

    Wieviele Stellen muß die Mantisse der normierten binären Gleitkomma-Darstellung dafür wenigstens haben?

    Für normierte binäre Gleitkommazahlen mit 4 Bit für Mantisse, 4 Bit für Exponent:

    Nenne Sie die größte, kleinste, kleinste positive darstellbare Zahl.

    Wir bezeichnen mit \(D(x)\) die zu \(x\) nächstliegende darstellbare Zahl.

    • bestimmen Sie \(D(59), D(75)\).

    • welche Auswirkung hat jeweils die Änderung der letzten Stelle der Mantisse?

    • vergleichen Sie \(D(75) - D(59)\) mit \(D(75-59)\).

  4. (Zusatz—ohne Wertung) Tragen Sie Ziffern 1 bis 5 ein, so daß ein korrektes Multiplikations-Schema entsteht:

            x x x x x 
      . x x x x x
-----------------
      x x x x x x
      x x x x x
  x x x x x x
  x x x x x
x x x x x  
-----------------
x x x x x x x x x

Rechnen mit Wahrheitswerten

Einleitung, Motivation

Wahrheitswerte und Funktionen

Wertetabellen

Null- und einstellige Boolesche Funktionen

Zwei- und mehrstellige Boolesche Funktionen

Rechenregeln

Boolesche Ausdrücke (Terme)

Auswertung von Termen

Eigenschaften von Booleschen Termen

Basis-Funktionen, Standard-Basis

Standard-Basis (Beweis-Idee), Disjunktive NF

Schaltungen

Schaltung für binäre Addition

Eine Basis mit einem Element

Die Funktion \(\operatorname{\textsf{Nand}}: (x,y) \mapsto ~\neg(x \wedge y)\) bildet eine Basis.

\[\begin{array}{cc|c|c} x & y & x \wedge y & \operatorname{\textsf{Nand}}(x,y) \\ \hline 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array}\]

Beweis: wir können diese Funktionen darstellen:

…und nach vorigem Basis-Satz auch alle anderen Ftk.

nand in Hardware

Aufgaben

WS21: Aufgaben 1 bis 3

  1. für den Term \((\neg x \vee y)\wedge (z\to x)\):

    • den Syntaxbaum angeben,

    • den Wahrheitswert unter der Belegung \(\{(x,0),(y,1),(z,1)\}\) angeben

    • die Wertertabelle der durch diesen Term beschriebenen dreistelligen aussagenlogischen Funktion angeben.

    • ist der Term allgemeingültig? erfüllbar? widersprüchlich?

    • einen äquivalenten Term in der Standard-Basis angeben.

  2. Eine zweistellige Funktion \(f\) heißt assoziativ,
    wenn für alle \(x,y,z\) gilt: \(f(f(x,y),z)=f(x,f(y,z))\).

    Stellen Sie mittels Wertetabellen fest,
    ob diese zweistelligen Funktionen assoziativ sind:

    a) Antivalenz, b) Implikation, c) Nand.

    Sind die Terme \(\operatorname{\textsf{Maj}}(\operatorname{\textsf{Maj}}(x_1,x_2,x_3),\operatorname{\textsf{Maj}}(x_4,x_5,x_6),\operatorname{\textsf{Maj}}(x_7,x_8,x_9))\) und \(\operatorname{\textsf{Maj}}(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9)\) äquivalent?

    (Wieviele Zeilen hat die Wertetabelle? Man kann die Aufgabe lösen, ohne diese Tabelle komplett hinzuschreiben.)

  3. Für \(\operatorname{\textsf{Maj}}(x_1,x_2,x_3,x_4,x_5)\) an:

    • wieviele Klauseln enthält die disjunktive Normalform? (systematisch abzählen oder ausrechnen, Klauseln nicht alle einzeln aufschreiben)

    • einen (möglichst kleinen) äquivalenten Term in der Standard-Basis angeben

    • eine (möglichst kleine) äquivalente Boolesche Schaltung in der Standard-Basis angeben

    • verallgemeinern Sie die Schaltung auf \(\operatorname{\textsf{Maj}}(x_1,\ldots, x_7)\) und evtl. größere.

  4. Begründen Sie, daß die Menge der Funktionen

    \(\{\) Implikation (2-stellig), 0 (0-stellig) \(\}\)

    eine Basis bildet. Stellen Sie

    a) die 2-stellige Konjunktion, b) die 3-stellige Disjunktion

    in dieser Basis dar.

  5. (Zusatz) Sieben Zwerge \(1,2,\dots,7\) bekommen im Schlaf je einen Hut auf den Kopf gesetzt, der blau oder rot ist.

    Die Zwerge wachen auf.

    Jeder Zwerg \(i\) sieht alle mit kleinerer Nummer als \(i\). (Das bedeutet unter anderem: Zwerg 1 sieht niemanden. Zwerg 7 wird von niemandem gesehen. Niemand sieht seinen eigenen Hut.)

    Nun soll (in irgendeiner Reihenfolge) jeder Zwerg laut (d.h., hörbar für alle) eine Farbe (blau oder rot) nennen. (Wirklich nur dieses eine Bit Information, keine versteckten Nachrichten.)

    Die Zwerge sollen vor dem Schlafengehen einen Algorithmus vereinbaren, nach dem garantiert wenigstens 6 von ihnen die eigene Hutfarbe dabei richtig nennen.

    Hinweis: die mehrstellige Antivalenz-Funktion.

    Warum kann man 7 Richtige nicht garantieren?

Informationsdarstellung — Medien

Einleitung, Überblick

Bausteine/Formen elektronischer Medien

Text-Strukturierung und -Formatierung

Schwarz-Weiß-Bilder

Beschreibung (Erzeugung) von Bildern

Operationen auf Bildern

Neben- und Übereinandersetzen

Boolesche Kombination von Bildern

Transformationen von Bildern

Hausaufgaben

  1. (nochmals) die Aufgabe wieviele Bit pro Semester: vergleichen Sie unterschiedliche Medienformen:

    • (Wdhlg.) jede Folie mit 1 Byte pro Zeichen, 10 Zeilen, 50 Spalten

    • jede Folie einzeln als Schwarz-Weiß-Bild mit 300 dpi (dots per inch) auf A4 (quer)

    • jede Vorlesung als Audio-Stream (mono, 48 kHz Sample-Rate, 16 Bit je Sample)

    • jede Vorlesung als Video-Stream (HD-Format, für jedes Pixel 4 Byte Farb-Information, 30 fps (frames per second))

    Nur jeweils die Anzahl der Bit für eine Vorlesung (20 Folien bzw. 90 min) ausrechnen und die Verhälnisse angeben, auf Zehnerpotenzen gerundet.

    Die dabei entstehenden Zahlen sind unrealistisch groß. In der Praxis werden solche Daten (teilweise drastisch) komprimiert, das behandeln wir später.

  2. Benutzen Sie die algebraische Bild-Sprache (die Test-Aufgabe im autotool) zum Zeichnen von

    • einzelnen Buchstaben

    • Verkehrszeichen

    Verwenden Sie dabei auch Kreise, Bild-Ausschnitte (slice), sowie Boolesche Verknüpfungen.

    Laden Sie einige so erzeugte Bilder im Forum des Opal-Kurses hoch, aber ohne Quelltexte. Diese sollen von den anderen Studenten geraten werden. Sie können Hinweise geben (z.B., welche Operationen wurde wie oft benutzt). Auflösung dann in der Übung.

  3. Überprüfen Sie das De-Morgansche Gesetz (aus der Aussagenlogik) durch die entsprechende Konstruktion auf Bildern.

    Formulieren Sie Assoziativ- und Distributiv-Aussagen für Bild-Operationen (Row, Column, Boolesche Kombinationen) und überprüfen Sie diese an Beispielen.

Speicher

Motivation, Überblick

Nand-Flip-Flop als 1-Bit-Speicher

Physikalische Grundlagen für Speicher

Speicherprinzipien historischer Rechner

Disketten und Festplatten

CD und DVD

Die Speicher-Hierarchie

Cache

Speicher-Zugriffs-Arten (technisch)

Speicher-Zugriff (Anwender-Sicht)

Dateisysteme

Dateistruktur und Suche

Speicher und Speicherdienste

Hausaufgaben

  1. Aufgaben von Folie Disketten und Festplatten

  2. Welchen Informationgehalt (in Bit) hat ein Buch? Den Informationsgehalt einer Buchseite abschätzen als Bild (300 dpi schwarz/weiß).

    Welche Informationsdichte (in Bit pro \(\textrm{cm}^3\))?

    Vergleichen mit Informationsdichte einer HDD (mit Gehäuse), eines Paketes mit SD-Karten (vgl. Randall Munroe, What If?, https://what-if.xkcd.com/31/ – dort angegebene Zahlen nachrechnen)

  3. Wiederholung Schaltkreise: lösen Sie autotool 45-1 (Majorität von 5 Eingängen) durch möglichst kleine Schaltung.

    Ansatz: zu realisieren ist die Funktion \(\operatorname{\textsf{Atleast}}_3^5(x_0,\ldots,x_4)\) mit \(\operatorname{\textsf{Atleast}}_k^n(x_0,\dots,x_{n-1}):=\) wenigstens \(k\) der \(n\) Eingaben sind wahr.

    Ergänzen, erklären und verallgemeinern Sie:

    • \(\operatorname{\textsf{Atleast}}_2^3(x_0,x_1,x_2) = (\operatorname{\textsf{Atleast}}_1^2(x_0,x_1)\wedge x_2) \vee (\operatorname{\textsf{Atleast}}_2^2(x_0,x_1)\wedge \neg x_2)\).

      Hier kann man \(\wedge \neg x_2\) sogar weglassen.

    • \(\operatorname{\textsf{Atleast}}_1^2(x_0,x_1) = \dots\)

    • \(\operatorname{\textsf{Atleast}}_2^2(x_0,x_1) = \dots\)

    Die Knoten der gesuchten Schaltung sind \(\operatorname{\textsf{Atleast}}_k^n(x_0,\dots)\) mit \(1\le k\le 3, 2\le n \le 5, k\le n\).

Programme

Motivation

Geradeaus-Programme

Sichtbarkeit, statische Korrektheit

Beispiel: Schachbrett

Baum-Struktur

Verdeckung von Namen

Unterprogramme (Motivation)

Unterprogramme (Syntax und Semantik)

Beispiele für Unterprogramme

Warum nicht Java, C#, …?

Trotzdem: Vergleich und Quellen

Hausaufgaben

  1. Ziffern, Buchstaben, Symbole (z.B. Verkehrszeichen) eigener Wahl programmieren

    unter wesentlicher Benutzung von Namen und Unterprogrammen.

  2. möglichst große Bilder konstruieren (es geht hier nur um die Fläche, nicht die Pixelfarben)

    durch (kleine) Programme der Form

    let { pixel = Rectangle (1,1) True
    ; row x y = Row    [x,y]
    ; col x y = Column [x,y]
} in  a

    wobei der Ausdruck a keine Domain-Operation enthält (sondern nur Let-Blöcke, UP-Aufrufe, Namen)

    Betrachten Sie dabei diese syntaktischen Einschränkungen für a:

    • überhaupt kein Let

    • mit Let, aber alle dort definierten Namen 0-stellig (also keine Unterprogramme)

    • …mit maximal 1-stelligen UP

    • …mit maximal 2-stelligen UP

    Beispiele 6, 7 aus https://www.imn.htwk-leipzig.de/~waldmann/talk/21/abp/ vorführen, erklären, die Größe nachrechnen.

    Falls Sie die eingestellte Größenbeschränkung im autotool überschreiten: rechnen Sie selbst (exakt) aus, welche Fläche Ihr Bild hat.

  3. möglichst kleine Programme, die ein Schachbrett erzeugen. Diskutieren Sie die Verwendung von

    • Rechtecken und Antivalenz (Combine Xor [p,q])

    • Let, Unterprogrammen

    Für \(8\times 8\), für größere Bretter.

Programm-Ablauf-Steuerung

Motivation

Beispiele für Daten-Abhängigkeiten

Datentypen und statische Typisierung

Typ-Inferenz und Typ-Deklaration

Die Verzweigung

Die Wiederholung (Iteration)

Beispiele zur Iteration

Termination

Iteration zur Bild-Erzeugung

Invarianten (Definition, Motivation)

Geometrische Invarianten (Beispiele)

Invariante (Beispiel)

Invariante (Beispiel—Lösung)

Invarianten (Hausaufgabe)

Vergleich, Quellen

Hausaufgaben

  1. Arithmetische Funktionen durch Iteration aus der Nachfolgerfunktion: Addieren, Multiplizieren, Potenzieren und weitere arithmetische Funktionen implementieren und vorführen.

    Mit einem kleinen Programm, das nur iterate, succ und let verwendet, eine möglichst große Zahl erzeugen.

  2. durch Iterieren von Bildfunktionen (unter Verwendung von Row, Column, Mirror, Rotate, Xor; nicht unbedingt alle gleichzeitig) interessante Muster erzeugen.

    Beispiel

    let { f (x::Pic) = 
           Column [Row  [Transform Mirror x,x ]
                  ,Row [Transform Rotate x, Combine Not [x]]] 
} in  iterate f 4 (Triangle (20,20) False)

    Bilder veröffentlichen (vor der Übung), Programme nicht oder nur Hinweise.

  3. Die Aufgabe mit Parteien A,B,C.

Algorithmen

Motivation, Überblick

Suchen

Suchen mit geordneter Eingabe

Einfügen in geordnete Eingabe

Sortieren

Sortieren durch Einfügen

Die informationstheoretische untere Schranke für das Sortieren

Optimales Sortieren für 5 Eingaben

Hausaufgaben

  1. Geben Sie ein Verfahren an, das die dritt-größte von fünf Zahlen (also den Median) durch höchstens 6 Vergleiche bestimmt.

    Sie können die Zahlen also nicht sortieren, denn das kostet 7 Vergleiche.

    Hinweis: trotzdem so anfangen wie bei Merge Insertion (bis jetzt gilt).

    Geben Sie alle Permutationen \([a,b,c,d]\) von \([1,2,3,4]\) an, für die gilt \(a\le b\le d\wedge c\le d\)

    Beschreibe Sie die Permutationen \([a,b,c,d,e]\) von \([1,2,3,4,5]\), für die gilt \(a\le b\le d\wedge c\le d\). Nicht alle hinschreiben, aber die Anzahl bestimmen und: Warum kann \(d\) in einer solchen Permutation nicht der Median von \([1,2,3,4,5]\) sein?

    Durch zwei weitere Vergleiche soll ein weiteres Element (aus dem gleichen Grund) ausgeschlossen werden.

    Der letzte Vergleich führt zum Ziel.

  2. In einem Behälter sind 91 Atome vom Typ A … (Aufgabe gestellt in der ersten VL)

  3. für dieses Programm:

    let { m (x::Pic) = Transform Mirror x
    ; r (x::Pic) = Transform Rotate x
    ; d (x::Pic) = m (r x)
    ; a (x::Pic) = r (m x)
    ; pixel = Rectangle (10,10) True
    ; blank (p::Pic) = Combine Xor [p,p]
    ; sep (k::Nat)  =
      let { f (p::Pic) =  Row [ pixel, blank p, blank p ]
      } in  iterate f k pixel
    ; f (k::Nat) (x::Pic) = Row
       [ Column [ x, sep k, d x]
       , a (Row [m (sep k), blank pixel, blank (sep k) ])
       , m (Column [ x, sep k, d x])
       ]
} in f 3 (f 2 (f 1 (f 0 pixel)))

    erklären Sie jede einzelne Funktion (rufen Sie sie einzeln auf), erklären Sie, wie dadurch das gesamte Bild entsteht.

    Gezeichnet wird die Hilbert-Kurve: der weiße Weg berührt oder kreuzt sich nicht selbst und durchläuft das gesamte Quadrat. Begründen Sie diese Eigenschaften.

    Können Sie das Programm verkürzen (bei genau gleicher Ausgabe)?

    Hinweis: die Protokollierung der Auswertung von Teilausdrücken kann ab- und angeschaltet werden, indem {-# silent #-} oder {-# verbose #-} davorgesetzt wird:

    ...
} in {-# silent #-} f 3 (f 2 (f 1 ( {-# verbose #-}  f 0 pixel)))

Computernetze

Motivation, Überblick

Graphen (Definition, Beispiele)

Graphen (Anwendungen)

Zeichnungen von Graphen, Planarität

Isomorphie von Graphen

Zusammenhang von Graphen

Beispiel für Weg im Internet-Graphen

Minimaler Zusammenhang: Bäume

Redundanter Zusammenhang

Durchmesser von Graphen

Ein Beispiel-Graph

Der Hyperwürfel

Das Internet (Definition)

Internet und IP-Adressen

Firewalls, Virtuelle private Netze (VPN)

Adressen und Namen

Kampf um die (DNS-)Daten

Kampf um die (DNS-)Daten (Quelle)

Hausaufgaben

  1. als Wiederholung zu Sortierverfahren: https://www.mathekalender.de/wp/de/kalender/aufgaben/aufgabe-05/

  2. für \(C_7=\) ein Kreis mit 7 Knoten:

    1. Bestimmen Sie Durchmesser und Knotenzusammenhangszahl.

    2. Fügen Sie möglichst wenige Kanten ein, so daß der Durchmesser kleiner wird

    3. Fügen Sie möglichst wenige Kanten ein, um die Zusammenhangszahl zu erhöhen.

    Für den Beispielgraphen (siehe Folie):

    • geben Sie eine möglichst schöne Zeichnung an (regelmäßig, wenige Kreuzungen)

    • bestimmen Sie den Durchmesser,

    • bestimmen Sie die Zusammenhangszahl.

  3. zu DNS und DoH (DNS over HTTPS) – Es geht bei diesen Fragen hier nur um die Technik, wir behandeln später noch die Überwachungs- und Anzeigenwirtschaft.

    1. Wo ist diese Einstellung in Firefox? Was ist das Default?

    2. Welche Information geht dem ISP bei DoH verloren? Die IP-Pakete sieht er ja dann doch beim Transport, egal, welcher Nameserver vorher verwendet wurde.

      Benutzen Sie diese Quelle: Timothy B. Lee Why big ISPs aren’t happy about Google’s plans for encrypted DNS, Ars Technica, 10/1/2019. https://arstechnica.com/tech-policy/2019/09/isps-worry-a-new-chrome-feature-will-stop-them-from-spying-on-you/

    3. Wie wirkt ein Pi-Hole als DNS-Server?

      Benutzen Sie Original-Quellen (https://docs.pi-hole.net/) und Sekundärquellen (z.B. Troy Hunt: Mmm... Pi-hole..., 26. Sept. 2018 https://www.troyhunt.com/mmm-pi-hole/)

      Welche Datenverarbeitung Ihrer Daten durch Dritte findet auf diesen Webseiten statt? Mit umatrix anzeigen, dann blockieren. Webseiten trotzdem noch benutzbar?

    4. Erklären und diskutieren Sie: wenn man uMatrix benutzt, braucht man das Pi-Hole braucht eigentlich nicht?

      Das Pi-Hole als DNS-Server für das gesamte lokale Netz verhindert auch die unerwünschte Datenübertragung von Geräten (z.B. sogenannten Smart-Fernsehern), deren Hersteller die Konfiguration durch den Besitzer verbieten. Es sei denn, das Gerät benutzt auch DoH.

Kodierung und Kompression

Kodierung: Definition,Motivation

Der Hamming-Abstand

Abstände und Codes

Fehler-Erkennung und -Korrektur

Anwendung, Ausblick

Kompression

Codes variabler Länge

Präfix-Codes (eigentlich: präfixfreie Codes)

Effiziente Präfix-Codes

Kompression durch Blockwiederholung

Beispiele für verlustfreie Kompression

Kompression durch Geradeaus-Programme

Verlustbehaftete Kompression

Beispiel Video-Kompression

Bespiele Audio-Kompression

Hausaufgaben

  1. Zeichnen Sie einen Hyperwürfel \(H_3\) der Dimension 3 (siehe Folie bei Graphen)

    Geben Sie eine möglichst große Teilmenge \(C_1\) der Knoten an, die einen Code bildet, der 1-Bit-Fehler erkennen kann.

    Geben Sie eine möglichst große Teilmenge \(C_2\) der Knoten an, die einen Code bildet, der 1-Bit-Fehler reparieren kann.

    Desgleichen für \(H_4\). (Hinweis: es ist unpraktisch, und auch nicht nötig, diesen Graphen zu zeichnen.) Bestimmen Sie eine obere Schranke für die Anzahl der Elemente eines 1-Bit-Fehler-reparierenden Codes \(C\) im \(H_4\):

    Für jeden Knoten \(x\in C\) betrachten wir die Menge \(H_4[x] = \{x\}\cup H_4(x) =\) der Knoten \(x\) mit seinen Nachbarn.

    Jede solche Menge hat …Elemente (warum?)

    Alle diese Mengen sind disjunkt (warum?)

    Die Vereinigung dieser Mengen liegt in \(V(H_4)\). Also gibt es höchstens \(\dots\) solche Mengen.

  2. Geben Sie eine Darstellung dieser Folge der Länge 100 durch ein möglichst kurzes Geradeaus-Programm an.

    \[s=1001000010000001000\dots 0001\]

    Die 1 stehen auf den Indizes, die Quadratzahlen sind.

    Verallgemeinern Sie a) auf längere Folgen dieser Art, b) auf entsprechende Folgen für Kubikzahlen.

  3. https://www.mathekalender.de/wp/de/kalender/aufgaben/aufgabe-06/

    Modellierung: \(G\) ist Kreis \(C_{33}\) auf Knoten 1, 2,…, 33 mit zusätzlichen Kanten (Diagonalen) \(1-16, 1-17,2-17,2-18,\dots\).

    Wieviele Kanten hat \(G\)? Welchen Grad hat jeder Knoten aus \(G\)? Welchen Durchmesser hat \(G\)?

    Gesucht ist eine größte unabhängige Knotenmenge \(U\) (rote Wichtel).

    Def. eine Menge \(U\subseteq V\) heißt unabhängig in \(G=(V,E)\), falls \(\forall x,y\in U: xy\notin E\).

    Aufgabe kann ersetzt werden durch andere Aufgabe aus dem gleichen Kalender, bei der Graphen vorkommen oder zur Lösung benutzt werden können. Rechtzeitig anmelden!

    Hinweise und Diskussion im Forum des Opal-Kurses (und nicht hier — die Aufgabensteller wünschen keine öffentliche Diskussion, denn der Wettbewerb der angemeldeten Teilnehmer soll nicht verzerrt werden.)

Verschlüsseln und unterschreiben

Motivation, Überblick

Verschlüsseln: Definition, Beispiel

Verfahren mit öffentlichen Schlüsseln

Das Rechnen mit Restklassen

Restklassen von Potenzen

Das RSA-Verfahren

Rechnen mit großen Zahlen

Anwendung: OpenPGP message format

Verschlüsselte Mails und Überwachung

Authentizität (Identitäts-Beweis)

Authentizität und Integrität von Nachrichten

Zertifikats-Ketten, Webserver-Zertifikate

Transportverschlüsselung (TLS)

Hausaufgaben

WS21: Aufgaben 1, 3, 4.

  1. Geben Sie Sie ein möglichst kurzes Geradeausprogramm an (vgl. Aufgabe zu Kompression einer Zeichenkette), das \(a^{111}\) nur mit Multiplikationen bestimmt.

    Etwa \(b=a\cdot a, c=b\cdot b,\dots\)

    Benutzen Sie die Binärdarstellung des Exponenten.

    Verallgemeinern Sie dazu dieses Beispiel: \(13=2\cdot 6 + 1 = 2(2\cdot 3+0)+1 =2(2(2\cdot 1+1)+0)+1 =2(2(2(2\cdot 0+1)+1)+0)+1\),

    also \(a^{13}=a^{2\cdot 6+1}=(a^6)^2\cdot a\) usw.

    Berechnen Sie damit \([3^{13}]_5, [3^{111}]_5\).

  2. Welche Fälschung wird ermöglicht, wenn bei dem auf Folie Authentizität und Integrität von Nachrichten angegebenem Verfahren eine Hashfunktion \(h\) benutzt wird, für die man zu gegebenem \(m\) leicht andere \(m'\) findet mit \(h(m)=h(m')\)?

    Begründen Sie, daß folgende Funktionen diese Eigenschaft haben (und deswegen ungeeignet sind)

    1. \(h_1(m)=0\)

    2. \(h_2(m)=\) Länge (Anzahl der Zeichen) von \(m\)

    3. \(h_3(m)=\) Summe der ASCII-Codes der Zeichen von \(m\)

  3. Zeigen Sie Zertifikat und Zertifikatskette für htwk-leipzig.de (und ähnliche, z.B. autotool, bildungsportal-sachsen.de) Welche Bitbreite wird verwendet? Wieviele Dezimalziffern wären das?

    Welches Root-Zertifikat wird verwendet, warum glaubt das Ihr Browser?

    Fassen Sie wesentliche Inhalte dieser Meldung über die (2019 zeitweilig) erzwungene Installation von Root-Zertifikaten in Kasachstan zusammen:

    Jon Brodkin: Google, Apple, and Mozilla block Kazakhstan government’s browser spying, Ars Technica 21. 8. 2019, https://arstechnica.com/tech-policy/2019/08/chrome-firefox-and-safari-updated-to-block-kazakhstan-government-spying/

    Was ist der aktuelle Status?

  4. Welche Daten sind im digitalen Impfzertifikat enthalten? Wie wird die Gültigkeit eines Zertifikates für eine konkrete Person geprüft? Warum ist das Verfahren fälschungssicher?

    Hinweis: die Antwort ist nicht: da muß man eben die richtige App verwenden. Die Form der Daten und ihre Gültigkeit ist unabhängig von einer konkreten Software spezifiziert. Der Gesetzgeber kann nicht die Installation einer bestimmten Software oder überhaupt Besitz und Benutzung eines sogenannten Smartphones vorschreiben.

    Zitieren Sie Primärquellen, z.B.

    Sie können Sekundärquellen verwenden, um die Primärquellen zu finden und zu verstehen.

    Vorsicht: Geben Sie Ihr eigenes Zertifikat (während der Bearbeitung dieser Aufgabe und auch sonst) nicht ohne triftigen Grund an Dritte weiter (z.B. eine angeblich Online-Zertifikatsprüfung). Fälschen kann man es nicht (siehe Teilaufgabe oben), aber es enthält doch personenbezogene Daten, an denen die Überwachungswirtschaft interessiert ist.

    Welche Vorschriften machen die Gesetzgeber (in EU, Bund, Sachsen) über die Verarbeitung personenbezogener Daten (z.B. durch Gastronomen) bei Impfnachweis (u.ä.) und Kontakterfassung?

  5. (optional) Schicken Sie mir (bis vor der nächsten Übung) eine nach OpenPGP verschlüsselte Email (von Ihrer Hochschuladresse aus). Inhalt test reicht.

    Wenn Sie Ihren public key mitschicken, werde ich verschlüsselt antworten. (Auch ohne Inhalt.)

    Vorsicht: Ihren public key nicht auf Keyserver hochladen. Keyserver sind eine Ansammlung von personenbezogenen Daten. (Lebende Email-Adressen—sind viel wert. Von Leuten, die sich mit Technik auskennen—sind noch viel mehr wert.)

    Welche Vorkehrungen zu Datenschutz/Datenreduzierung sehen Sie auf https://keys.openpgp.org/? (ist voreingestellter Keyserver bei Thunderbird)

Protokolle, Dienste

Überblick

Dienste: lokal, entfernt, zentral?

Lokale Dienste, Betriebssysteme

Beispiele für Netzwerk-Dienste: DNS, NTP

Electronic Mail (Email)

Bulletin Boards (News, NNTP)

Das World-Wide Web: HTTP

Das World-Wide Web: HTML (CSS, JS)

Datenübertragungen durch HTTP, Cookies

Das World-Wide Web: URLs

URLs und ihre Feinde

Zentralisiert, föderiert

Bsp. für offene Protokolle, föderierte Dienste

Software-Lizensierung

Freie Software, öffentliches und privates Geld

Dienste: lokal und fern, gestern und morgen

Hausaufgaben

WS21: Aufgaben 1, 4, 5

  1. der Graph des WWW: hat wieviele Knoten (wieviele Webseiten gibt es)?

    Vorsicht: zwei Interpretationen von Webseite denkbar

    • die einzelne Seite, gegeben durch ihren URL,

    • web site (site im Sinne von Ort, für mehrere Seiten) gegeben durch Domain-Namen des Servers.

    was ist der durchschnittliche Kantengrad (wieviele Links sind auf einer Seite)?

    (recherchieren Sie nach möglichst aktuellen und glaubhaften Schätzungen in wissenschaftlichen Publikationen, überprüfen Sie deren Plausibilität durch eigene Anschauung)

    Wenn jede Webseite 1 kByte Text enthält (ist das realistisch? finden Sie dazu evtl. andere Werte?), wieviele Byte hat das WWW insgesamt?

    Wenn man das alles auf Datenträger (micro-SD oder ähnlich) speichern würde (z.B. zum Archivieren): welches Volumen/welche Masse/welche Kosten?

    (PS: 1. es ist natürlich schon gespeichert, aber meist nicht langfristig, 2. das meiste lohnt sich wohl nicht zu archivieren, denn es ist Unsinn von und für Maschinen (SEO–search engine optimisation), 3. vergleiche https://archive.org/ )

  2. Erklären und erproben Sie das Firefox-Addon https://addons.mozilla.org/en-US/firefox/addon/temporary-containers/

    Legen Sie dazu zunächst ein neues Browser-Profil an (about:profiles) und installieren Sie das Addon dort.

    Beobachten Sie dann das Verhalten bei gleichzeitiger Verwendung (Login) von autotool und Opal, mit und ohne Addon.

  3. Stellen Sie die Lizenzen der Lernmanagementsysteme Opal und des zugrundeliegenden Systems (open)Olat fest. Was wäre anders, wenn Olat unter GPL stünde?

  4. (a) Bestimmen Sie einige URLs, die direkt das Studium betreffen (z.B. Ihre Studienordnung, Modulbeschreibung, akademischer Kalender) und schätzen Sie deren Langlebigkeit ein.

    (b) Bestimmen Sie den URL der Tagesschau vom 11. Januar 2022 in der ARD-Mediathek (oder konkretes anderes Datum, konkrete andere Sendung im öfftl.-rechtlichen Rundfunk) (1. einfach: die Seite mit eingebettetem Player, 2. nicht so einfach: die tatsächliche mp4-Datei)

    (c) Vgl. dazu auch https://arstechnica.com/tech-policy/2021/10/viewing-website-html-code-is-not-illegal-or-hacking-prof-tells-missouri-gov/ Jon Brodkin, 10/25/2021

    (d) was ist das Geschäftsmodell von kostenlosen URL-Verkürzungs-Diensten?

  5. Um die Silo-Wirkung (das Eingesperrtsein der Benutzten) der monopolistischen sogenannten sozialen Netzwerke etwas zu mildern, hat die EU das Recht auf Datenportabilität definiert.

    Geben Sie die Primärquelle an (das Gesetz).

    Wie soll das wirken? Tut es das? (recherchieren Sie dazu Sekundärquellen)

    Sehen Sie Anwendungen auf Verarbeitung Ihrer Daten durch HTWK?

Die Überwachungswirtschaft

Einleitung, Überblick

Suchmaschinen

Suchmaschinen-Optimierung

Publizieren und Werben

Online-Werbung

Versteigerung von Suchbegriffen

Eindeutige Personenkennung

Sogenannte soziale Netzwerke

Auswirkungen massiver Datensammlung

Informationsfilterung, Microtargeting

Überwachung und Bürgerrechte

Irreführende Benutzerschnittstellen

Aktuelle Informationen und Gesetzgebungsvorhaben

Hausaufgaben

  1. Fassen Sie wesentliche Aspekte von https://atg.sd.gov/docs/20201216 COMPLAINT_REDACTED.pdf zusammen. Benutzen Sie auch (aber nicht nur) Sekundärquellen.

  2. Fassen Sie den aktuellen Konflikt zwischen Facebook und Apple zusammen, siehe z.B. NZZ vom 31. 1. 21 https://www.nzz.ch/technologie/facebook-und-apple-der-heranziehende-datenkrieg-der-giganten-ld.1599202

  3. (Aufgabe von voriger Woche) Recht auf Datenportabilität

  4. zu soziale Netzwerken:

    Was ist eine Kevin-Bacon-Zahl? Bestimmen Sie diese für den Darsteller der Titelfigur in Ein Fall für Rettig https://www.htwk-leipzig.de/no_cache/de/hochschule/aktuelles/newsdetail/artikel/944/

    Definieren Sie den Begriff Erdös-Zahl, bestimmen Sie meine. (Bonus: und die von Kevin Bacon.)

    Schätzen Sie für den jeweiligen Graphen (Schauspieler, Mathematiker): Anzahl der Knoten, Knotengrad, Durchmesser.

Ausblick, Wiederholung

Definition, Ziele

Themen

Struktur-Modell: Baum, Graph

Programmierung?

Informatik und Medien (Beispiele)

Prüfung