Back
Semester | spring semester 2018 |
Course frequency | Irregular |
Lecturers | Peter Zaspel (peter.zaspel@unibas.ch, Assessor) |
Content | Unser Alltag ist voll von Aufgabenstellungen, die durch Graphen und davon abgeleiteten Datenstrukturen modelliert werden können. Dies reicht von der Routenplanung in Navigationsgeräten und Abfragen bei Online-Fahrplänen über die Modellierung und Optimierung von Produktionsprozessen bis hin zu Suchalgorithmen im Internet. Im Rahmen dieser Vorlesung wollen wir uns einen einen Überblick über Graphen, Bäume und Netzwerke verschaffen. Diese Datenstrukturen werden wir zunächst modellieren, so dass wir einen einheitlichen mathematischen Formalismus verwenden können. Er ermöglicht es, wesentliche Eigenschaften wie zum Beispiel den (starken) Zusammenhang zu definieren und zu analysieren. Schliesslich sollen klassische Algorithmen zur Durchmusterung und zum Beispiel für die Bestimmung kürzester Wege und maximaler Flüsse diskutiert werden. Wesentlich ist hierbei, dass wir auch stets die Korrektheit und Komplexität der Algorithmen beweisen, so dass wir ein solides theoretisches Fundament für Algorithmen auf Graphen, Bäumen und Netzwerken erarbeiten. Darüberhinaus werden wir immer wieder versuchen, in kurzen, ausblicksartigen Beispielen einen Eindruck von weiteren, aktuellen Anwendungen von Graphen zu erhalten. Diese können zum Beispiel im Bereich der graphbasierten linearen Löser, des Rankings bei Suchmaschinen, der Visualisierung über Spektren von Graphen, der optimalen Partitionierung von Ortsdiskretisierungen für High Performance Computing und der Repräsentationen für maschinelles Lernen auf Graphen liegen. Im Rahmen der vorlesungsbegleitenden Übungen werden wir sowohl theoretische Aufgaben lösen als auch einige der besprochenen Algorithmen im Rechner umsetzen. |
Comments | Das Kursmaterial sowie weitergehende Informationen zu Übungsbetrieb, Examen, etc. wird über den ADAM-Workspace zur Vorlesung bereit gestellt. |
Weblink | ADAM-Workspace zur Vorlesung |
Admission requirements | Grundkenntnisse aus der Linearen Algebra sind wünschenswert |
Course application | Amelden: via MOnA; Abmelden: Studiendekanat (schriftlich) |
Language of instruction | German |
Use of digital media | Online, mandatory |
Course auditors welcome |
Interval | Weekday | Time | Room |
---|
No dates available. Please contact the lecturer.
Modules |
Modul Applications and Related Topics (Bachelor's degree subject: Computer Science) Modul Mathematical Foundations of Computer Science (Bachelor's degree subject: Computer Science) Module Applications and Related Topics (Bachelor Computer Science) Module Applied Mathematics (Bachelor Mathematics) Module Applied Mathematics (Computational Mathematics) (Bachelor Computational Sciences) Module Mathematical Foundations of Computer Science (Bachelor Computer Science) |
Assessment format | main lecture exam |
Assessment registration/deregistration | Reg.: in 'course reg.'; dereg.: Dean of Std. Off. in writing |
Repeat examination | one repetition, best attempt counts |
Scale | 1-6 0,5 |
Repeated registration | no repetition |
Responsible faculty | Faculty of Science, studiendekanat-philnat@unibas.ch |
Offered by | Fachbereich Mathematik |