7905
Comment:
|
9989
|
Deletions are marked like this. | Additions are marked like this. |
Line 18: | Line 18: |
== Projekt 1 (Suchmaschine) == | == Projekt 1 (Snake) == |
Line 20: | Line 20: |
'''Kurzbeschreibung:''' Eine Suchmaschine für eine gegebene Menge von Dateien auf der eigenen Festplatte. | '''Kurzbeschreibung:''' Realisierung einer einfachen Version des gleichnamigen Videospiels, mittels ASCII Grafik. Siehe zum Beispiel http://www.youtube.com/watch?v=SAF95FAV-6M . |
Line 23: | Line 23: |
* Ein ausführbares Programm ''!BuildIndexMain'', das eine (über die Kommandozeile) gegebene Menge von Dateien "parsed" (= in die einzelnen Worte zerlegt), dafür einen invertierten Index baut (= pro Wort, das irgendwo vorkommt, die Liste aller Dateien, die dieses Wort enthalten, berechnet), und diesen in einer bzw. mehreren Datei speichert (siehe "Technische Realisierung"). * Ein ausführbares Programm ''!QueryIndexMain'', das mit Hilfe eines zuvor gebauten Indexes eine gegebene Suchanfrage (= einfach eine Folge von Wörtern, wie bei Google) beantwortet, und den Namen von den Dateien (mit vollständiger Pfadangabe) zurückliefert, die diese Suchworte enthalten. Dabei sollte von dem vorberechneten Index nur der Teil eingelesen werden, der auch zur Beantwortung der Suchanfrage benötigt wird. * Zusätzlich zu den Namen der Dateien sollten auch Zeilen aus der Datei angezeigt werden, die die eingegebenen Suchworte enthalten, sogenannte ''result snippets'', siehe "Technische Realisierung". |
* 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. |
Line 28: | Line 32: |
* Eine Kommandozeilenoption mit der man den Namen von (einem oder mehreren) Verzeichnissen übergeben kann, die dann rekursiv durchsucht werden. * Eine Indexdatei, statt im einfachsten Fall eine pro indiziertem Suchwort. * Markierung der Suchworte in den result snippets. * Höhere Gewichtung von Worten, die im Dateinamen bzw. im Pfad zu der Datei vorkommen. * Was immer Ihnen einfällt. |
* 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. |
Line 35: | Line 39: |
* 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. | * 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 [[https://ad-teaching.informatik.uni-freiburg.de/cplusplus-ss2012/virus-signatures.txt|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. |
Line 40: | Line 70: |
== Projekt 2 (Pong) == '''Kurzbeschreibung:''' Realisierung einer einfach Version des Uralt-Video-Spiels ''Pong'' mit ASCII-Zeichen auf der Konsole. Siehe zum Beispiel http://de.wikipedia.org/wiki/Pong oder http://www.youtube.com/watch?v=BkzK9q_FcH0 . '''Geforderte Funktionalität:''' * Ein ausführbares Programm ''!PongMain'', mit dem die Grundversion des Spieles gespielt werden kann (über insgesamt vier Tasten, zwei für das Auf und Ab des linken Schlägers, zwei für das Auf und Ab des rechten Schlägers) * Mitzählen und Anzeige des Spielstandes, wer zuerst 3 Punkt hat, hat gewonnen * Größe des Spielfeldes (Anzahl Reihen und Spalten) über Kommandozeilenparameter einstellbar. Ebenso die Länge des Schläger und die Geschwindigkeit des Spieles. Vernünftige Defaultwerte dafür. '''Optionale Funktionalität:''' * "Anschneiden" des Balles (falls der Schläger beim Ausprall des Balles gerade in Bewegung ist / war). * Verändern der Schlägergröße, Spielgeschwindigkeit, etc. während des Spiels. * Möglichkeit, dass der Computer einen der Spieler steuert, mit einer einstellbaren "Geschicklichkeit" * Mehrere Spiele, Merken des Highscores * Was immer Ihnen einfällt. '''Technische Realisierung:''' * Positionierung auf dem Bildschirm mittels ANSI espace codes: http://en.wikipedia.org/wiki/ANSI_escape_code . Siehe dazu auch das einfach Beispiel aus der Vorlesung. Damit kann auch der Bildschirm gelöscht werden, in verschiedenen Farben oder fett gedruckt werden, etc. Sie sollten immer nur soviel malen wie nötig, also nicht jedes Mal das ganze Spielfeld neu malen, wenn sich nur wenige Zeichen darauf verändert haben. * Alternativ können Sie auch die "Curses" Bibliothek benutzen: http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf , die ist portabler. |
|
Line 62: | Line 73: |
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 muss es schließlich verstehen und korrigieren können. | 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. |
Line 64: | Line 75: |
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. | 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. |
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.