Fakultät für Informatik | KIT |  Deutsch  | English

Kontakt

Am Fasanengarten 5

Geb. 50.34

D-76131 Karlsruhe

Tel.: + 49 721 608-44205
Fax: + 49 721 608-55022

E-Mail: crypto-info(at)iti.kit.edu

Aktuelles

Jörn Müller-Quade wird acatech-Mitglied

Am 1. Dezember 2016 wurde Prof. Jörn Müller-Quade aufgrund seiner Verdienste und Leistungen auf dem Gebiet der theoretischen Informatik und der IT-Sicherheit in die deutsche Akademie der Technikwissenschaften(acatech) aufgenommen. Die acatech ist eine interdisziplinäre, gemeinnützige Organisation, die hauptsächlich in beratender Funktion agiert und das das Gebiet der deutschen Technikwissenschaft auf nationaler und internationaler Ebene vertritt.

Link zur acatech

ERC Consolidator Grant für Prof. Dennis Hofheinz

Prof. Dennis Hofheinz hat für das Projekt „PREP-CRYPTO: Preparing Cryptography for Modern Applications“ den Consolidator Grant des European Research Council (ERC) erhalten. Das Projekt beschäftigt sich neue kryptographische Bausteine für Bereiche wie Big Data und Cloud Computing zu entwickeln und wird in den nächsten fünf Jahren mit rund zwei Millionen Euro gefördert.

Link zur offiziellen Pressemitteilung

Prof. Jörn Müller-Quade und PD Oliver Raabe auf Smart Data Jahreskongress

Am 14. November fand in Berlin der vom Bundesministerium für Wirtschaft und Energie(BMWi) der Jahreskongress Smart Data 2016 statt. Der Kongress stand dieses Jahr unter dem Thema Datenschutz. So hielten Prof. Jörn Müller-Quade und PD Oliver Raabe einen Impulsvortrag zum Thema "Möglichkeiten des technischen Datenschutzes".

Link zur Veranstaltung 

Prof. Jörn Müller-Quade bei CyberRisk-Kongress

"Wie gefährlich sind Cyberattacken?" BadenTV berichtet über den CyberRisk-Kongress, der am 4. Oktober in den Räumen der Firma Vollack stattfand. Dabei ging es um die Gefahren von Cyberattacken sowohl für Privatpersonen als auch für Unternehmen. Unter anderem nahm auch Prof. Jörn Müller-Quade teil und hielt einen Vortrag zum Thema Beweisbare Sicherheit.

Link zum Beitrag von BadenTV.

Link zur Webseite des CyberRisk-Kongress.

Dokumentation zu ZKM-Ausstellung

Die Dokumentation zur ZKM-Ausstellung "Global Control and Censorship" ist nun online.

KASTEL-PI bei Baden-TV

Prof. Jörn Müller-Quade gab Baden-TV ein Interview zum Thema Keyless-Go.

KASTEL beim 8. Tag der IT-Sicherheit

Beim 8. Tag der IT-Sicherheit führten KASTEL-Mitarbeiter das Blurry-Box-Verfahren vor.

Prof. Müller-Quade beim Big Tech Day 9

Beim 9. Big Tech Day nahm Prof. Müller-Quade mit dem Vortrag "No Cat-and-Mouse Game - Models, Assumptions and Evidence in Cryptography and IT Security" teil.

3. Platz bei CTF

Am 26. Mai fand in Amsterdam der HITB CTF statt. Unter 20 teilnehmenden internationalen Teams gelang es dem KIT-Team, den 3. Platz zu belegen und 1000$ Preisgeld zu gewinnen.

Gründungsmitglied von Clusternetzwerk

Das KIT ist mit KASTEL Gründungsmitglied eines europäischen Netzwerks von Sicherheitsclustern. Sechs europäische Cluster aus den Bereichen zivile Sicherheit und IT-Sicherheit bereiten den Boden für eine engere Zusammenarbeit europäischer Unternehmen und Forschungseinrichtungen.

Ausstellung "Global Control and Censorship" im ZKM verlängert

Die Ausstellung "Global Control and Censorship", zu welcher das KIT mehrere Exponate beigesteuert hat, wird nun bis zum 7. August 2016 verlängert.

Uni-Chat mit der FAZ

Die Online-Sprechstunde der FAZ fand am 3.5. statt und gab Abiturienten die Gelegenheit, ihre Fragen zum Informatik- und Mathematikstudium an Prof. Müller-Quade und Prof. Beutelsbacher zu stellen.

Prof. Jörn Müller-Quade bei "Deutschlands größter Sprechstunde"

