Technische Universität Braunschweig
  • Studium & Lehre
    • Vor dem Studium
      • Informationen für Studieninteressierte
      • Studiengänge von A-Z
      • Bewerbung
      • Fit4TU - Self-Assessment
      • Beratungsangebote für Studieninteressierte
      • Warum Braunschweig?
    • Im Studium
      • Erstsemester-Hub
      • Semestertermine
      • Lehrveranstaltungen
      • Studien-ABC
      • Studienorganisation
      • Beratungsnavi
      • Zusatzqualifikationen
      • Finanzierung und Kosten
      • Besondere Studienbedingungen
      • Gesundheit & Wohlbefinden
      • Campusleben
    • Nach dem Studium
      • Exmatrikulation und Vorlegalisation
      • Nach dem Abschluss
      • Alumni*ae
    • Strategien und Qualitätsmanagement
      • Strategiepapiere für Studium und Lehre
      • Studienqualitätsmittel
      • Studiengangsentwicklung
      • Qualitätsmanagement
      • Systemakkreditierung
      • Rechtliche Grundlagen
      • TU Lehrpreis
    • Für Lehrende
      • Informationen für Lehrende
      • Konzepte
      • Lernmanagementsystem Stud.IP
    • Kontakt
      • Studienservice-Center
      • Sag's uns - in Studium und Lehre
      • Zentrale Studienberatung
      • Immatrikulationsamt
      • Abteilung 16 - Studium und Lehre
      • Career Service
      • Projekthaus
  • Forschung
    • Forschungsprofil
      • Forschungsschwerpunkte
      • Exzellenzcluster der TU Braunschweig
      • Forschungsprojekte
      • Forschungszentren
      • Forschungsprofile der Professuren
    • Frühe Karrierephase
      • Förderung in den frühen Phasen der wissenschaftlichen Karriere
      • Promotion
      • Postdocs
      • Nachwuchsgruppenleitung
      • Junior Professur und Tenure-Track
      • Habilitation
      • Service-Angebote für Wissenschaftler*innen
    • Forschungsdaten & Transparenz
      • Transparenz in der Forschung
      • Forschungsdaten
      • Open Access Strategie
      • Digitale Forschungsanzeige
    • Forschungsförderung
      • Netzwerk Forschungsförderung
      • Datenbanken und Stiftungen
    • Kontakt
      • Forschungsservice
      • Graduiertenakademie
  • International
    • Internationale Studierende
      • Warum Braunschweig?
      • Studium mit Abschluss
      • Austauschstudium
      • TU Braunschweig Summer School
      • Geflüchtete
      • International Student Support
    • Wege ins Ausland
      • Studium im Ausland
      • Praktikum im Ausland
      • Lehren und Forschen im Ausland
      • Arbeiten im Ausland
    • Internationale Forschende
      • Welcome Support
      • Promotionsstudium
      • Service für gastgebende Einrichtungen
    • Sprachen und interkulturelle Kompetenzvermittlung
      • Deutsch lernen
      • Fremdsprachen lernen
      • Interkulturelle Kompetenzvermittlung
    • Internationales Profil
      • Internationalisierung
      • Internationale Kooperationen
      • Strategische Partnerschaften
      • Internationale Netzwerke
    • International House
      • Wir über uns
      • Kontakt & Sprechstunden
      • Aktuelles und Termine
      • International Days
      • 5. Studentische Konferenz: Internationalisierung der Hochschulen
      • Newsletter, Podcast & Videos
      • Stellenausschreibungen
  • Die TU Braunschweig
    • Unser Profil
      • Ziele & Werte
      • Ordnungen und Leitlinien
      • Allianzen & Partner
      • Hochschulentwicklung 2030
      • Stiftungsuniversität
      • Internationale Strategie
      • Fakten & Zahlen
      • Unsere Geschichte
    • Karriere
      • Arbeiten an der TU
      • Stellenmarkt
      • Berufsausbildung an der TU
    • Wirtschaft & Unternehmen
      • Unternehmensgründung
      • Freunde & Förderer
    • Öffentlichkeit
      • Veranstaltungskalender
      • Check-in für Schüler*innen
      • Hochschulinformationstag (HIT)
      • Kinder-Uni
      • Das Studierendenhaus
      • Gasthörer*innen & Senior*innenstudium
      • Nutzung der Universitätsbibliothek
    • Presse & Kommunikation
      • Stabsstelle Presse und Kommunikation
      • Medienservice
      • Ansprechpartner*innen
      • Tipps für Wissenschaftler*innen
      • Themen und Stories
    • Kontakt
      • Allgemeiner Kontakt
      • Anreise
      • Für Hinweisgeber
  • Struktur
    • Leitung & Verwaltung
      • Das Präsidium
      • Stabsstellen
      • Verwaltung
      • Organe, Statusgruppen und Kommissionen
    • Fakultäten
      • Carl-Friedrich-Gauß-Fakultät
      • Fakultät für Lebenswissenschaften
      • Fakultät Architektur, Bauingenieurwesen und Umweltwissenschaften
      • Fakultät für Maschinenbau
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Fakultät für Geistes- und Erziehungswissenschaften
    • Institute
      • Institute von A-Z
    • Einrichtungen
      • Universitätsbibliothek
      • Gauß-IT-Zentrum
      • Zentrale Personalentwicklung
      • International House
      • Projekthaus
      • Transferservice
      • Hochschulsportzentrum
      • Einrichtungen von A-Z
    • Studierendenschaft
      • Studierendenparlament
      • Fachschaften
      • Studentische Wahlen
    • Lehrer*innenbildung
      • Lehrer*innenfortbildung
      • Forschung
    • Chancengleichheit
      • Gleichstellung
      • Familie
      • Diversität
    • Kontakt
      • Personensuche
  • Suche
  • Schnellzugriff
    • Personensuche
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Mensa
    • TUconnect (Studierendenportal)
    • Lehrveranstaltungen
    • Im Notfall
    • Stud.IP
    • UB Katalog
    • Status GITZ-Dienste
    • Störungsmeldung GB3
    • IT Dienste
    • Informationsportal (Beschäftigte)
    • Beratungsnavi
    • Linksammlung
    • DE
    • EN
    • IBR YouTube
    • Facebook
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
Menü
  • Struktur
  • Fakultäten
  • Carl-Friedrich-Gauß-Fakultät
  • Institute
  • Institut für Betriebssysteme und Rechnerverbund
  • Lehrveranstaltungen
  • Lehrveranstaltungen Sommersemester 2021
