Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teaching:proseminar-ads-ws2019 [2019-07-04 14:26] Nils Kriege [Inhalt] |
teaching:proseminar-ads-ws2019 [2019-10-22 00:04] (current) Nils Kriege [Ablauf] |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| | Veranstalter | [[staff:kriege|Dr. Nils Kriege]] | | | Veranstalter | [[staff:kriege|Dr. Nils Kriege]] | | ||
| | Veranstaltungsart | Proseminar mit Präsentationskurs ([[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-P/INF-BSc-110.pdf|INF-BSc-110]], Elemente 1 und 2)| | | Veranstaltungsart | Proseminar mit Präsentationskurs ([[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-P/INF-BSc-110.pdf|INF-BSc-110]], Elemente 1 und 2)| | ||
| - | | Veranstaltungsnummer | N/A | | + | | Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=217885&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040609]] | |
| | SWS | 3 | | | SWS | 3 | | ||
| | Max. Teilnehmer | 16 | | | Max. Teilnehmer | 16 | | ||
| + | | Moodle | [[https://moodle.tu-dortmund.de/course/view.php?id=16781|lsf-ADS-19_2]] | | ||
| ===== Inhalt ===== | ===== Inhalt ===== | ||
| - | Als Folge der Digitalisierung sind Daten in zunehmend großer Menge verfügbar und ihre automatisierte Analyse gewinnt an Bedeutung. Die Daten können sich dabei je nach Anwendungsgebiet in ihrer Art stark unterscheiden. Beispielsweise können soziale Netzwerke, Moleküle sowie Straßen- und Rechnernetze durch Graphen repräsentieren werden, während sich Häufigkeitsverteilungen von Ereignissen durch Histogramme beschreiben lassen. Im Rahmen der Analyse treten die unterschiedlichsten Probleme auf. Die Analyse von Graphen beruht auf graphentheoretischen Konzepten wie Graphisomorphie und Graphenalgorithmen. Die Wasserstein-Metrik kann zum Vergleich von Verteilungen herangezogen werden und ihre Berechnung steht in einem engen Zusammenhang mit Transport- und Flussproblemen in Graphen. Die effiziente Berechnung von Maßen für den Vergleich von Ranglisten erinnert an klassische Sortierverfahren, Methoden des hierarchischen Clustering an die Berechnung minimaler Spannbäume in Graphen. | + | Die Veranstaltung besteht aus einem Proseminar mit integriertem Präsentationskurs. |
| + | |||
| + | ==== Proseminar ==== | ||
| + | Als Folge der Digitalisierung sind Daten in zunehmend großer Menge verfügbar und ihre automatisierte Analyse gewinnt an Bedeutung. Die Daten können sich dabei je nach Anwendungsgebiet in ihrer Art stark unterscheiden. Beispielsweise können soziale Netzwerke, Moleküle sowie Straßen- und Rechnernetze durch Graphen repräsentieren werden, während sich Häufigkeitsverteilungen von Ereignissen durch Histogramme beschreiben lassen. Im Rahmen der Analyse treten die unterschiedlichsten Probleme auf. Die Analyse von Graphen beruht auf graphentheoretischen Konzepten wie Graphisomorphie und Graphenalgorithmen. Zur Bestimmung der Ähnlichkeit von Verteilungen kann die Wasserstein-Metrik herangezogen werden, deren Berechnung wiederum in einem engen Zusammenhang mit Transport- und Flussproblemen in Graphen steht. Die effiziente Berechnung von Maßen für den Vergleich von Ranglisten erinnert an klassische Sortierverfahren, Methoden des hierarchischen Clustering an die Berechnung minimaler Spannbäume in Graphen. | ||
| Im Rahmen des Proseminars möchten wir uns mit Algorithmen für ausgewählte Probleme befassen, die im Data-Mining und Maschinellen Lernen auftreten. | Im Rahmen des Proseminars möchten wir uns mit Algorithmen für ausgewählte Probleme befassen, die im Data-Mining und Maschinellen Lernen auftreten. | ||
| + | |||
| + | ==== Präsentationskurs ==== | ||
| + | Der Kurs führt in grundlegende Präsentationstechniken ein. Es werden unter anderem die folgenden Themen behandelt: | ||
| + | |||
| + | * Verfassen wissenschaftlicher Ausarbeitungen | ||
| + | * Einführung in die Kommunikationstheorie | ||
| + | * Mündliche Präsentation wissenschaftlicher Inhalte | ||
| + | * Foliengestaltung | ||
| + | |||
| + | Darüber hinaus werden grundlegende Funktionen des Textsatzsystems LaTeX für die Erstellung von Ausarbeitungen und Vortragsfolien behandelt. | ||
| + | |||
| ===== Themen ===== | ===== Themen ===== | ||
| - | <WRAP todo center round big 60% bigger> | + | ^ Nr. ^ Thema ^ Teilnehmer ^ Quellen ^ |
| - | Eine Liste möglicher Themen und geeignete Literatur werden rechtzeitig vor der Themenvergabe im Rahmen der Vorbesprechung bekanntgegeben. | + | |**Zuordnungsprobleme** |||| |
| - | </WRAP> | + | | 1| Theoretische Grundlagen: Heiratssatz, perfekte Matchings | Jan Schülling | 1, Abschnitt 2.1 | |
| + | | 2| Theoretische Grundlagen: Das Assignment Polytop | | 1, Abschnitt 2.2 | | ||
| + | | 3| Matchings in bipartitten Graphen: Grundlagen | Jin Ke | 1, Abschnitt 3.1 und 3.2 | | ||
| + | | 4| Algorithmus von Hopcroft und Karp | Rand Serjawi | 1, Abschnitt 3.3 | | ||
| + | | 5| Matchings in konvexen bipartiten Graphen | Andreas Rüb | 1, Abschnitt 3.5 | | ||
| + | | 6| Das lineare Assignment Problem: Die ungarische Methode | Hendrik Zemke | 1, Abschnitt 4.1 und 4.2 (ohne 4.2.3) | | ||
| + | | 7| Die ungarische Methode mittels kürzester Wege | Burak Özkan | 1, Abschnitt 4.4 | | ||
| + | | 8| Das quadratische Assignment Problem | Daniel Lensker | 1, Abschnitt 7.1 | | ||
| + | |**Transportprobleme** |||| | ||
| + | | 9| Die Probleme von Monge und Kantorovich | Fatima Taleb | 2, Abschnitt 2 | | ||
| + | | 10| Algorithmen: LP und Flußformulierungen | Peter Tisoczki | 2, Abschnitt 3 | | ||
| + | |**Optimale Spannbäume** |||| | ||
| + | | 11| Single-linkage Clustering | George Mamar | 9 | | ||
| + | | 12| Algorithmen von Borůvka und Jarnik | Carsten Kellner | 10 | | ||
| + | |**Spektren von Graphen** |||| | ||
| + | | 13| Graph-Spektrum | Josef Schneider | 11, Abschnitt 1.1-1.7 | | ||
| + | | 14| Eigenwerte und Eigenvektoren | Jonathan Liening | 11, Abschnitt 3.1-3.6 | | ||
| + | | 15| Anwendungen von Eigenvektoren | | 11, Abschnitt 3.13 | | ||
| + | |**Ausgewählte Themen** |||| | ||
| + | | 16| PageRank | Mohamad Nassar | 3 | | ||
| + | | 17| Network Alignment: IsoRank and NSD | Benjamin Biehler | 4 | | ||
| + | | 18| Kendal's Tau und seine Berechnung | Roman Leis | 5, 6 | | ||
| + | | 19| Die Softassign und Softmax Methode | Jonas Grobe | 7 | | ||
| + | | 20| Optimale Schnitte für Baummetriken | | 8 | | ||
| + | | 21| Locality-Sensitive Hashing | Sergius Becker | 3 | | ||
| + | |||
| + | * [1] R.E. Burkard, M. Dell'Amico, and S. Martello. Assignment Problems. SIAM, 2012. | ||
| + | * [2] G. Peyré, M. Cuturi. [[http://dx.doi.org/10.1561/2200000073|Computational Optimal Transport]]. Foundations and Trends in Machine Learning 11(5-6): 355-607, 2019. | ||
| + | * [3] J. Leskovec, A. Rajaraman, J.D. Ullman. [[http://infolab.stanford.edu/~ullman/mmds/book.pdf|Mining of Massive Datasets]], 2014. | ||
| + | * [4] G. Kollias, S. Mohammadi, and A. Grama. Network similarity decomposition (NSD): A fast and scalable approach to network alignment. IEEE Tranactions on Knowledge and Data Engineering, 24(12), 2012. | ||
| + | * [5] H. Abdi. Kendall rank correlation. Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage, 2007. | ||
| + | * [6] W. Knight. A Computer Method for Calculating Kendall's Tau with Ungrouped Data. Journal of the American Statistical Association. 61 (314): 436–439, 1966. | ||
| + | * [7] S. Gold, A. Rangarajan. Softassign versus Softmax: Benchmarks in Combinatorial Optimization. NIPS: 626-632, 1995. | ||
| + | * [8] M. Karpinski, A. Lingas, D. Sledneu. Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113(12): 447-451, 2013. | ||
| + | * [9] J.C. Gower, G.J. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C. 18 (1): 54–64, 1969. | ||
| + | * [10] J. Nešetřil, H. Nešetřilová. [[https://www.math.uni-bielefeld.de/documenta/vol-ismp/30_nesetril-nesetrilova.pdf|The Origins of Minimal Spanning Tree Algorithms - Borůvka und Jarnik]], Documenta Mathematica, 2012 | ||
| + | * [11] A.E. Brouwer, W.H. Haemers: [[https://www.win.tue.nl/~aeb/2WF02/spectra.pdf|Spectra of Graphs - Monograph]], Springer, 2011 | ||
| Line 23: | Line 74: | ||
| Diese Veranstaltung ist ein Proseminar für Studierende im Grundstudium. Sie umfasst 3SWS und beinhaltet einen Präsentationskurs. | Diese Veranstaltung ist ein Proseminar für Studierende im Grundstudium. Sie umfasst 3SWS und beinhaltet einen Präsentationskurs. | ||
| - | 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 regelmäßigen Treffen im Rahmen des Präsentationskurses geben und ggf. themenbezogene Einzelgespräch. | + | 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 regelmäßigen Treffen im Rahmen des Präsentationskurses geben und ggf. themenbezogene Einzelgespräche. |
| - | Die schriftliche Ausarbeitung soll **10-12 Seiten** umfassen und mit **LaTeX** erstellt werden. Die Abgabe erfolgt per E-Mail als PDF. | + | Die schriftliche Ausarbeitung soll **10-12 Seiten** umfassen und mit **LaTeX** erstellt werden ({{:teaching:proseminar-ads-ws2019:template_ads_ws2019.zip|Vorlage}}). Die Abgabe erfolgt per E-Mail als PDF. |
| Es wird empfohlen, rechtzeitig vor der Abgabe der schriftlichen Ausarbeitung dem Betreuer ein kurzes Konzeptpapier vorzulegen, in dem der Inhalt und Aufbau der Ausarbeitung stichpunktartig erläutert wird. Denn eine Aufgabe der Teilnehmer/innen besteht auch darin, den zu präsentierenden Stoff aus der Literaturquelle sorgsam auszuwählen. Es geht nicht darum, den ganzen Inhalt zu präsentieren, sondern die interessanten Aspekte. Hierbei ist eine frühzeitige Rückmeldung oft hilfreich. Der Inhalt der Ausarbeitung stimmt im Allgemeinen mit dem Inhalt der späteren Präsentation überein. | Es wird empfohlen, rechtzeitig vor der Abgabe der schriftlichen Ausarbeitung dem Betreuer ein kurzes Konzeptpapier vorzulegen, in dem der Inhalt und Aufbau der Ausarbeitung stichpunktartig erläutert wird. Denn eine Aufgabe der Teilnehmer/innen besteht auch darin, den zu präsentierenden Stoff aus der Literaturquelle sorgsam auszuwählen. Es geht nicht darum, den ganzen Inhalt zu präsentieren, sondern die interessanten Aspekte. Hierbei ist eine frühzeitige Rückmeldung oft hilfreich. Der Inhalt der Ausarbeitung stimmt im Allgemeinen mit dem Inhalt der späteren Präsentation überein. | ||
| Line 39: | Line 90: | ||
| Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. | Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. | ||
| - | /* | + | |
| === Termine === | === Termine === | ||
| ^ Termin ^ Datum ^ Zeit ^ Ort ^ | ^ Termin ^ Datum ^ Zeit ^ Ort ^ | ||
| - | | **Vorbesprechung** | **09.10.2017** | **14:15 -- 15:45** | R202, OH14 | | + | | **Vorbesprechung** | **08.10.2019** | **14:15 -- 15:45** | R202, OH14 | |
| - | | **Präsentationskurs** | **23.10.2017** | **14:15 -- 17:45** | R202, OH14 | | + | | **Präsentationskurs** | **22.10.2019** | **14:15 -- 17:45** | R202, OH14 | |
| | Abgabe eines Ausarbeitungskonzepts | optional, nach Bedarf ||| | | Abgabe eines Ausarbeitungskonzepts | optional, nach Bedarf ||| | ||
| - | | Abgabe der Ausarbeitung | 22.11.2017 | 23:59 | --- | | + | | Abgabe der Ausarbeitung | 17.11.2019 | 23:59 | --- | |
| - | | **Besprechung der Ausarbeitungen** | **04.12.2017** | **14:15 -- 17:45** | R202, OH14 | | + | | **Besprechung der Ausarbeitungen** | **26.11.2019** | **14:15 -- 17:45** | R202, OH14 | |
| - | | **Präsentationskurs** | **11.12.2017** | **14:15 -- 17:45** | R202, OH14 | | + | | **Präsentationskurs** | **10.12.2019** | **14:15 -- 17:45** | R202, OH14 | |
| - | | **Präsentationskurs** | **18.12.2017** | **14:15 -- 17:45** | R202, OH14 | | + | | **Präsentationskurs** | **17.12.2019** | **14:15 -- 17:45** | R202, OH14 | |
| - | | Abgabe der Ausarbeitung (finale Version) | 07.01.2018 | 23:59 | --- | | + | | Abgabe der Ausarbeitung (finale Version) | 06.01.2020 | 23:59 | --- | |
| - | | **Kurzvorträge zur Probe** | **08.01.2018** | **14:15 -- 17:45** | R202, OH14 | | + | | **Kurzvorträge zur Probe** | **07.01.2020** | **14:15 -- 17:45** | R202, OH14 | |
| - | | Abgabe der Folien | 23.01.2018 | 23:59 | --- | | + | | Abgabe der Folien | 22.01.2020 | 23:59 | --- | |
| - | | **Besprechung der Folien** | **29.01.2018** | **14:15 -- 17:45** | R202, OH14 | | + | | **Besprechung der Folien** | **28.01.2020** | **14:15 -- 17:45** | R202, OH14 | |
| - | | **Vorträge** | **05.--06.02.2018** || R304, OH14 | | + | | **Vorträge** | **05.--07.02.2020** || R202, OH14 | |
| + | |||
| + | /* | ||
| === Zeitplan === | === Zeitplan === | ||
| | ^ Montag, 05.02.2018 ^ Dienstag, 06.02.2018 ^ | | ^ Montag, 05.02.2018 ^ Dienstag, 06.02.2018 ^ | ||