Programmieren in C++ im SS 2012 — Projekt

Hier finden Sie der Spezifikation der möglichen Projekte.

Allgemeine Anforderungen für alle Projekte

Unabhängig vom Projekt sollen Sie natürlich Code nach der Art schreiben, wie Sie es in der Vorlesung gelernt haben, insbesondere:

• Gutes Klassendesign, mit zwei separaten Dateien pro Klasse (Deklarationen in einer .h Datei, Implementierungen in einer .cpp Datei).

• Dazu ein funktionierendes Makefile, das nur das kompiliert, was sich geändert hat, und die vier Standard-Targets compile, test, checkstyle und clean realisiert.

• Nachvollziehbare Benennung von Klassen, Methoden und Membervariablen. In der Regel wird nicht abgekürzt, es sei denn eine zentrale Variable taucht in einer Funktion viele Male auf und ein langer Name würde den Code deutlich schwerer lesbar machen. Private Membervariablen beginnen grundsätzlich mit einem Unterstrich.
• Jede Klasse, jede Methode und jede Membervariable sollte dokumentiert werden. Wenn die Funktion einfach / klar ersichtlich ist, reicht eine kurze Erklärung, ansonsten eine angemessen ausführliche Erklärung. Das gilt auch für Codeblöcke in größeren Funktionen, die ohne Kommentar schwer zu verstehen wären.

• Unit tests für jede nicht-triviale Methode, die für die korrekte Funktion des Programms wichtig ist. Bei Methoden mit Spezial/Grenzfällen, neben einem allgemeinen Fall auch mindestens einen solchen Spezialfall testen. Bei Klassen mit komplexerem Inhalt, erwägen eine asString Methode zu implementieren, das hilft beim Debuggen und beim Testen.

• Der gesamte Code sollte keine checkstyle Fehler produzieren. Benutzung von // NOLINT nur in absoluten Ausnahme- (= von der Dozentin genehmigten) Fällen.

• Alle ausführbaren Programme enden auf Main. Bei Aufruf ohne Argument kommt eine "usage info", die genug Information enthält um zu verstehen, wie man das Programm benutzt. Handling von Kommandozeilenoptionen über die getopt Bibliothek, siehe Vorlesung 7.

Projekt 1 (Snake)

Kurzbeschreibung: Realisierung einer einfachen Version des gleichnamigen Videospiels, mittels ASCII Grafik. Siehe zum Beispiel http://www.youtube.com/watch?v=SAF95FAV-6M .

Geforderte Funktionalität:

• Ein ausführbares Programm SnakeMain, mit dem das Spiel gespielt werden kann.

• Schlange über Tasten in alle vier Himmelsrichtungen steuerbar.
• Wahlweise 1 oder 2 Spieler Modus. Bei zwei Spielern, entsprechend zwei Schlangen, von denen jede durch ihre eigenen Tasten steuerbar ist (so dass es im Prinzip gleichzeitig auf ein- und derselben Tastatur gespielt werden kann).
• Es erscheinen in unregelmäßigen Abständen (zufällig) Symbole auf dem Bildschirm. Wenn eine Schlange die "frisst", bekommt der entsprechende Spieler einen Punkt und seine Schlange wird um eins länger.
• Spielstandsanzeige. Es gewinnt, wer zuerst 10 Punkte hat oder wenn der andere Spieler mit dem Kopf seiner Schlange gegen den Körper seiner oder der gegnerischen Schlange oder gegen den Rand kommt. Der Rand sollte ersichtlich als solcher visualisiert werden.
• Automatische Erkennung der Bildschirm-Dimensionen.
• Kommandozeilenargumente für: 1 oder 2 Spieler Modus, Spielgeschwindigkeit, benutzerdefinierte Tastenbelegung, Schlangenlänge zu Beginn. Sinnvolle Default-Werte.

Optionale Funktionalität:

• Feinere Richtungssteuerung (beliebige bzw. fast beliebige Winkel).
• Ränder haben Löcher, wenn eine Schlange da rein läuft, kommt sie auf der anderen Seite wieder raus.
• "Wände" auch mitten im Spielfeld, wer da gegen läuft hat verloren, genau so wie wenn man den Rand oder die andere Schlange oder seinen Körper trifft.
• Zweite Spieler auf Wunsch computer-gesteuert, wenn's geht natürlich einigermaßen schlau.
• Was immer Ihnen noch einfällt.

Technische Realisierung:

• Malen auf dem Bildschirm mittels ANSI espace codes: http://en.wikipedia.org/wiki/ANSI_escape_code, oder mit der "Curses" Bibliothek: http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf . Letztere ist komfortabler und unterstützt auch so Dinge wie das Registrieren eines Tastendruckes, ohne dass der User dazu erst Return drücken muss (was für ein Spiel etwas unpraktisch wäre).

• Zum besseren Testen sollte Bewegung und Zeichnen der Objekte voneinander getrennt sein.

Projekt 2 (Virenscanner)

Kurzbeschreibung: Prüfen ob eine gegebene Datei die "Signatur" eines Virus enthält.

Geforderte Funktionalität:

• Ein ausführbares Programm VirusScanMain, mit dem eine oder mehrere gebenene Dateien auf Viren untersucht werden können. Alle Kommandozeilenargumente, die keine Optionen sind, sollten dabei als Dateinamen interpretiert werden.

• Die Signaturen der bekannten Viren stehen in einer ASCII Datei. Erklärung zum Format, siehe Vorlesung. Benutzen Sie für Ihr Projekt diese Datei.

