====== Seminar Algorithm Engineering (SoSe 2012) ====== | Veranstalter | [[staff:mutzel|Prof. Dr. Petra Mutzel]] | | Modul | Diplom, Master [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Master_Inf/Pflichtveranstaltungen/INF-MSc-102.pdf|INF-MSc-102 (Informatik, Angewandte Informatik)]] | | Veranstaltungsart | Seminar | | Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=110824&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|041406]] | | Forschungsbereich | Algorithmen und Komplexität | | SWS | 2 | | Max. Teilnehmer | 12 | ===== Inhalt ===== Algorithmen und Datenstrukturen sind das Herz jeder Computeranwendung. Traditionell werden Algorithmen für einfache und abstrakte Problem- und Maschinenmodelle entworfen und Leistungsgarantien werden für alle möglichen Eingaben bewiesen (z.B. //Worst-Case-Analyse//). Bei wachsenden Anforderungen an innovative Algorithmen für konkrete Anwendungen ergibt sich zunehmend eine Lücken zwischen Theorie und Praxis, in der beispielsweise Parallelisierbarkeit und Speicherhierarchien berücksichtigt werden müssen. Seit Beginn der 1990er Jahre wird deshalb eine breitere Sichtweise der Algorithmik immer wichtiger, die als //Algorithm Engineering// bezeichnet wird. Dabei stehen der Entwurf, die Analyse, die Implementierung und die experimentelle Bewertung von Algorithmen gleichberechtigt nebeneinander. Ein aktuelles Forschungsgebiet, das z.B. in der Chemie- und Bioinformatik zunehmend an Bedeutung gewinnt, befasst sich mich der Anwendung von Methoden des //Data-Minings// auf Graphen. Hierbei verwendete Graphenalgorithmen sind häufig theoretisch gut untersucht, dennoch können diese Resultate nicht direkt auf praktische Anwendungen übertragen werden: Die konkrete Problemstellung kann sich beispielsweise durch zusätzliche Nebenbedingungen von der theoretisch untersuchten Problemdefinition unterscheiden oder Teilprobleme müssen in einem Vorverarbeitungsschritt gelöst werden, um performance-kritische Anfragen anschließend effizient beantwortet zu können. Im Rahmen des Seminars sollen in diesem Semester aktuelle Themen des //Graph Data Minings// unter dem Aspekt des Algorithm Engineerings behandelt werden, ausgehend von dem Buch: [[http://www.springerlink.com/content/978-1-4419-6045-0|Managing and Mining Graph Data]]\\ Advances in Database Systems, Volume 40, 2010\\ Aggarwal, Charu C.; Wang, Haixun (Eds.) Das Buch ist als E-Book über die Seite der [[http://www.ub.tu-dortmund.de/|Universitätsbibliothek]] verfügbar. ===== Themenliste ===== ^ Nr. ^ Thema ^ Material ^ Teilnehmer ^ Abgabe ^ Termin ^ Betreuer ^ | **Graph similarity and graph queries** |||||| |1.| Exact and inexact graph matching | MMGD7 | Mike Gösker | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/01_ausarbeitung.pdf|Ausarbeitung}} | 17.07. | [[staff:kurz|Denis Kurz]] | |2.| Graph indexing | MMGD5 | Christoph Schikora | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/02_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/02_folien.pdf|Folien}} | 17.07. | [[staff:kriege|Nils Kriege]] | |3.| Substructure similarity search | [[http://dx.doi.org/10.1145/1807167.1807264|1]] | Jannic Hartwecker | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/03_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/03_folien.pdf|Folien}} | 17.07. | [[staff:kriege|Nils Kriege]] | |4.| Reachability queries | MMGD6 | Andre Droschinsky | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/04_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/04_folien.pdf|Folien}} | 17.07. | [[staff:gutwenger|Carsten Gutwenger]] | | **Pattern mining in graphs** |||||| |5.| Mining dense subgraphs | MMGD10, ([[http://dx.doi.org/10.1109/ICDE.2011.5767911|1]]) | Martin Bring | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/05_ausarbeitung.pdf|Ausarbeitung}} | 18.07. | [[staff:kriege|Nils Kriege]] | |6.| Frequent subgraph mining | MMGD12 | Sebastian Homann | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/06_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/06_folien.pdf|Folien}} | 18.07. | [[staff:kriege|Nils Kriege]] | |7.| Frequent subgraph mining in outerplanar graphs | [[http://dx.doi.org/10.1007/s10618-009-0162-1|1]] | Christopher Morris | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/07_ausarbeitung.pdf|Ausarbeitung}} | 18.07. | [[staff:zey|Bernd Zey]] | |8.| Frequent subgraph mining in graphs of bounded tree-width | [[http://dx.doi.org/10.1016/j.tcs.2010.03.030|1]] | Florian Kurpicz | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/08_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/08_folien.pdf|Folien}} | 18.07. | [[staff:zey|Bernd Zey]] | | **Graph clustering & classification** ||||| |9.| Node clustering algorithms | (MMGD9), [[http://dx.doi.org/10.1080/15427951.2004.10129093|1]] | Zhivko Zhelyazkov | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/09_ausarbeitung.pdf|Ausarbeitung}} | 19.07. | [[staff:mutzel|Petra Mutzel]] | |11.| Graph kernels | MMGD11 / [[http://jmlr.csail.mit.edu/papers/v12/shervashidze11a.html|1]] | Andriy Kandyba | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/11_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/11_folien.pdf|Folien}} | 19.07. | [[staff:kurz|Denis Kurz]] | |12.| Graph boosting | MMGD11 | Florian Bellmann | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/12_ausarbeitung.pdf|Ausarbeitung}}, {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/12_folien.pdf|Folien}} | 19.07. | [[staff:mutzel|Petra Mutzel]] | | **Algorithms for massive graphs** |||||| |10.| Streaming algorithms | MMGD13 | Stephan Schlagkamp | {{http://ls11-www.cs.tu-dortmund.de/people/kriege/seminarae-ss2012/10_ausarbeitung.pdf|Ausarbeitung}} | 19.07. | [[staff:gutwenger|Carsten Gutwenger]] | MMGD bezieht sich auf das entsprechende Kapitel im oben genannten Buch. ===== Anmeldung und Vorbesprechung ===== Es sind bereits alle Seminarplätze vergeben, eine Anmeldung ist daher nicht mehr möglich. Die Themenverteilung erfolgt bei der Vorbesprechung (Termin s. unten). ===== Ablauf des Seminars ===== Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben, die Seminarteilnehmer besprechen sich allerdings mit ihrem zugeordneten Betreuer. Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende des Semesters einen **45-minütigen** Vortrag über das festgelegte Thema; im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Bitte beachten Sie auch die [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|Hinweise]] zur Foliengestaltung! Es herrscht Anwesenheitspflicht bei allen Vorträgen. Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen **Ausarbeitung**, welche 15-20 Seiten umfasst und mit **LaTeX** erstellt wird. Mangelhafte Ausarbeitungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. ===== Termine ===== Vorbesprechung und Themenvergabe: Donnerstag, der **05.04.2012** um 14:00 Uhr (pünktlich) in OH14, Raum 202 (Seminarraum des LS11). Weitere Termine voraussichtlich: | Abgabe des Ausarbeitungskonzepts | **18.06.2012** | | Abgabe der Ausarbeitung | **25.06.2012** | | Abgabe der Präsentationsfolien (Aufbau) | **02.07.2012** | | Abgabe der Präsentationsfolien (Final) | **09.07.2012** | | Vorträge | **17.-19.07.2012**, jeweils 10:15-12:30 Uhr und 14:00-16:15 Uhr | ===== Ansprechpartner ===== Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:mutzel|Petra Mutzel]].