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

Molekülabfolge als Passwort

Jeder hat sie in mehreren Ausführungen und in unterschiedlichen Sicherheitsstufen: Passwörter. Sie gelten als Schutz wichtiger Daten und sind aus unserem Leben nicht wegzudenken. Wurde das Passwort jedoch gestohlen, erraten oder errechnet liegen diese vermeintlich geschützten Daten offen. KIT- und ITI-Mitarbeiter  arbeiten derzeit an einer neuen Idee: der Verschlüsselung durch organische Moleküle. In der Abfolge der einzelnen Bausteine soll das Passwort als Binärcode verschlüsselt werden.

21. E-Voting Kolloquium in Karlsruhe

Am 9.-10.April 2018 findet am Karlsruher Institut für Technologie das 21. E-Voting Kolloquium statt. Die seit 2006 europaweit stattfindende Tagung thematisiert verschiedene Aspekte des E-Voting wie rechtliche Hürden, Identitätsmanagement, technische Aspekte und die Verifizierung der Wahl. Die Veranstaltung wird von Prof. Dr. Bernhard Beckert, Prof. Dr. Jörn Müller-Quade und Prof. Dr. Melanie Volkamer sowie Dr. Oskana Kulyk mitorganisiert.

Die Arbeit eines Kryptologen

Am 02.Februar wurde ITI-Mitarbeiter Andy Rupp in die Podcast-Reihe „Resonator“  ,einen Audio-Podcast der Helmholtz-Gemeinschaft Deutscher Forschungszentren aufgenommen. Die Podcast-Reihe befasst sich mit Forscherinnen, Forschern und deren Themengebieten. Andy Rupp gibt Aufschluss über die Arbeit eines Theoretikers an Systemen wie Bonuskarten oder Mautsystemen, die die Privatsphäre der User schützen können. Zum Podcast .

Lernende Systeme - Die Plattform für künstliche Intelligenz

KIT-Präsident Holger Hanselka und ITI-Professor Jörn Müller-Quade sind an der BMBF-initiierten Plattform Lernende System beteiligt. Die Plattform soll dazu beitragen, künstliche Intelligenz im Sinne von Mensch und Gesellschaft zu gestalten und so die Lebensqualität zu verbessern. Während der KIT Präsident im Lenkungskreis wirkt, ist Herr Müller-Quade Leiter der Arbeitsgruppe 3, die Fragen zu den Gebieten Sicherheit, Zuverlässigkeit und dem Umgang mit Privatheit thematisiert. Weitere Infos zur Plattform  und zur Arbeitsgruppe .

Datenschleuder Smartphone

Das Smartphone sammelt Daten- immer und überall. Doch was genau das Gerät alles aufzeichnet und wer alles an diese Daten kommen kann ist den meisten nicht bewusst. In der Landesschau Baden-Württemberg erschien am 29.01.2018 ein Beitrag zu diesem Thema , der auch ITI-Mitarbeiter Professor Jörn Müller-Quade als Experten zu diesem Thema befragt.

Link zum Beitrag

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 fand am Montag, den 4. September 2017, 11.00 - 13.00 Uhr statt.

Die Klausureinsicht fand am 29.09.2017 statt.

Nachklausur

Die Nachklausur hat am 11.04.2018 stattgefunden.

Die vorläufigen Klausurergebnisse sind online. Bitte melden Sie sich schnellstmöglich bei Björn Kaidel (bjoern.kaidel(at)kit.edu), falls Sie einen Termin für eine mündliche Nachprüfung benötigen.

Die Klausureinsicht findet am 03.05.2018 zwischen 16 und 18 Uhr im Raum 252, Geb. 50.34 ("Info-Bau") statt.

 

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.