Am 3. Mai findet, organisiert von der FAZ, "Deutschlands größte Sprechstunde" zum Thema Mathematik und Informatik statt, an welcher Prof. Müller-Quade teilnimmt.

Ministerin Bauer weiht Profilregion Mobilität ein

Ministerin Theresia Bauer und Staatssekretär Peter Hofelich sprachen bei der Eröffnung der Profilregion Mobilitätssysteme. KASTEL ist an der zweijährigen Pilotphase beteiligt.

Bundeskanzlerin besucht KASTEL auf der CeBIT

Auf der CeBit 2016 besuchte Bundeskanzlerin Angela Merkel den Gemeinschaftsstand KIT und FZI, auf dem KASTEL das mit dem deutschen IT-Sicherheitspreis ausgezeichnete Blurry-Box-Verfahren vorstellte.

SecUnity-Kick-Off

Am 1.1.16 startete das Verbundprojekt secUnity (Supporting the security community).

In diesem BMBF Projekt wollen 7 Arbeitsgruppen von 5 Standorten die europäische IT-Sicherheitsforschung in Deutschland stärken. Am 29.1.16 fand am KIT das Kick-Off-Treffen des Projekts statt.

Prof. Jörn Müller-Quade als Gastredner bei 20-jährigem Helmholtz-Jubiläumsempfang

Prof. Jörn Müller-Quade hielt am 1.12.15 einen Gastvortrag zum Anlass des 20-jährigen Jubiläums der Helmholtz-Gemeinschaft.

Best-Paper-Award auf der ProvSec'15

Prof. Jörn-Müller Quade und Mitarbeiter erhielten für ihr Papier "From Stateful Hardware to Resettable Hardware Using Symmetric Assumptions" den begehrten Best-Paper-Award der diesjährigen

ProvSec-Konferenz, ein Forum für Arbeiten im Bereich "Beweisbare Sicherheit".

Prof. Jörn Müller-Quade bei Podiumsdiskussion

Am 10.12.15 nahm Prof. Jörn Müller-Quade bei einer öffentlichen Podiumsdiskussion zum Thema "IT-Sicherheit und Datenschutz" mit weiteren hochrangigen Gästen wie Bundesjustizministering a.D. Frau Leutheusser-Schnarrenberger teil.

Großer Erfolg für Prof. Dennis Hofheinz auf der TCC 2016

Prof. Dennis Hofheinz ist mit seinen Mitarbeitern auf der Theory of Cryptography Conference (TCC) 2016 gleich mit vier Papieren vertreten. Die TCC ist eine von der International Association for Cryptologic Research (IACR) ausgerichtete Konferenz im Bereich Kryptographie und eines der wichtigsten Foren für theoretische Resultate in diesem Bereich.

Prof. Jörn Müller-Quade beim ZDF-Morgenmagazin

Prof. Jörn Müller-Quade gab beim ZDF-Morgenmagazin vom 26.11.15 Auskunft

über die Kommunikationsmöglichkeiten des Islamischen Staates.

"Das Digitale Ich braucht Verschlüsselung"

Prof. Jörn Müller-Quade hielt am 15.10.15 einen eingeladenen Vortrag auf der Konferenz "Das digitale Ich",

die von der Bundesdruckerei und der Frankfurter Allgemeinen Zeitung in Berlin veranstaltet wurde. Heise berichtet in seinem Artikel

"Das Digitale Ich braucht Verschlüsselung" über die Highlights der Konferenz und "den kleinen Professor mit der Fliege, der die Konferenz rockte".

Prof. Jörn Müller-Quade im FAZ-Interview

Im FAZ-Uni-Ratgeber werben Deutschlands beste Professoren für ihr Fach. Hier beantwortet Prof. Jörn Müller-Quade

in einem Video-Interview fragen zur Informatik und IT-Sicherheit.

Interview mit Prof. Jörn Müller-Quade auf MDR-Online

Prof. Jörn Müller-Quade stand am 20. Juni 2015 Deborah Manavi vom MDR SACHSEN zum Thema "Welche Auswirkungen haben Kryptographie, Internetspionage und die Nutzung von Social Media für unseren Alltag?" Rede und Antwort. Das Interview kann auf den WDR-Webseiten nachgelesen werden.

20 Jahre Helmholtz-Gemeinschaft

Am 24. und 25. Juni 2015 fand der Festakt "20 Jahre Helmholtz-Gemeinschaft" im Beisein von Angela Merkel sowie ein Symposium mit 20 Vorträgen statt. Prof. Jörn Müller-Quade war dabei mit einem Vortrag zum Thema "Kryptographie jenseits der Verschlüsselung" vertreten.

