Algorithm Engineering und Network Science (SS 2024)

Wie bereits angekündigt, kommt es in KW26 und KW27 zu Abweichungen. Konkret:

  • Am Mi, den 26.06., findet die Vorlesung regulär statt
  • Am Do, den 27.06., entfallen die Vorlesung und Übung
  • Am Mi, den 03.07., entfällt die Vorlesung
  • Am Do, den 04.07., vertritt Daniel Allendorf die Vorlesung und spricht über exaktes uniformes Ziehen von Zufallsgraphen nach Gradsequenzen. Die Übung entfällt.

Vorlesung

Dr. Manuel Penschuck

Mittwoch 12:15 - 14:00 in Hörsaaltrakt Bockenheim - H 9
Donnerstag 10:15 - 12:00 in SR 307

Sprechstunde: Nach Vereinbarung

Tutorials

Alexander Leonhardt

Donnerstag 12:30 - 14:00 in SR 307

Sprechstunde: Nach Vereinbarung

Organisation der Übungen

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt und es können bis zu drei Personen eine Abgabe einreichen (bitte alle Namen/Matrikelnummern auf der Abgabe nennen). Einmal gebildete Gruppen können nur in Rücksprache mit den Veranstaltern verändert werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Inhalt

Unser alltägliches Leben wird durch Netzwerke geprägt; Strom und Wasser erreichen uns durch entsprechende Leitungsnetze. Logistikketten stellen unsere Lebensmittel zur Verfügung und das Datennetz liefert Katzenvideos. Aber auch wir selbst bewegen uns im Straßennetz und leben meist in gleich mehreren sozialen Netzwerken.

Wenig überraschend lassen sich diese Netze als Graphen auffassen, und zeigen dann –trotz unterschiedlicher Herkunft– oft strukturelle Ähnlichkeiten. Network Science versucht diese so genannten Komplexen Strukturen zu erklären und sowohl qualitativ wie quantitativ zu analysieren. In dieser Vorlesung betrachten wir eine Auswahl von Eigenschaften von komplexen Netzwerken (z.B. Small-World, Powerlaw Gradverteilungen, Communities). Zusätzlich betrachen wir Algorithmen um solche Eigenschaten zu finden, zu produzieren, oder auszunutzen.

Prüfung

Die Prüfungsform wird während der Veranstaltung bekannt gegeben.

Übungsblätter

DownloadAusgabeAbgabeKommentar
Blatt 124. Apr30. AprAbgabe ausnahmsweise bereits am Dienstag!
Blatt 201. Mai08. Mai 
Blatt 308. Mai15. MaiSkript Seite 13 (Teile des Chernoff Beweises), siehe auch Wikipedia
Blatt 422. Mai29. Mai 
Blatt 529. Mai05. Juni 
Blatt 612. Juni19. Juni 
Blatt 724. Juni09. Juli 

Materialien