Programm heute Algorithmen und Datenstrukturen (f¨ur ET/IT) Sommersemester 2015 1 Organisation Dr. Tobias Lasser 2 Einf¨ uhrung Ziele und Inhalt der Vorlesung Anwendungen von Algorithmen und Datenstrukturen Einf¨ uhrung Algorithmen Einf¨ uhrung Datenstrukturen Einordnung in Computer-Schema Computer Aided Medical Procedures Technische Universit¨ at M¨ unchen 2 Personen Termine • Vorlesung: Dr. Tobias Lasser • Akademischer Rat am Lehrstuhl Prof. Nassir Navab, I16 Computer Aided Medical Procedures Vorlesung • Zentral¨ ubung: • Matthias Wieczorek ¨ Ubung Montag, 8:00 - 9:30, Raum 1200 Donnerstag 8:00 - 9:30, Raum 1200 • Wiss. Mitarbeiter I16 Zentral¨ ubung: Mittwoch, 9:45 - 11:15, Raum 1200 • Tutoren: • Markus Steppberger • Benedict Simlinger Tutorfragestunden: Dienstag nachmittags (Zeit und Raum: tba) Freitag vormittags (Zeit und Raum: tba) 3 4 Informationen online Kontakt und Feedback F¨ ur Fragen: • Pers¨ onlich Vorlesungs-Website ¨ • z.B. vor oder nach der Vorlesung/Ubung • in Tutorfragestunden http://campar.in.tum.de/Chair/TeachingSs15AuD • Email • [email protected] • Diskussions-Forum • Moodle: https: //www.moodle.tum.de/mod/forum/view.php?id=292073 • Sprechstunde • nach Vereinbarung • aktuelle Nachrichten • Vorlesungs-Folien ¨ • Ubungsbl¨ atter • zus¨ atzliche Materialien Moodle https://www.moodle.tum.de/course/view.php?id=17994 Feedback • Diskussions-Forum ¨ Feedback zur Vorlesung/Ubung ist jederzeit willkommen! 6 5 ¨ Ablauf: Ubung Ablauf: Vorlesung • Erste Zentral¨ ubung: Mittwoch, 15.04.2015 ¨ • Jede Woche ein Ubungsblatt • 3-5 Aufgaben • zur Anwendung und Vertiefung der Vorlesung • In der Zentral¨ ubung • Besprechung der Aufgaben • Beantwortung von Fragen • In den Tutorfragestunden • Individuelle Beantwortung von Fragen • Folienvortrag • mit gelegentlichen Annotationen / Tafelanschrieb • kein Skript! • Folien vor Vorlesung als PDF zum Download • http://campar.in.tum.de/Chair/TeachingSs15AuD • Eigene Notizen sind hilfreich! ¨ • Eigene Bearbeitung der Ubungsbl¨ atter dringend empfohlen! • z.B. auch in kleinen Gruppen 7 8 Leistungsnachweis Literatur • Klausur am 29.07.2015 • Schriftliche Pr¨ ufung • Dauer: 120 Minuten • erlaubte Hilfsmittel: handbeschriebenes DIN A4 Blatt Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einf¨ uhrung Oldenbourg, 3. Auflage 2010 • Vorbereitung durch aktive Teilnahme und Bearbeitung des ¨ Ubungs-Programms Verf¨ ugbar in der Lehrbuchsammlung • Zwei Probeklausuren Mitte und Ende des Semesters in Zentral¨ ubung 10 9 Erg¨anzende Literatur Fragen? • Sedgewick: Algorithmen, Addison-Wesley, 2001 • Ottmann, Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2002 • Knuth: The Art of Computer Programming Vol. 1-4A, Addison-Wesley, 1997/98, 2011 11 12 Programm heute Ziele der Vorlesung Wissen: 1 Organisation • Algorithmische Prinzipien verstehen und anwenden • Grundlegende Algorithmen kennen lernen • Grundlegende Datenstrukturen kennen lernen 2 Einf¨ uhrung • Bewertung von Effizienz und Korrektheit lernen Ziele und Inhalt der Vorlesung Anwendungen von Algorithmen und Datenstrukturen Einf¨ uhrung Algorithmen Einf¨ uhrung Datenstrukturen Einordnung in Computer-Schema Methodenkompetenz: • f¨ ur Entwurf von effizienten und korrekten Algorithmen • zur Analyse von Algorithmen 14 13 ¨ Ubersicht der Inhalte Grundlagen: http://xkcd.com/835/ 15 1 Einf¨ uhrung in Algorithmen und Datenstrukturen Motivation, Definitionen, Einordnung 2 Grundlagen von Algorithmen Darstellung, elementare Bausteine, Pseudocode 3 Grundlagen von Datenstrukturen Primitive Datentypen, Felder, abstrakte Datentypen 4 Grundlagen der Korrektheit von Algorithmen Verifikation, Testen, Sortieren 5 Grundlagen der Effizienz von Algorithmen Komplexit¨atsanalyse, Sortieren 6 Grundlagen des Algorithmen-Entwurfs Entwurfs-Prinzipien 16 ¨ Ubersicht der Inhalte ¨ Ubersicht der Inhalte Fortgeschrittene Algorithmen und Datenstrukturen: 7 Fortgeschrittene Datenstrukturen B¨aume, Graphen, Priority-Queue 8 Such-Algorithmen Elementare Suchmethoden, Suchb¨aume 11 Datenkompression Huffmann-Codes, JPEG 9 Graph-Algorithmen Elementare Algorithmen, k¨ urzeste Pfade, Spannbaum 12 Kryptographie symmetrische und asymmetrische Verschl¨ usselungsverfahren 10 Numerische Algorithmen Matrizen-Operationen, Fast Fourier Transform Ausgew¨ahlte Themen (je nach verf¨ ugbarer Zeit, nicht Klausur-relevant!): 17 Wo kommen Algorithmen und Datenstrukturen vor? 18 Wo kommen Algorithmen und Datenstrukturen vor? 22 23 Was ist ein Algorithmus? Was ist ein Algorithmus? H. Rogers: Theory of Recursive Functions and Effective Computability Duden online: Rechenvorgang nach einem bestimmten (sich wiederholenden) ” Schema“ Ein Algorithmus ist eine ” • deterministische Handlungsvorschrift, • benannt nach dem Mathematiker Al’Khwarizmi (ca. 780 – • die auf eine bestimmte Klasse von Eingaben angewendet 850) aus Persien, t¨atig im Haus der Weisheit“ in Baghdad ” • Beispiele f¨ ur Algorithmen bereits in der Antike, etwa der Euklidsche Algorithmus zur Berechnung des ggT: werden kann, • und f¨ ur jede dieser Eingaben eine korrespondierende Ausgabe liefert.“ Wenn CD aber AB nicht misst, und man nimmt bei AB, CD ” abwechselnd immer das kleinere vom gr¨oßeren weg, dann muss (schließlich) eine Zahl u ¨brig bleiben, die die vorangehende misst.“ Im weiteren Verlauf des Buches wird mathematische Theorie zur Berechenbarkeit entwickelt aus Euklid: Die Elemente, Buch VII (Clemens Thaer) −→ theoretische Informatik 24 Was ist ein Algorithmus? 25 Was ist ein Algorithmus? Mathematische Definition Algorithmus M. Broy: Informatik: Eine grundlegende Einf¨uhrung Eine Berechnungsvorschrift zur L¨ osung eines Problems heißt Algorithmus genau dann, wenn Ein Algorithmus ist ein Verfahren ” • mit einer pr¨ azisen (d.h. in einer genau festgelegten Sprache abgefassten), • eine zu dieser Berechnungsvorschrift ¨ aquivalente Turingmaschine exisitiert, • endlichen Beschreibung, • unter Verwendung • effektiver (d.h. tats¨ achlich ausf¨ uhrbarer), • elementarer (Verarbeitungs-) Schritte.“ • die f¨ ur jede Eingabe, die eine L¨ osung besitzt, terminiert. Alan Turing (1936): Turingmaschine als mathematisches Modell eines Computers Diese Beschreibung ist f¨ ur unsere Zwecke ausreichend. −→ theoretische Informatik 26 27 Beispiel Algorithmus Beispiel Kochrezept R¨ uhrei Euklidscher Algorithmus Input: Eier, Salz, Pfeffer Output: R¨ uhrei Input: nat¨ urliche Zahlen a, b Output: gr¨oßter gemeinsamer Teiler von a, b 1 Setze m := a und n := b 1 Butter in Pfanne zerlaufen lassen 2 Falls m < n vertausche m und n 2 Eier in Pfanne hauen 3 Berechne r := m − n 3 Prise Salz und Pfeffer hinzuf¨ ugen und gut durchr¨ uhren 4 Setze m := n und n := r 4 In Pfanne brutzeln lassen und umr¨ uhren bis die Eier durch sind 5 Falls r > 0, gehe zu Schritt 2 6 Der Output ist m −→ dies ist kein Algorithmus! 28 Eigenschaften von Algorithmen 29 Beispiel Kochrezept • Input (Eingabe): definiert eine Instanz des Algorithmus R¨ uhrei • Output (Ausgabe): das Ergebnis Input: Eier, Salz, Pfeffer Output: R¨ uhrei Input −→ Algorithmus −→ Output • Determiniertheit: • Schrittfolge ist eindeutig festgelegt • vorgegebener Input liefert immer eindeutigen Output • Endlichkeit: der Algorithmus terminiert, d.h. er bricht bei 1 Butter in Pfanne zerlaufen lassen 2 Eier in Pfanne hauen 3 Prise Salz und Pfeffer hinzuf¨ ugen und gut durchr¨ uhren 4 In Pfanne brutzeln lassen und umr¨ uhren bis die Eier durch sind jeder Eingabe nach endlich vielen Schritten ab • Korrektheit: der Algorithmus produziert den richtigen Output 30 31 Beispiel Algorithmus Analyse von Algorithmen Euklidscher Algorithmus Input: nat¨ urliche Zahlen a, b Output: gr¨oßter gemeinsamer Teiler von a, b Entscheidende Fragestellungen: • Darstellung −→ Kapitel 2 1 Setze m := a und n := b • Robustheit und Korrektheit −→ Kapitel 4 2 Falls m < n vertausche m und n • Effizienz und Komplexit¨ at −→ Kapitel 5 3 Berechne r := m − n • Entwurfstechniken −→ Kapitel 6 4 Setze m := n und n := r 5 Falls r > 0, gehe zu Schritt 2 6 Der Output ist m 32 Definition Datenstruktur 33 Beispiel Datenstruktur Stapel (oder Englisch: Stack), z.B. Pizza-Stapel Definition Datenstruktur (nach Prof. Eckert) neu e Eine Datenstruktur ist eine Piz Piz • logische Anordnung von Datenobjekten, 3 za # 2 Piz • die Informationen repr¨ asentieren, Piz za # • den Zugriff auf die repr¨ asentierte Information u ¨ber za za # 1 Operationen auf Daten erm¨ oglichen und • die Information verwalten. Operationen: • Element auf Stapel legen – push • Element von Stapel nehmen – pop Operationen jeweils nur auf oberstem Element! 34 35 Algorithmen und Algorithmus Datenstrukturen Hochsprache (z.B. C, C++) Betriebssystem • Felder, Listen, Stack, Queue −→ Kapitel 3 Assembler • B¨ aume, Graphen −→ Kapitel 7, 8, 9 Computertechnik Maschinensprache Mikroarchitektur Digitale Logik Digitaltechnik Transistoren, Verdrahtung Schaltungstechnik Masken-Layout, Halbleiter Software Wie funktioniert ein Computer? Hardware Weitere Beispiele von Datenstrukturen Schema nach Prof. Diepold: Grundlagen der Informatik. 36 Beispiel-Problem Navigationssystem Auto: Algorithmen und Algorithmus Datenstrukturen Hochsprache (z.B. C) Finde k¨ urzesten Weg von Berlin nach M¨ unchen. Berlin −→ −→ Betriebssystem M¨ unchen Assembler • Datenstruktur: gewichteter Graph (→ Kapitel 7) Maschinensprache • Algorithmus: k¨ urzester Pfad (→ Kapitel 9) Mikroarchitektur • Algorithmus-Beschreibung: Programmiersprache (z.B. C) Digitale Logik ¨ • Ubersetzung in Maschinensprache: Compiler (z.B. GCC) Transistoren, Verdrahtung • Aufruf des Programms: Betriebssystem (z.B. Linux) Masken-Layout, Halbleiter • Ausf¨ uhrung des Programms: Computer (z.B. Laptop) Software Einordnung Algorithmen und Datenstrukturen Hardware Einordnung Algorithmen und Datenstrukturen 37 Schema nach Prof. Diepold: Grundlagen der Informatik. 38 39 Zusammenfassung 1 Organisation 2 Einf¨ uhrung Ziele und Inhalt der Vorlesung Anwendungen von Algorithmen und Datenstrukturen Einf¨ uhrung Algorithmen Einf¨ uhrung Datenstrukturen Einordnung in Computer-Schema 40
© Copyright 2024 ExpyDoc