Vorlesung: Algorithmen I

Dozent

Prof. Jörn Müller-Quade

Übungsleiter

Björn Kaidel, Sascha Witt, Sebastian Schlag

Termin und Ort

  • Vorlesung: montags, 15.45 - 17.15, Audimax und mittwochs, 14.00 - 14.45, Audimax
  • Übung: mittwochs, 14.45 - 15.30, Audimax

Am Mittwoch, den 28.06.2017, finden Vorlesung und Übung ausnahmsweise im Hörsaal am Fasanengarten statt.

Klausur

Die Hauptklausur hat am Montag, den 4. September 2017, 11.00 - 13.00 Uhr stattgefunden.

Die vorläufigen Klausurergebnisse stehen nun fest und können hier abgerufen werden: Ergebnisse Klausur 04.09.2017

Die Klausureinsicht fand am 29.09.2017 statt.

Nachklausur

Die Nachklausur wird am 11.04.2018 um 8:00 Uhr stattfinden.

Ablauf

Hier werden die Folien zu den Vorlesungen und Übungen veröffentlicht.

 

DatumInhalt
24.04.2017

Vorstellung, Motivation, Langzahlmultiplikation, Karatsuba-Ofman-Multiplikation

Folien VL01 Videoaufzeichnung VL01

Folien Organisatorisches

26.04.2017

Karatsuba-Ofman-Multiplikation, Maschinenmodell, Pseudocode, Master-Theorem

Folien VL02 Videoaufzeichnung VL02

03.05.2017

Übung: O-Kalkül, Schleifeninvarianten, Master-Theorem, Rekurrenzen

Folien Übung 01 Ergänzung Übung 01

Videoaufzeichnung Übung 01

Hinweis: Beim Beispiel zu Karatsuba-Ofman hatte sich ein Zahlendreher eingeschliechen, dieser wurde korrigiert.

08.05.2017

Verkettete Listen, Felder (Arrays), unbeschränkte Felder, armortisierte Analyse

Folien Vorlesung 03 Videoaufzeichnung VL03

10.05.2017

Vorlesung: Stapel, Schlangen, Movitation Hashing

Übung: Listen, Amortisierte Analyse

Folien Vorlesung 04 Folien Übung 02

Videoaufzeichnung VL04 & ÜB02

15.05.2017

Hashtabellen (Definition, Hashing mit verketteten Listen, Vorbereitung zur Analyse), Analyse von Hashtabellen mit verketteten Listen, Hashing mit linearer Suche

Folien Vorlesung 05

Videoaufzeichnung VL05

17.05.2017

Vorlesung: Mehr Hashing, Sortieren (Motivation)

Übung: Hashtabellen & Anwendungsbeispiele (Duplikaterkennung, Bloom Filter)

Folien Vorlesung 06 Folien Übung 03

Videoaufzeichnung VL06 & ÜB03

22.05.2017

Sortieren, InsertionSort (Sortieren durch Einfügen), MergeSort (Sortieren durch Mischen), Untere Schranke für vergleichbasiertes Sortieren, QuickSort

Folien Vorlesung 07

Videoaufzeichnung VL07

24.05.2017

Vorlesung: randomisierter QuickSort, Implementierung von QuickSort

Übung: InsertionSort, Adaptives Sortieren, Analyse von InsertionSort, MergeSort, SplitSort

Folien Vorlesung 08 Folien Übung 04

Videoaufzeichnung VL08 & ÜB04

29.05.2017

Mehr zu QuickSort, Ganzzahliges Sortieren, Heaps

Folien Vorlesung 09

Videoaufzeichnung VL09

31.05.2017

Vorlesung: Heaps, HeapSort

Übung: "Ganzzahliges" Sortieren, schnelle Priority Queues

Folien Vorlesung 10 Folien Übung 05

Videoaufzeichnung VL10 & ÜB05

07.06.2017

Vorlesung: Adressierbare Prioritätslisten, Sortierte Folgen

Übung: Einführung/Wiederholung Graphen

Folien Vorlesung 11 Folien Übung 06

Videoaufzeichnung VL11 & ÜB06

12.06.2017

Sortierte Folgen, (a,b)-Bäume

Folien Vorlesung 12

Videoaufzeichnung VL12

(aufgrund technischer Probleme wurden die Folien während der Vorlesung nicht aufgezeichnet. Wir haben aber im Nachhinein versucht die Folien möglichst genau an die Audiospur anzupassen)

