Achtung: Aufgrund von Wartungsarbeiten des BRZ-SAP Systems können im TISS derzeit Fehler auftreten. Die Wartungsarbeiten sind bis 27.06.2022 angesetzt. Vielen Dank für Ihr Verständnis.

191.126 Competitive Programming for Programming Contests
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2022S, VU, 2.0h, 3.0EC
TUWEL

LVA-Bewertung

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • Programmierprobleme schnell und detailliert zu analysieren,
  • die notwendigen, effizienten Algorithmen zum Lösen von Programmieraufgaben zu kennen und 
  • effiziente Programmiertechniken selbstständig beim Erstellen einer korrekten Lösung anzuwenden.

Inhalt der Lehrveranstaltung

Einführung und Überblick über Programming Contests

Detaillierte Analyse des ACM ICPC-Programmierwettbewerbs

  • Arten der Probleme
  • Ein- und Ausgabeformate
  • Funktionsweise Online Judge
  • Aktuelle Contests

Vorstellung häufig benötigter Algorithmen

  • Graphalgorithmen (Breiten- und Tiefensuche, Single Source Shortest Path)
  • String-Matching
  • Zahlensysteme, Big Integer Programming
  •  Sortieren

 Programmiertechniken

  • Dynamic Programming
  • Backtracking
  • Branch-and-Bound
  • Encodings

Spezielle Algorithmen und deren Implementierung

  • Dijkstra
  • Knuth-Morris-Pratt
  • Bellman-Ford
  • Kruskal’s Algorithm

Effiziente Programmiertechniken

  • Syscalls vermeiden
  • Testbaren Code schreiben
  • Datentypen (Breite, Packing)
  • Code Inlining
  • Loop Unrolling
  • Effiziente Datenstrukturen (hashes, adjacency lists vs. arrays, etc.)

Überdies ist es ein Ziel, dass die besten Teams die TU Wien beim “Central Europe Regional Contest” (CERC) des ACM ICPC-Programmierwettbewerbs vertreten.

 

Methoden

  • Programmierübungen
  • Lösen von Problemen vergangener Programmierwettbewerbe

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

ECTS breakdown

lectures: 10h (5x2h)
exercises: 6h (3x2h)
assignments: 35h (3x15h)
exam preparation: 14h
total: 75h = 3 ECTS

# News for 2022S

Wir werden uns am 10.3.2022 im EI 6 Eckert HS treffen. Bis dahin werde ich noch keine Personen offiziell für die LVA bestätigen.

Wir werden bei der Vorbesprechung auf den Modus der LVA eingehen und Gruppen finden. Da die Plätze limitiert sind, möchte ich vor allem keine Personen vorzeitig ablehnen müssen, da wahrscheinlich noch einige Studierende abspringen werden.

Am 10.3. werde ich auch eine Einführung in den Programmierwettbewerb  "ICPC" geben.

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.13:00 - 15:0024.03.2022 - 30.06.2022EI 6 Eckert HS Vorlesung
Di.17:00 - 19:0007.06.2022Seminarraum DE0110 Meeting with ICPC sponsors
Competitive Programming for Programming Contests - Einzeltermine
TagDatumZeitOrtBeschreibung
Do.24.03.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.31.03.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.07.04.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.28.04.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.05.05.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.12.05.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.19.05.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.02.06.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Di.07.06.202217:00 - 19:00Seminarraum DE0110 Meeting with ICPC sponsors
Do.09.06.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.23.06.202213:00 - 15:00EI 6 Eckert HS Vorlesung
Do.30.06.202213:00 - 15:00EI 6 Eckert HS Vorlesung

Leistungsnachweis

Die Bewertung besteht aus zwei Teilen: ein Übungs- und Prüfungsteil.

Der Übungsteil sieht das Lösen von Programmieraufgaben in Gruppen vor.

Im Prüfungsteil muss man eine Aufgabe selbstständig bearbeiten.

LVA-Anmeldung

Von Bis Abmeldung bis
01.02.2022 00:00 24.03.2022 23:59 01.04.2022 23:59

Anmeldemodalitäten

Dieser Kurs ist speziell für Studierende gedacht, die die TU Wien bei dem ACM ICPC-Wettbewerb vertreten können. Deshalb ist der Kurs für Studierende offen, welche noch keine 8 Semester absolviert haben.

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

Ein gewisses Verständnis der folgenden Gebiete wird vorausgesetzt:

  • gute Kenntnis mind. einer der folgenden Programmersprachen: C/C++, Java, Python
  • Betriebssysteme
  • Compiler
  • Datenstrukturen
  • Graphentheorie
  • Linux
  • grundlegende Algorithmen (z.B. Quicksort)

Sprache

Englisch