Hasso-Plattner-Institut
Hasso-Plattner-Institut
  
Login
  • de
 

Competitive Programming (Sommersemester 2018)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Pascal Lenzner (Algorithm Engineering)

Beschreibung

Beim Competitive Programming geht es darum, möglichst schnell

möglichst gut zu programmieren. Die Zeit zum Programmieren ist

beschränkt. Die Korrektheit und Effizienz wird über eine Online-Judge

mit unbekannten Test-Cases überprüft. Diese Art der

Programmierwettbewerbe haben eine lange Tradition. Die Association for

Computing Machinery (ACM) richtet seit 1970 jährlich den International Collegiate Programming Contest (ICPC) aus. An diesem Format werden wir uns orientieren.

Beim

ACM-ICPC geht es darum, daß Teams von drei Studenten einer Uni an einem

Computer möglichst viele Probleme gemeinsam lösen. Gewonnen hat, wer

nach fünf Stunden mit seinen Programmen die meisten Aufgaben richtig

gelöst hat. Es gibt fünf typische Arten von Aufgaben: Graphen-Probleme

(z.B. Dijkstra), Suchprobleme (z.B. Backtracking), Geometrische Probleme

(z.B. Schnittbildung), zahlentheoretische Probleme (z.B.

Primzahl-Zerlegung), und sonstige Probleme (z.B. Brettspiele oder

Parser). Das Problem Set Archive bietet über tausend Probleme, welche online gelöst werden können.

Das HPI hat im letzten Jahr zum ersten Mal am europäischen Wettbewerb

des ACM-ICPC teilgenommen. Das Ziel ist, auch für das Jahr 2018 ein HPIUP-Team für den nordwesteuropäischen Regionalausscheid des ACM-ICPC (NWERC)

aufzubauen und zu trainieren. Dies werden wir im Rahmen eines

interaktiven Projektseminars umsetzen. Jeder Studierende am HPI und am

IfI der UP ist dazu eingeladen.

Voraussetzungen

Voraussetzungen sind gute Programmierkentnisse in C/C++ und ein

Basiswissen über Algorithmik, beispielsweise aus den Veranstaltungen Theoretische Informatik 1 , Einführung in die Algorithmik oder Algorithmix

Wir setzen Grundkenntnisse in den Folgenden Bereichen voraus:

  • Algorithmenentwurfsmethoden: Greedy, Divide and Conquer, dynamisches Programmieren, Backtracking und Rekursion
  • Grundlegende Datenstrukturen: Arrays, Listen, Stacks, Queues, binäre Suchbäume, binäre Heaps, Adjazenzlisten und -matrizen
  • Standardthemen

    der Algorithmik: O-Notation, Sortieren, Suchen, Hashing, einfache

    Graphenalgorithmen (z.B. Baumtraversierung, Breiten- und Tiefensuche)

Lern- und Lehrformen

Das Projektseminar soll maßgeblich von einer lebhaften interaktiven

Diskussion unterschiedlicher Lösungsansätze und Tipps und Tricks geprägt

sein. Zudem werden im Laufe des Seminars hilfreiche Konzepte

eingeführt.    

Leistungserfassung

Im Laufe des Seminars wird es wöchentlich Programmieraufgaben geben,

deren Lösung dann per Online-Judge ausgewertet und im Seminar diskutiert

werden. Neben den wöchentlichen Aufgaben wird es mehrere Live-Contests

geben, in welchen wir einen echten Progammierwettbewerb simulieren. 

Die

Bewertung der Veranstaltung basiert zu 50% auf den wöchentlichen

Aufgaben und zu 50% auf den Contests im Laufe des Semesters.

Allgemeine Information

  • Semesterwochenstunden : 4
  • ECTS : 6
  • Benotet : Ja
  • Einschreibefrist : 20.04.2018
  • Programm : IT-Systems Engineering BA
  • Lehrform : PS
  • Belegungsart : Wahlpflicht

Module

  • ISAE-Grundlagen
  • ISAE-Vertiefung
  • OSIS-Grundlagen
  • OSIS-Vertiefung
  • SAMT-Grundlagen
  • SAMT-Vertiefung

Zurück