Logo IBR
IBR Login
  • Institut für Betriebssysteme und Rechnerverbund
    • News
    • Wir über uns
      • Gesamtes Team
      • Anreise
      • Raumplan
      • Projekte
      • Veröffentlichungen
      • Software
      • News Archiv
    • Connected and Mobile Systems
      • Team
      • Lehrveranstaltungen
      • Abschlussarbeiten
      • Projekte
      • Veröffentlichungen
      • Software
      • Datensätze
    • Verlässliche Systemsoftware
      • Übersicht
      • Team
      • Lehre
      • Arbeiten & Jobs
      • Forschung
      • Publikationen
    • Algorithmik
      • Team
      • Lehrveranstaltungen
      • Abschlussarbeiten
      • Projekte
      • Veröffentlichungen
    • Mikroprozessorlabor
    • Studium
      • Sommersemester 2025
      • Wintersemester 2024/2025
      • Abschlussarbeiten
    • Service
      • Bibliothek
      • Mailinglisten
      • Webmail
      • Knowledgebase
      • Wiki
      • Account Management
      • Service-Status
    • Spin-Offs
      • Docoloc
      • bliq (formerly AIPARK)
      • Confidential Technologies
    • Forschungsverbünde
      • IST.hub

Netzwerkalgorithmen

Semester
Sommersemester 2021
Sommersemester 2023Sommersemester 2022Sommersemester 2020
StudiengängeWirtschaftsinformatik Bachelor, Informations-Systemtechnik Bachelor, Informatik Bachelor
IBR GruppeALG (Prof. Fekete)
ArtVorlesung & Übung
Dozent
Photo
Dr. Arne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Raum 333
Assistent
Photo
Dr. Christian Rieck
Ehemaliger Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
LP5
SWS2+1+1
Ort & Zeit Vorlesung: Dienstags, 11:30 - 13:00 Uhr
Große Übung: Donnerstags, 11:30 - 13:00 Uhr (unregelmäßig, siehe Semesterplan)
Kleine Übung: Freitags, 11:30 - 13:00 Uhr (unregelmäßig, siehe Semesterplan)

Den kompletten (vorläufigen) Semesterplan findet ihr hier (aktualisiert am 08.04.2021). Bitte beachtet, dass sich dieser auch ändern kann. Sollten sich Termine ändern, werden wir dies hier und über die Mailingliste veröffentlichen.
Beginn Vorlesung: 20.04.2021
Große Übung: 22.04.2021
Kleine Übung: 07.05.2021
Voraussetzungen keine. (Empfohlen: Algorithmen und Datenstrukturen, Basiswissen NWA)
Scheinerwerb

Studienleistung: 50% der Hausaufgabenpunkte
Prüfungsleistung: Erfolgreiche Teilnahme an der Online-Klausur

