Info IV, Tutorium 2, SS 06

Dies ist die Homepage zum Informatik IV Tutorium Nummer 2 im Sommersemester 2006 an der Universität Karlsruhe (TH).

Einen Übungsschein könnt ihr erwerben. Hierfür sind diesmal die Hälfte der zu erreichenden Punkte sowie das erfolgreiche Lösen der Programmieraufgabe nötig.

Die Abgabe in Zweiergruppen ist nicht erlaubt. Dafür wird es vermutlich immer nur eine Korrekturaufgabe pro Übungsblatt geben.

Die bearbeiteten Übungsblätter sind, wie gewohnt, versehen mit Name, Matrikelnummer sowie der Tutoriumsnummer in die Einwurfsschlitze im Keller des Informatik Neubaus zu werfen. Bitte achtet darauf dass eure Blätter zusamengetackert sind.

Begleitend zur Vorlesung gibt es außerdem eine Newsgroup in der diskutiert und Fragen gestellt werden können.

Neues…

Fehler in Tut Aufgabe

Montag, 27.08.2006, 20:35

In den Tut Aufgaben vom 05.05.2006 in der letzten Aufgabe 3b) war ein Fehler im Beweis der unteren Schranke. Die qq rationalen Funktionen müssen paarweise verschieden sein, was leider nicht der Fall war. Ich habe die Lösung ausgebessert und neu hochgeladen. Die untere Schranke hat sich dadurch von Ω(n)\Omega(n) auf Ω(log⁡2(n+1))\Omega(\log_2(n+1)) verbessert.

Vielen Dank an Misha für den Hinweis!

Boyer-Moore

Montag, 08.08.2006, 13:38

In den letzten Tagen habe ich einige Hinweise bekommen, dass auf dem Boyer-Moore Papier in dem „Banana“ Beispiel in der Tabelle ein Fehler vorliegt. Natürlich kann das kk nicht negativ sein, und somit ist der Wert für m−km-k nicht 88 sondern 66, da kein Präfix des Wortes ein Suffix des Suffix des Wortes ist. Eine upgedatete Version (rev2) findet ihr unter Material.

Vielen Dank für den Hinweis! :)

JPEG Kompression

Montag, 24.07.2006, 23:25

Wie versprochen kommt hier noch das Applet zur JPEG Kompression aus dem Tutorium von heute. Ihr könnt es hier finden.

Programmieraufgabe

Dienstag, 17.07.2006, 20:10

Zum zweiten Teil der Programmieraufgabe poste ich euch nochmal die Punkte die wir bei der Abnahme prüfen werden:

Merkmale

Metrik

Integration [2 Punkte]

Auswertung

Punkte / Schein

Donnerstag, 06.07.2006, 18:53

Es gibt zwei Dinge zu den Übungsblättern sowie Punkten zu sagen.

Zum einen war leider ein Fehler in der Aufgabe 5d) auf dem 10. Übungsblatt. Die Matrix PP hätte eigentlich folgendermaßen aussehen müssen

P=(010α01−α100)P = \begin{pmatrix}0 & 1 & 0 \\ \alpha & 0 & 1 - \alpha \\ 1 & 0 & 0\end{pmatrix}

was der transponierten Matrix auf dem Blatt entspricht. Da auch die Aufgabe e) davon betroffen ist (sie beruht ja auf der d)) wird die Gesamtpunktzahl auf dem Blatt auf 7 abgesetzt. Wer die Aufgabe(n) trotzdem richtig bearbeitet hat, und den Fehler umgangen hat, bekommt bis zu 3 Extrapunkte.

Da es voraussichtlich insgesamt 12 Blätter geben wird, habe ich schonmal die noch zu bearbeitenden Blätter in das Übungsblattsystem eingetragen, so dass ihr überprüfen könnt wieviel Punkte ihr schon erreicht habt, und seht ob ihr den Schein erhaltet. Vergesst aber nicht den zweiten Teil der Programmieraufgabe zu machen, denn den Schein bekommt nur wer sowohl bei den Übungsblättern, alsauch bei der Programmieraufgabe mindestens 50% erreicht hat.

Übungsfolien

Donnerstag, 29.06.2006, 21:35

Die Folien zur Informatik IV Übung von heute habe ich mal unter Material verlinkt. Möglicherweise werden sie auch noch auf die offizielle Info IV Seite hochgeladen!

Informationstheorie / Notation

Montag, 19.06.2006, 17:05

