Suchergebnis: Katalogdaten im Herbstsemester 2016
Informatik Lehrdiplom Weitere Informationen: Link | ||||||
Informatik als 1. Fach | ||||||
Auflagenfächer (für Studierende mit ETH-Master in Phys/MATH/RW) | ||||||
Teil 1 | ||||||
Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |
---|---|---|---|---|---|---|
252-0057-00L | Theoretische Informatik | O | 8 KP | 4V + 2U + 1A | J. Hromkovic | |
Kurzbeschreibung | Konzepte zur Beantwortung grundlegender Fragen wie: a) Was ist völlig automatisiert machbar (algorithmisch lösbar) b) Wie kann man die Schwierigkeit von Aufgaben (Problemen) messen? c) Was ist Zufall und wie kann er nützlich sein? d) Was ist Nichtdeterminisus und welche Rolle spielt er in der Informatik? e) Wie kann man unendliche Objekte durch Automaten und Grammatiken endlich darstellen? | |||||
Lernziel | Vermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung | |||||
Inhalt | Die Veranstaltung ist eine Einführung in die Theoretische Informatik, die die grundlegenden Konzepte und Methoden der Informatik in ihrem geschichtlichen Zusammenhang vorstellt. Wir präsentieren Informatik als eine interdisziplinäre Wissenschaft, die auf einer Seite die Grenzen zwischen Möglichem und Unmöglichem und die quantitativen Gesetze der Informationsverarbeitung erforscht und auf der anderen Seite Systeme entwirft, analysiert, verifiziert und implementiert. Die Hauptthemen der Vorlesung sind: - Alphabete, Wörter, Sprachen, Messung der Informationsgehalte von Wörtern, Darstellung von algorithmischen Aufgaben - endliche Automaten, reguläre und kontextfreie Grammatiken - Turingmaschinen und Berechenbarkeit - Komplexitätstheorie und NP-Vollständigkeit - Algorithmenentwurf für schwere Probleme | |||||
Skript | Die Vorlesung ist detailliert durch das Lehrbuch "Theoretische Informatik" bedeckt. | |||||
Literatur | Basisliteratur: 1. J. Hromkovic: Theoretische Informatik. 5. Auflage, Springer Vieweg 2014. 2. J. Hromkovic: Theoretical Computer Science. Springer 2004. Weiterführende Literatur: 3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997 4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson 2002. 5. I. Wegener: Theoretische Informatik. Teubner Weitere Übungen und Beispiele: 6. A. Asteroth, Ch. Baier: Theoretische Informatik | |||||
Voraussetzungen / Besonderes | Während des Semesters werden zwei freiwillige Probeklausuren gestellt. | |||||
252-0061-00L | Systems Programming and Computer Architecture | O | 8 KP | 4V + 2U + 1A | T. Roscoe | |
Kurzbeschreibung | Introduction to computer architecture and system programming: Instruction sets, storage hiearchies, runtime structures with an emphasis on computers as engines for the execution of compiled programs. Interaction between system software and the hardware. Problems that arise from the final respresentation, performance measurement and tuning, and program portability issues are covered. | |||||
Lernziel | The objective is to allow students to understand all aspects of the execution of compiled (C) programs on modern architectures -- the instruction set, the storage resources (registers, stack, memory), input/output, the impact of compiler decisions, and the interaction between the operating system and hardware. Two main themes are correctness issues (esp. those that arise from the finite representation of data) and performance issues (incl. measurement and tuning issues). The interface to the operating system is discussed to prepare for subsequent classes on more advanced systems topics. The two key goals are: 1) To equip students with a thorough understanding of how to write correct programs that run fast on modern computer, and 2) How to write correct and efficient low-level systems code. This course does not cover how to design or build a processor or computer. | |||||
Inhalt | This course provides an overview of "computers" as a platform for the execution of (compiled) computer programs. This course provides a programmer's view of how computer systems execute programs, store information, and communicate. The course introduces the major computer architecture structures that have direct influence on the execution of programs (processors with registers, caches, other levels of the memory hierarchy, supervisor/kernel mode, and I/O structures) and covers implementation and representation issues only to the extend that they are necessary to understand the structure and operation of a computer system. The course attempts to expose students to the practical issues that affect performance, portability, security, robustness, and extensibility. This course provides a foundation for subsequent courses on operating systems, networks, compilers and many other courses that require an understanding of the system-level issues. Topics covered include: machine-level code and its generation by optimizing compilers, address translation, input and output, trap/event handlers, performance evaluation and optimization (with a focus on the practical aspects of data collection and analysis). | |||||
Literatur | The course is based in part on "Computer Systems: A Programmer's Perspective" (2nd Edition) by R. Bryant and D. O'Hallaron, with some additional material. | |||||
Voraussetzungen / Besonderes | 252-0024-00L Parallel Programming, 252-0014-00L Digital Circuits | |||||
252-0026-00L | Algorithmen und Datenstrukturen | O | 7 KP | 3V + 2U + 1A | P. Widmayer, M. Püschel | |
Kurzbeschreibung | Es werden grundlegende Entwurfsmuster für Algorithmen sowie klassische algorithmische Probleme und Datenstrukturen behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. In die Graphentheorie wird kurz eingeführt. | |||||
Lernziel | Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. | |||||
Inhalt | Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt. | |||||
Literatur | Th. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 |
- Seite 1 von 1