Anmeldung
Die Anmeldung für die Übungsgruppen ist abgelaufen. Falls Du Dich dennoch für die Übungsgruppen anmelden möchtest, schreibe eine kurze Mail an Dr. Arne Schmidt oder Dr. Christian Rieck mit vollem Namen, Matrikelnummer, Studiengang und Fachsemester
Bitte einloggen, um als Mitglied der Gruppe mitarb mehr Information zu erhalten.
Inhalt Die Veranstaltung untersucht Algorithmen und Eigenschaften auf Graphen. Themenbereiche die in der Vorlesung behandelt werden sind:
  • Kostenminimale aufspannende Bäume
  • Kürzeste Wege
  • Maximale Flüsse
  • Maximum Matchings
In der großen Übung werden weitere Themen besprochen, die die Themen der Vorlesung ergänzen und einen Ausblick auf teils schwerere Probleme geben sollen.
Literatur/Links
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, MIT Press, 2001.
  • Bernhard Korte, Jens Vygen: Combinatorial Optimization, Springer, 2006. Zugriff der deutschen Version über die UB: [Link]
  • William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver: Combinatorial Optimization, John Wiley & Sons, 2011.

Aktuelles

  • Die letzte Vorlesung (am 20.07.21) findet nicht über YouTube, sondern über BigBluButton (s.u.) statt und wird nicht aufgezeichnet.
  • Aufgrund der Covid-19 Pandemie, findet die Veranstaltung im Sommersemester 2021 online statt.
  • Die Mailingliste steht jetzt zur Anmeldung zur Verfügung (siehe unten!). Bitte meldet euch dort an, weil wir auch dort kurzfristig Informationen zur Veranstaltung (wie zum Beispiel Veranstaltungsbeginn und -art) verteilen.
  • Zur selbständigen Vorbereitung haben wir ein Dokument mit (vorausgesetztem) Basiswissen erstellt.

Vorlesung

Die Vorlesung findet voraussichtlich über YouTube (Playlist) statt. Fragen können beispielsweise über TU-Messenger oder alternativ Discord gestellt werden.

  • VL 1, 20.04.21 - Einführung: [slides], [Satz 2.5], [YouTube], [IBR]
  • VL 2, 27.04.21 - Kruskals Algorithmus: [slides], [Satz 2.9], [Lemma 2.12], [YouTube], [IBR]
  • VL 3, 04.05.21 - Prims Algorithmus: [slides], [Lemma 2.14], [Satz 2.15],[YouTube], [IBR]
  • VL 4, 11.05.21 - Dijkstras Algorithmus: [slides], [Satz 3.8], [YouTube], [IBR]
  • VL 5, 18.05.21 - Algorithmus von Moore, Bellman und Ford: [slides], [Satz 3.10], [YouTube], [IBR]
  • VL 6, 01.06.21 - Algorithmen von Floyd-Warshall und Johnson: [slides], [YouTube], [IBR]
  • VL 7, 08.06.21 - Algorithmus von Ford-Fulkerson: [slides], [YouTube], [IBR]
  • VL 8, 15.06.21 - Algorithmus von Edmonds-Karp: [slides], [Lemma 4.12], [Satz 4.16],[YouTube], [IBR]
  • VL 9, 22.06.21 - Algorithmus von Stoer-Wagner: [slides], [YouTube], [IBR]
  • VL 10, 29.06.21 - Algorithmus von Hopcroft-Karp: [slides], [YouTube], [IBR]
  • VL 11, 06.07.21 - Blossom-Algorithmus: [slides], [YouTube], [IBR]
  • VL 12, 13.07.21 - Ungarische Methode: [slides],[YouTube], [IBR]
  • VL 13, 20.07.21 - Zusammenfassung: [slides]

Die Ergebnisse der Quizze: [MST], [SP], [MaxFlow], [Mat]

Große Übung

Die große Übung findet an den folgenden Donnerstagen jeweils um 11:30 Uhr über BigBlueButton statt.

  • GÜ 0, 22.04.2021. Organisation, Einführung, Rückblick und Ausblick. [slides]
  • GÜ 1, 06.05.2021. Pfadkompression, Bottleneck Spannbaum, Steinerbaum Problem, Komplexität. [notizen]
  • GÜ 2, 20.05.2021. Längste Pfade, Wurmlöcher, Starker Zusammenhang, Abbiegungen. [slides], [notizen], [abbiegungen]
  • GÜ 3, 17.06.2021. Zirkulationen, Flüsse mit unteren Schranken, Matrix-Rounding, Gomory-Hu Bäume. [slides], [Multi-Terminal Network Flows]
  • GÜ 4, 01.07.2021. Metrisches Traveling Salesman Problem. [notizen], [christofides], [slightly improved heuristic]
  • GÜ 5, 15.07.2021. Stabile Matchings, 3D-Matching. [slides], [notizen]