Zu den Grundlagen der Informationstheorie (Entropie, Kanal, Redundanz) habe ich letztes Jahr einen Artikel geschrieben, wo das Ganze nochmal erklärt wird. Er ist hier zu finden.

Ich soll euch allerdings darauf hinweisen, dass die Notation dieses Jahr zum Teil etwas von der Notation der letzten Jahre abweicht. Insbesondere dass Pr\text{Pr} für Wahrscheinlichkeiten benutzt wird und dass das Alphabet X\mathcal{X} auch von der Zufallsvariable XX streng unterschieden wird. Meine Notation im Tutorium heute war eher die von letztem Jahr, aber ich habe heute in der Tutorenbesprechung erfahren, dass Prof. Beyerer wohl recht hohen Wert auf “seine” Notation legt. Benutzt also in der Klausur am besten die Notation aus den Vorlesungsfolien.

Boyer & Moore

Freitag, 09.06.2006, 10:11

Anscheinend gab es noch ein bisschen Schwierigkeiten mit dem Boyer & Moore Algorithmus, vorallem mit der Berechnung der Sprungtabelle. Im Internet gibt es leider ziemlich viele verschiedene „Versionen“ und Herleitungen, die sich meistens in Details unterscheiden, was sehr verwirrend sein kann.

Ich habe daher versucht den Algorithmus, und die Berechnung der Sprungtabellen, nochmal im Sinne der Vorlesung ausführlich herzuleiten. Das Papier was dabei rausgekommen ist findet ihr unter Material.

Mal wieder Feiertag

Mittwoch, 31.05.2006, 18:55

Da der Montag, 5. Juni schonwieder ein Feiertag ist, fällt das Tutorium an dem Tag aus. Es gibt aber ein Ausweichtermin am

Freitag, 9. Juni 2006, 11:30 Uhr in Raum -118 (Geb. 50.34)

Zu Rabin Karp

Mittwoch, 31.05.2006, 18:18

Da die Korrekturaufgabe zum Rabin & Karp Algorithmus ist, und ich den leider nicht mehr geschafft hatte im Tutorium, hier ein paar kleine Tipps.

Die grundlegende Funktionsweise des Algorithmus ist ja in der Aufgabe erklärt und findet sich auch nochmal in den Folien (Vorlesung 6, Folie 18). Die Hashfunktion die in der Aufgabe benutzt wird ist auch die selbe wie auf den Folien. Der Wert xx berechnet sich aus einem String aa also durch

x=a0dm−1+a1dm−2+…+am−1d0d=∣Σ∣x = a_0 d^{m-1} + a_1 d^{m-2} + \ldots + a_{m-1} d^{0} \qquad d = |\Sigma|

Wir interpretieren also die Zeichenkette als Zahl zur Basis dd.

Um alle Zeichenketten zu finden, die den gleichen Hashwert haben, empfehle ich euch nicht alle Zeichenketten auszurechnen und durchzuprobieren, das sind nämlich viel zu viele! Überlegt lieber wie ihr aus dem xx des Musters MM neue Zahlen x1,…x_1, \ldots konstruieren könnt, die dann x1mod  q,…x_1 \mod q, \ldots den gleichen Wert wie xmod  qx \mod q haben.

So, mehr möchte ich aber nicht verraten. Viel Erfolg! :)

Definition für morphologische Operationen

Montag, 29.05.2006, 21:12

Heute im Tutorium kam ja die Frage auf wie das mit den morphologischen Operationen nun genau ist.

Da in der Vorlesung für die Bildmaske drei Zustände pro Bildpunkt definiert wurden, nämlich 11, 00 und −- (don’t care), funktioniert die Beschreibung das Bild als Menge zu definieren nicht mehr.

Für Erosion sowie Dilation haben jedoch don’t care und die 00 im Filter genau die gleiche Funktion. Wegen A⊖M:={p∈Z2  ∣  Mp⊆A}A \ominus M := \{p \in \mathbb{Z}^2 \;\vert{}\; M_p \subseteq A\} wird im Ausgabebild genau dann eine 11 gesetzt, wenn jede 11 im Filter (angesetzt auf den Bildpunkt pp) auch im Bild AA vorhanden ist. Genauso ist es auch bei der Definition aus der Vorlesung.

Betrachte z.B. den Bild(-Ausschnitt) [1,1,x][1,1,x] und die Maske [1,1,0][1,1,0] bzw. [1,1,−][1,1,-]. So liefern beide Masken angesetzt auf den Bildausschnitt eine 11 egal welchen Wert das xx enthält. Die 00 in der Maske hat also schon die Funktion eines don’t cares. Ebenso gilt das auch für die Dilation.