14.06.2017

Graphen, Breitensuche

Folien Vorlesung 13

Videoaufzeichnung VL13

19.06.2017

Tiefensuche, Dijkstra (Einstieg)

Folien Vorlesung 14

Videoaufzeichnung VL14

21.06.2017Probeklausur (Klausur, Klausur mit Lösungsvorschlag)
26.06.2017

Dijkstra, Bellman-Ford, kürzeste Wege

Folien Vorlesung 15

Videoaufzeichnung VL15

28.06.2017

Vorlesung: Exkurs Routenplanung

Übung: Breiten- & Tiefensuche, Dijkstra

Folien Vorlesung 16 Folien Übung 07

Videoaufzeichnung VL16 & ÜB07

03.07.2017

Minimale Spannbäume, Jarník-Prim, Kruskal

Folien Vorlesung 17

Videoaufzeichnung VL17

05.07.2017

Vorlesung: Optimierungsprobleme, Rucksackproblem, Lineare Programmierung

Übung: Bellman-Ford, minimale Spannbäume, Steinerbäume

Folien Vorlesung 18 Folien Übung 08

Videoaufzeichnung VL18 & ÜB08

10.07.2017

Anwendungen dynamischer Programmierung, Branch-and-Bound, weitere Lösungsmöglichkeiten für Optimierungsprobleme

Folien Vorlesung 19

Videoaufzeichnung VL19

12.07.2017

Schwierige Probleme, Traveling Salesman Problem, Vertex Cover

Übung 09

  • Update: Beim Graph für das Vertex Cover Beispiel hat eine Kante gefehlt, damit das Tabu-Suche-Gegenbeispiel funktioniert. Diese Kante wurde ergänzt.
Videoaufzeichnung Übung 09
17.07.2017

Überblicksvorlesung

Folien Vorlesung 20

Videoaufzeichnung VL20

19.07.2017Fragestunde
24.07.2017

Schnuppervorlesung Sicherheit

Videoaufzeichnungs Schnuppervorlesung

26.07.2017Entfällt

 

 

Übungsblätter

 

ÜbungsblattMaterialien
Blatt 01
Blatt 02
  • Übungsblatt 02
    • Hinweis: Aufgrund mehrerer Nachfragen haben wir uns entschieden Aufgabe 3 etwas zu vereinfachen. Sie können in der Aufgabe nun von n=2^k ausgehen. In Aufgabe 3 dürfen start und end natürlich auch den Wert 0 annehmen.
  • Lösung Übungsblatt 02
Blatt 03
Blatt 04
Blatt 05
Blatt 06
Blatt 07
Blatt 08
Blatt 09
Blatt 10
  • Übungsblatt 10
    • Update: Aufgabe 3b) war unpräzise formuliert. Die Aussage ist nur beweisbar, wenn der Graph mehr als einen Knoten enthält. Die Aufgabe wurde entsprechend umformuliert.
  • Lösung Übungsblatt 10
Blatt 11
  • Übungsblatt 11
    • Update: Es hatte sich ein Fehler in Aufgabe 3b) eingeschliechen. Der Algorithmus läuft nur, bis der Graph keine Kanten mehr hat. Vorher stand fälschlicherweise dort, dass der Algorithmus so lange laufen würde, bis der Graph leer ist.
  • Lösung Übungsblatt 11

 

 

Tutorien

Die Einteilung in die Tutorien ist über WebInscribe abrufbar. 

ILIAS-Forum

Es gibt ein ILIAS-Forum zur Vorlesung. Bitte postet dort Fragen, Anregungen, etc. zur Vorlesung und Übung.

Maillingliste

Für die Veranstaltung gibt es eine Mailingliste, die dazu genutzt werden soll, direkt und zeitnah Informationen von Seiten der Dozenten an die Studierenden schicken zu können (beispielsweise Infos zur Klausur, Terminen, Übungsblättern...). Die Anmeldung an die Mailingliste ist hier möglich:

https://lists.ira.uni-karlsruhe.de/mailman/listinfo/algorithmeni

Die Mailingliste ist nicht zur Diskussion konzipiert, verwenden Sie dazu besser das oben genannte ILIAS-Forum.

 

Lehrinhalt

Der Inhalt der Vorlesung orientiert sich am Buch "Algorithms and Data Structures - The Basic Toolbox" von Kurt Mehlhorn und Peter Sanders.

Der Studierende

  • kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
  • kann mit diesem Verständnis auch neue algorithmische Fragestellungen bearbeiten,
  • wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
  • wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.