Hausaufgaben

Die Hausaufgabenblätter findet ihr ab dem jeweiligen Datum hier. Hausaufgabenblatt 0 dient der persönlichen Vorbereitung und ist nicht relevant für die Studienleistung. Bitte beachtet den Hinweiszettel und die Merkzettel zu Beweisen, Laufzeiten und Pseudocode.

  • Hausaufgabenblatt 0 vom 19.04.2021.
  • Hausaufgabenblatt 1 vom 03.05.2021. Abgabe bis Sonntag, den 16. Mai 2021.
  • Hausaufgabenblatt 2 vom 17.05.2021. Abgabe bis Sonntag, den 06. Juni 2021.
  • Hausaufgabenblatt 3 vom 07.06.2021. Abgabe bis Sonntag, den 20. Juni 2021.
  • Hausaufgabenblatt 4 vom 21.06.2021. Abgabe bis Sonntag, den 04. Juli 2021.
    (Es wurde eine Index-Regel für verschmolzene Knoten hinzugefügt. Stand: 28.06.21)
  • Hausaufgabenblatt 5 vom 05.07.2021. Abgabe bis Sonntag, den 18. Juli 2021.

Die kleinen Übungen finden ab dem 07.05.21 jede zweite Vorlesungswoche über BigBlueButton statt. Der Link zu den jeweiligen Räumen und die Gruppeneinteilung können der nachstehenden Tabelle entnommen werden.

Gruppe Tutor Zeit Raum Teilnehmer
1 Marlin Melansek Fr., 11:30 - 13:00 BigBlueButton Raum 1 Nachnamen: A bis K
2 Tobias Wallner Fr., 11:30 - 13:00 BigBlueButton Raum 2 Nachnamen: L bis Z

Klausur

Die Klausur findet am Montag, den 16.08.2021 zwischen 08:15 Uhr und 10:15 Uhr über EvaExam statt. Die Informationen zur NWA-Klausur sind analog zu der von AuD (siehe Beitragsseite von AuD).

  • Die Klausur startet um 08:15 Uhr und endet um 10:15 Uhr.
  • Sie haben 2 Stunden Zeit für die Bearbeitung
  • Eine TAN zur Teilnahme wird etwa 30 Minuten vor Beginn der Klausur per Mail an Ihre tubs-Adresse versandt.
  • Für Fragen steht ein BigBlueButton Raum zur Verfügung
  • Bei Internetproblemen melden Sie sich per Telefon bei Arne Schmidt (0531 391 3115) oder Christian Rieck (0531 391 3114).
  • Nach der Prüfung muss ein Scan der Selbständigkeitserklärung (siehe Cloudstorage) in unsere Nextcloud hochgeladen werden: https://nextcloud.ibr.cs.tu-bs.de/s/NNcANwpjBHbssAE (Format für den Dateinamen: Nachname_Name_Matrikelnummer)

Wiederholungsprüfung

Die Wiederholungsprüfung wird als mündliche Prüfung geplant. Sobald die Anmeldungen zur Prüfung beim Prüfungsamt abgeschlossen ist, melden wir uns per Mail.

Mailingliste

Es gibt eine Mailingliste zu dieser Vorlesung. Bitte meldet euch an, denn wir werden sie nutzen, um kurzfristig Informationen zu verteilen. Um Spam und Probleme zu vermeiden, können nur Mailadressen der TU Braunschweig freigegeben werden. Solltet ihr technische Schwierigkeiten bei der Anmeldung haben, meldet euch bitte direkt per Mail bei Christian.


aktualisiert am 19.04.2022, 16:21 (dynamischer Inhalt) von Dr. Christian Rieck

Für alle

Stellen der TU Braunschweig
Jobbörse des Career Service
Merchandising
Sponsoring- & Spendenleistungen
Drittmittelgeförderte Forschungsprojekte
Vertrauenspersonen für Hinweisgeber

Für Studierende

Semestertermine
Lehrveranstaltungen
Studiengänge von A-Z
Informationen für Erstsemester
TUCard

Interne Tools

Status GITZ-Dienste
Handbuch für TYPO3 (Intern)
Corporate Design-Toolbox (Intern)
Glossar (DE-EN)
Meine Daten ändern
Hochschulöffentliche Bekanntmachungen

Kontakt

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig
Postfach: 38092 Braunschweig
Telefon: +49 (0) 531 391-0

Anreise

© Technische Universität Braunschweig
Impressum Datenschutz Barrierefreiheit