Bei der Hit-or-Miss Operation, wo ja gefordert wird dass genau dann eine 11 im Ausgabebild gesetzt wird, wenn sowohl Nullen als auch Einsen der Maske mit dem Bild übereinstimmen sind die don’t cares auf den ersten Blick vielleicht doch wichtig. Man kann jedoch auch diese Operation auf einfache Mengenoperationen zurückführen. Wir teilen die Maske MM in zwei Teilmasken (M1,M2)(M_1, M_2) auf, wobei beide für sich wieder als Mengen von Koordinaten dargestellt seien. Wir fordern außerdem, dass sie disjunkt sind, also M1∩M2=∅M_1 \cap M_2 = \emptyset gilt. Wir interpretieren nun M1M_1 als „Vordergrundmaske“ und M2M_2 als “Hintergrundmaske”. Hit-or-Miss ist dann einfach

A⊗(M1,M2):=(A⊖M1)∩(A‾⊖M2)A \otimes (M_1, M_2) := (A \ominus M_1) \cap (\overline{A} \ominus M_2)

Es wird also das Bild zunächst mit der Vordergundmaske erodiert. Das liefert alle Stellen im Bild die vom Vordergrund her passen. Dann wird das Komplementbild mit der Hintergrundmaske erodiert. Das liefert alle Stellen im Bild die vom Hintergrund her passen. Der Schnitt dieser beiden (temporären) Bilder liefert dann schließlich genau die Stellen wo das gesuchte Objekt, das wir durch MM beschrieben haben, vorhanden ist.

Unter Material habe ich noch ein (vielleicht hilfreiches) PDF zu morphologischen Operationen und ihren Anwendungen verlinkt.

Punkteverteilung Progaufgabe (Teil I)

Montag, 29.05.2006, 19:51

Für alle die die Programmieraufgabe machen, und diese auch bewerten möchten gibt es jetzt eine Verteilung der Punkte (Es scheint wohl doch welche zu geben). Ich werde sie hier mal grob auflisten, damit ihr wisst auf was ihr beim Programmieren achten müsst. Folgende Dinge werden also bewertet:

Konzept

Implementierung der Bausteine

Funktion

Insgesamt sind das also 20 Punkte für den ersten Teil. Wie auch schon heute im Tut gesagt ist im ersten Teil noch nicht so wichtig, dass ihr schon komplizierte Merkmale implementiert, sondern es reichen einfache wie zum Beispiel „mittlerer Farbwert“, „Histogramm“ etc aus. Wichtig ist aber, dass ihr die Merkmalsextraktion erweiterbar haltet, so dass ihr leicht neue Merkmale hinzuprogrammieren könnt, da so etwas vermutlich im zweiten oder dritten Teil gefordert sein wird.

Falls ihr sonst noch Fragen habt, so schreibt mir am besten einfach eine E-Post.

Fehlende E-Mail Adressen

Sonntag, 21.05.2006, 02:54

Von folgenden Leuten, die bei mir abgegeben, bzw. von Webinscribe zugeteilt wurden, habe ich noch keine E-Mail Adressen:

Bitte schickt mir eine E-Mail mit eurer Adresse, sonst kann ich euch keinen Login für die Punktetabelle hier auf der Seite geben.

Material zu Bäumen und Aufgaben aus dem Tut

Freitag, 15.05.2006, 19:04

Ich habe, wie im Tut heute angesprochen, die Vorlesungsfolien aus der Informatik II Vorlesung (damals gehalten von ITM Zitterbart) über Binärbäume, AVL, Rot-Schwarz und B-Bäume unter Material verlinkt. Einige Erklärung sind dort ausführlicher als in den aktuellen Info IV Folien.

Außerdem gibt’s unter Material die Aufgaben mit Lösungen, die ich im Tutorium immer rechne. Insbesondere auch die Aufgaben die wir heute nicht geschafft haben. Die Lösung zu der AVL Aufgabe muss ich allerdings noch irgendwie TeXen, da ich das gestern abend nicht mehr geschafft habe ;-)

Erster Termin

Freitag, 28.04.2006, 00:19

Achtung: Da der erste Montag gleich ein Feiertag ist, fällt das Tutorium am 1. Mai aus! Ein Ersatztutorium wird am

Freitag, 5. Mai 2006, 11:30 Uhr in Raum -118 (Geb. 50.34)

stattfinden. Dieser Termin ist einmalig. Ab dem 7. Mai geht es dann regulär in Raum 236 weiter.