Index of /anton/lvas/effizienz-aufgabe14

Abgabe Effiziente Programme WS14/15

Sie können ein beliebiges Beispiel wählen.

Wer nichts anderes vorhat, kann die unten vorgegebene Aufgabe für dieses Semester wählen.

Natürlich können Sie, wenn Sie wollen, auch die Implementierung eines anderen Problems optimieren; allerdings hat das einige Nachteile: Sie müssen einen Teil der Zeit Ihrer Präsentation für die Erklärung des Problems und des Algorithmus aufwenden, und die Ergebnisse sind nicht direkt vergleichbar. Der Vorteil (vor allem, wenn Sie einen späteren Termin wählen) ist, dass Sie nicht das wiederholen, was andere gemacht haben, oder ein langsameres Programm präsentieren.

Bereiten Sie eine 15-18-minütige Präsentation vor (am besten machen Sie einen Probelauf, damit sich die Präsentation auch sicher in der Zeit ausgeht). Da Sie dabei nicht soviel Zeit haben wie ich in der Vorlesung, präsentieren Sie die meisten Schritte nur im Überblick (also eventuell nur, wieviel er gebracht hat), und nur ein paar besonders interessante Schritte mit mehr Details. Besonders interessant sind u.a. die Schritte, die unerwartet viel oder unerwartet wenig bringen.

Erlaubte Optimierungen

Auch wenn der Fokus bei der Vorlesung nicht bei effizienten Algorithmen lag, dürfen Sie auch Algorithmen und Datenstrukturen ändern (damit erübrigt sich die Frage, ob eine Änderung den Algorithmus ändert oder nicht).

An sich muss das optimierte Programm für die gleiche Eingabe die gleiche Ausgabe produzieren wie das Originalprogramm, insbesondere für die gemessenen Testfälle. Sie können Sich auch überlegen, bestimmte Eingaben nicht korrekt zu verarbeiten, müssen das dann aber dokumentieren und begründen, warum Sie meinen, dass das sinnvoll ist.

Sie dürfen auch die Programmiersprache ändern.

Ausgeschlossen sind allerdings Optimierungen zu Trivialprogrammen (z.B. if Eingabe=Benchmarkeingabe then print Benchmarkausgabe), da dabei zuwenig zu lernen ist.

Vorgegebene Aufgabe: N-Damen-Problem

Das N-Damen-Problem besteht darin, N Damen auf einem NxN-Schachbrett so zu setzen, dass keine Dame eine andere schlagen kann. Unser spezielles Problem besteht darin, alle Lösungen zu zählen.

Das vorgegebene Programm ist in Java geschrieben und von dem in Pascal geschriebene Programm von Niklaus Wirth aus seinem Algorithmen-Lehrbuch abgeleitet (daher ist der Programmierstil auch nicht idiomatisches Java). Das Programm implementiert Backtracking mittels Rekursion.

Bei einem Aufruf mit

perf stat -e cycles -e instructions -e cache-misses -e branch-misses java nqueens 16

erhielt ich auf der g0.complang.tuwien.ac.at die folgende Ausgabe:

14772512

 Performance counter stats for 'java nqueens 16':

   523831716202  cycles                   #      0.000 M/sec
   801011053783  instructions             #      1.529 IPC  
         237721  cache-misses             #      0.000 M/sec
     7488545479  branch-misses            #      0.000 M/sec

  155.371804861  seconds time elapsed

Das sind die Basiswerte, mit denen Sie Ihre Lösung vergleichen sollten (am Besten, indem Sie einen Speedup-Faktor angeben). Relevant sind vor allem die Zyklen, die anderen Werte können aber zur Erklärung der gemessenen Zyklen dienen.

Sie können Ihr Programm (und Doku dazu, z.B. Ihre Präsentation) im Web veröffentlichen (wird nicht beurteilt), und zwar indem Sie auf /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2014w ein Verzeichnis anlegen und Ihre Dateien in diesem Verzeichnis ablegen.

Aufgaben vom [WS02/03 | WS03/04 | WS04/05 | WS05/06 | WS06/07 | WS07/08 | WS08/09 | WS09/10 | WS10/11 | WS11/12 | WS12/13 | WS13/14 ]

Termin/Anmeldung zur Präsentation

Die Termine sind:

9.1., 16.1., 23.1.

Die Terminvergabe erfolgt, über unser Web-Anmeldesystem. Und zwar müssen Sie dabei folgendermaßen vorgehen:

Eines der Mitglieder der Gruppe klickt auf "Gruppe bilden" und trägt die Matrikelnummer seiner Partner ein (zur Gruppengröße siehe unten).
Wenn die Gruppe gebildet ist, sollte eines der Gruppenmitglieder auf "Abgabegespräche anzeigen" und "Termine anzeigen" klicken, um sich dort zum Präsentationstermin anzumelden.

Im WS 2014/2015 ist im Normalfall eine Gruppengröße von 3 Personen vorgesehen. Wenn Sie eine andere Gruppengröße bilden wollen, kontaktieren Sie mich. Beachten Sie allerdings, dass die Anzahl der Präsentationstermine begrenzt ist, sodass wir nur eine begrenzte Zahl kleinerer Gruppen akzeptieren können.

Anton Ertl

Name	Last modified	Size

Parent Directory		-
eightqueens.pascal	11-Nov-2014 16:34	1.3K
nqueens.class	13-Nov-2014 16:39	1.2K
nqueens.java	12-Nov-2014 17:42	1.7K

Apache/2.2.22 (Debian) DAV/2 mod_fcgid/2.3.6 PHP/5.4.36-0+deb7u3 mod_python/3.3.1 Python/2.7.3 mod_ssl/2.2.22 OpenSSL/1.0.1e mod_perl/2.0.7 Perl/v5.14.2 Server at www.complang.tuwien.ac.at Port 80