• Es sollen folgende Signaturen unterstützt werden: feste Hex-Sequenz, mit ?, mit *, mit {...}. Erklärungen dazu siehe Vorlesung. Es sollte für jeden dieser Operatoren mindestens einen Unit Test geben, und am besten auch für ein paar Kombinationen davon, von denen Sie denken, dass Ihr Programm damit ein Problem haben könnte.
• Ihre Algorithmen müssen nicht besonders effizient sein, aber die Laufzeit sollte linear oder fast-linear sein. Konkret sollte ihr Programm auf einer 1 MB großen Datei nicht länger als 1 Minute brauchen.

Optionale Funktionalität:

• Erkennen von "statischen" Virusdateien mit einer festen MD5-Summe. Das sind die Dateien, die in der Datei oben mit MD5 markiert sind. Eine Spezifikation zur Berechnung der MD5-Summe einer Datei siehe http://en.wikipedia.org/wiki/MD5

• Versuchen Sie ihre Algorithmen zur Signaturerkennung effizienter zu machen. Schaffen Sie es, dass der Virencheck für eine Datei < 1 Sekunden dauert?

• Unterstützung weiterer Signaturen von ClamAV. Für eine Übersicht, siehe http://www.clamav.net/doc/latest/signatures.pdf .

Technische Realisierung:

• Um Signaturen mit mindestens einem * oder {...} gehen Sie wie folgt vor: Teilen Sie die Signatur an diesen Operatoren. Suchen Sie alle Vorkommen der so entstehenden Teile (die dann kein * oder {...} enthalten). Schauen Sie dann ob sich siese Vorkommen so zu einer Signatur zusammen setzten lassen, dass den Operatoren dazwischen genüge getan wird.
• * Beispiel 1: Die Signatur lautet A*B und in der Datei fängt A an Position 12 an und B an Position 764. (Und A hört auf, bevor B anfängt.) Dann kommt die Signatur A*B in der Datei vor.
• * Beispiel 2: Wie Beispiel 1, aber jetzt fängt B an Position 12 an und A an Position 764, und zwar jeweils nur dort. Dann kommt die Signatur A*B nicht in der Datei vor, weil die Reihenfolge nicht stimmt.
• * Beispiel 3: Die Signatur lautet A*B{10,20}C und in der Datei steht A an den Position 12..57, B steht einmal an den Positionen 74 bis 87 und einmal an den Positionen 215 bis 228, und C fängt an Position 337 an. Dann kommt die Signatur A*B{10,20}C in der Datei vor, allerdings muss man dazu das zweite Vorkommen von B nehmen, weil das erste Vorkommen (bis Position 87) zu weit von dem Vorkommen von C (ab Position 337) entfernt ist.

Für die invertierten Listen sollte jede Datei eine eindeutige ID haben; die invertierte Liste für ein Wort ist dann die Liste der IDs aller Dateien, die dieses Wort enthalten. Man braucht dann eine Variable (bei fortlaufenden IDs reicht ein std::vector), die die Zuordnung von IDs zu Dateinamen speichert.

• Am einfachsten ist es, wenn Sie jede invertierte Liste in einer eigenen Datei speichern, deren Name von dem Wort dieser invertierten Liste ableitet ist. Schöner wäre es, wenn Sie alle invertierten Listen in eine Datei schreiben. Dann brauchen Sie aber eine Art Inhaltsverzeichnis (in einer separaten Datei oder ebenfalls in der einen Indexdatei), damit Sie die invertierten Listen, die für die Suchanfragen benötigt werden, lesen können ohne die ganze Indexdatei zu lesen.
• Zur Beantwortung einer Suchanfrage einfach die Schnittmenge der invertierten Liste der in der Anfrage enthaltenen Suchworte berechnen. Die Schnittmenge enthält dann die IDs von genau den Dateien, die alle Suchworte enthalten. Zur effizienten Berechnung der Schnittmenge sollten die invertierten Listen (bei der Vorberechnung schon) sortiert werden, siehe Übungsblatt 9.

• Die result snippets kann man selber implementieren (die jeweilige Datei öffnen und nach Vorkommen der Suchworte suchen), oder aus dem Programm heraus ein externes Programm wie grep aufrufen (am einfachsten über system, siehe man 3 system, oder, wenn man die Ausgabe des externen Programms vor der Ausgabe auf den Bildschirm intern nachbearbeiten möchte, über exec, siehe man 3 exec; letzteres hat auch den Vorteil, das man einen unit test dafür schreiben kann).

Projekt 3 (selbstgewählt)

Bei dieser Alternative, ist die Spezifikation des Projektes Ihnen überlassen. Einzige Bedingung ist, dass es in Umfang und Komplexität den ersten beiden Projekten ähnlich ist. Insbesondere sollte es vom Schwierigkeitsgrad nicht zu weit darüber hinaus gehen, Ihr Tutor / Ihre Tutorin muss es schließlich verstehen und korrigieren können.

Projekt 3 ist etwas für Teilnehmer/innen, die sich in der Sprache C++ schon sehr sicher fühlen und denen die bisherigen Übungsblätter leicht gefallen sind. Wenn Sie ein solches Projekt machen wollen, kontaktieren Sie frühzeitig Ihren Tutor / Ihre Tutorin.

Projekte aus vergangenen Jahren sind aus offensichtlichen Gründen als Thema für eine selbstgewähltes Projekt ausgeschlossen.