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).
- Ort: Raum 236 im Informatik Neubau (Geb. 50.34)
- Zeit: Wöchentlich – Montag, 11:30 Uhr
- Kontakt: thomas.pajor (at) logn.de oder #uka.info1 im Quakenet
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 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 auf 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 nicht negativ sein, und somit ist der Wert für nicht sondern , 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
- Implementierung der GÜM [2 Punkte]
- Implementierung der Haralick-Merkmale [2 Punkte]
- Implementierung der Lauflängenberechnung [2 Punkte]
- Implementierung der Lauflängenmerkmale [2 Punkte]
Metrik
- Implementierung [2 Punkte]
- Begründung (Auswahl der Merkmale, Kombination, …) [2 Punkte]
Integration [2 Punkte]
Auswertung
- Finden der Testbilder [3 Punkte]
- Analyse des Programmierers [3 Punkte]
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 hätte eigentlich folgendermaßen aussehen müssen
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 für Wahrscheinlichkeiten benutzt wird und dass das Alphabet auch von der Zufallsvariable 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 berechnet sich aus einem String also durch
Wir interpretieren also die Zeichenkette als Zahl zur Basis .
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 des Musters neue Zahlen konstruieren könnt, die dann den gleichen Wert wie 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 , 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 im Filter genau die gleiche Funktion. Wegen wird im Ausgabebild genau dann eine gesetzt, wenn jede im Filter (angesetzt auf den Bildpunkt ) auch im Bild vorhanden ist. Genauso ist es auch bei der Definition aus der Vorlesung.
Betrachte z.B. den Bild(-Ausschnitt) und die Maske bzw. . So liefern beide Masken angesetzt auf den Bildausschnitt eine egal welchen Wert das enthält. Die 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 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 in zwei Teilmasken auf, wobei beide für sich wieder als Mengen von Koordinaten dargestellt seien. Wir fordern außerdem, dass sie disjunkt sind, also gilt. Wir interpretieren nun als „Vordergrundmaske“ und als “Hintergrundmaske”. Hit-or-Miss ist dann einfach
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 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
- Grobskizze Architektur (Bausteine, Abhängigkeiten) [4 Punkte]
- Erklärung der Implementierungsentscheidungen (Bibliotheken, Programmiersprache, …) [2 Punkte]
Implementierung der Bausteine
- Benutzeroberfläche (Steuerung Scanvorgang, Eingabe Suchbild, Ausgabe Ergebnisse) [1 Punkt]
- Verzeichnissuche [1 Punkt]
- Bildimport (3 Formate) [1 Punkt]
- Datenbank [3 Punkte]
- Merkmalsextraktion [4 Punkte]
Funktion
- Finden des zum Suchbild identischen Bildes [1 Punkt]
- Ergebnislose Suche bei leerem Suchbild (weiß od. schwarz) [1 Punkt]
- Finden ähnlicher Bilder je nach Ausrichtung der Merkmalsextraktion [2 Punkte]
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:
- Patrick Armbruster
- Simon Grebe
- Andreas Grün
- Christian Harnisch
- Anton Malsam
- Manuela Noe
- Christian Trefzer
- Chengchao Qu
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.