Das Herbstsemester 2020 findet in einer gemischten Form aus Online- und Präsenzunterricht statt.
Bitte lesen Sie die publizierten Informationen zu den einzelnen Lehrveranstaltungen genau.

Suchergebnis: Katalogdaten im Frühjahrssemester 2015

Informatik Master Information
Vertiefungsübergreifende Fächer
NummerTitelTypECTSUmfangDozierende
263-0008-00LComputational Intelligence Lab
Office hour always on Mondays from 11-12 in room CAB H53
O6 KP2V + 2U + 1AT. Hofmann
KurzbeschreibungThis laboratory course teaches fundamental concepts in computational science and machine learning based on matrix factorization. This method provides a powerful framework of numerical linear algebra that encompasses many important techniques, such as dimension reduction, clustering, combinatorial optimization and sparse coding.
LernzielStudents acquire the fundamental theoretical concepts related to a class of problems that can be solved by matrix factorization. Furthermore, they successfully develop solutions to application problems by following the paradigm of modeling - algorithm development - implementation - experimental validation.

This lab course has a strong focus on practical assignments. Students work in groups of two to three people, to develop solutions to three application problems:
1. Compression: Exploiting image statistics to compress an image with minimal perceptual loss.
2. Collaborative filtering: predicting a user interest, based on his own and other peoples ratings. The "Netflix prize" is one such example.
3. Inpainting: Filling in lost parts of an image based on its surroundings.

For each of these problems, students submit their solutions to an online evaluation and ranking system, and get feedback in terms of numerical accuracy and computational speed. In the final part of the course, students combine and extend one of their previous promising solutions, and write up their findings in an extended abstract in the style of a conference paper.
Vertiefungsfächer
Vertiefung in Computational Science
Kernfächer der Vertiefung in Computational Science
NummerTitelTypECTSUmfangDozierende
263-2300-00LHow To Write Fast Numerical Code Information
Prerequisite: Master student, solid C programming skills.
W6 KP3V + 2UM. Püschel
KurzbeschreibungThis course introduces the student to the foundations and state-of-the-art techniques in developing high performance software for numerical functionality such as linear algebra and others. The focus is on optimizing for the memory hierarchy and for special instruction sets. Finally, the course will introduce the recent field of automatic performance tuning.
LernzielSoftware performance (i.e., runtime) arises through the interaction of algorithm, its implementation, and the microarchitecture the program is run on. The first goal of the course is to provide the student with an understanding of this interaction, and hence software performance, focusing on numerical or mathematical functionality. The second goal is to teach a general systematic strategy how to use this knowledge to write fast software for numerical problems. This strategy will be trained in a few homeworks and semester-long group projects.
InhaltThe fast evolution and increasing complexity of computing platforms pose a major challenge for developers of high performance software for engineering, science, and consumer applications: it becomes increasingly harder to harness the available computing power. Straightforward implementations may lose as much as one or two orders of magnitude in performance. On the other hand, creating optimal implementations requires the developer to have an understanding of algorithms, capabilities and limitations of compilers, and the target platform's architecture and microarchitecture.

This interdisciplinary course introduces the student to the foundations and state-of-the-art techniques in high performance software development using important functionality such as linear algebra functionality, transforms, filters, and others as examples. The course will explain how to optimize for the memory hierarchy, take advantage of special instruction sets, and, if time permits, how to write multithreaded code for multicore platforms. Much of the material is based on state-of-the-art research.

Further, a general strategy for performance analysis and optimization is introduced that the students will apply in group projects that accompany the course. Finally, the course will introduce the students to the recent field of automatic performance tuning.
Wahlfächer der Vertiefung in Computational Science
NummerTitelTypECTSUmfangDozierende
252-0526-00LStatistical Learning Theory Information W4 KP2V + 1UJ. M. Buhmann
KurzbeschreibungThe course covers advanced methods of statistical learning :
PAC learning and statistical learning theory;variational methods and optimization, e.g., maximum entropy techniques, information bottleneck, deterministic and simulated annealing; clustering for vectorial, histogram and relational data; model selection; graphical models.
LernzielThe course surveys recent methods of statistical learning. The fundamentals of machine learning as presented in the course "Introduction to Machine Learning" are expanded and in particular, the theory of statistical learning is discussed.
Inhalt# Boosting: A state-of-the-art classification approach that is sometimes used as an alternative to SVMs in non-linear classification.
# Theory of estimators: How can we measure the quality of a statistical estimator? We already discussed bias and variance of estimators very briefly, but the interesting part is yet to come.
# Statistical learning theory: How can we measure the quality of a classifier? Can we give any guarantees for the prediction error?
# Variational methods and optimization: We consider optimization approaches for problems where the optimizer is a probability distribution. Concepts we will discuss in this context include:

* Maximum Entropy
* Information Bottleneck
* Deterministic Annealing

# Clustering: The problem of sorting data into groups without using training samples. This requires a definition of ``similarity'' between data points and adequate optimization procedures.
# Model selection: We have already discussed how to fit a model to a data set in ML I, which usually involved adjusting model parameters for a given type of model. Model selection refers to the question of how complex the chosen model should be. As we already know, simple and complex models both have advantages and drawbacks alike.
# Reinforcement learning: The problem of learning through interaction with an environment which changes. To achieve optimal behavior, we have to base decisions not only on the current state of the environment, but also on how we expect it to develop in the future.
Skriptno script; transparencies of the lectures will be made available.
LiteraturDuda, Hart, Stork: Pattern Classification, Wiley Interscience, 2000.

Hastie, Tibshirani, Friedman: The Elements of Statistical Learning, Springer, 2001.

L. Devroye, L. Gyorfi, and G. Lugosi: A probabilistic theory of pattern recognition. Springer, New York, 1996
Voraussetzungen / BesonderesRequirements:

basic knowledge of statistics, interest in statistical methods.

It is recommended that Introduction to Machine Learning (ML I) is taken first; but with a little extra effort Statistical Learning Theory can be followed without the introductory course.
151-0104-00LUncertainty Quantification for Engineering & Life Sciences Belegung eingeschränkt - Details anzeigen
Findet dieses Semester nicht statt.
Number of participants limited to 40.
W4 KP3GP. Koumoutsakos
KurzbeschreibungQuantification of uncertainties in computational models pertaining to applications in engineering and life sciences. Exploitation of massively available data to develop computational models with quantifiable predictive capabilities. Applications of Uncertainty Quantification and Propagation to problems in mechanics, control, systems and cell biology.
LernzielThe course will teach fundamental concept of Uncertainty Quantification and Propagation (UQ+P) for computational models of systems in Engineering and Life Sciences. Emphasis will be placed on practical and computational aspects of UQ+P including the implementation of relevant algorithms in multicore architectures.
InhaltTopics that will be covered include: Uncertainty quantification under
parametric and non-parametric modelling uncertainty, Bayesian inference with model class assessment, Markov Chain Monte Carlo simulation, prior and posterior reliability analysis.
SkriptThe class will be largely based on the book: Data Analysis: A Bayesian Tutorial by Devinderjit Sivia as well as on class notes and related literature that will be distributed in class.
Literatur1. Data Analysis: A Bayesian Tutorial by Devinderjit Sivia
2. Probability Theory: The Logic of Science by E. T. Jaynes
3. Class Notes
Voraussetzungen / BesonderesFundamentals of Probability, Fundamentals of Computational Modeling
Seminar in Computational Science
NummerTitelTypECTSUmfangDozierende
252-5251-00LComputational ScienceW2 KP2SP. Arbenz, T. Hoefler, P. Koumoutsakos
KurzbeschreibungSeminarteilnehmer studieren grundlegende Papiere aus der Computational Science und halten in einem 40-min. Vortrag (auf Englisch). Der Vortrag (Struktur, Inhalt, Darstellung) ist mit dem verantw. Professor vorzubesprechen. Der Vortrag muss so gehalten werden, dass ihn die anderen Seminarteilnehmer verstehen und etwas lernen können. Teilnahme während des ganzen Semesters ist
vorgeschrieben.
LernzielStudieren und präsentieren einer grundlegenden Arbeit aus dem Bereich der Computational Science. Lernen, über ein wissenschaftliches Thema vorzutragen.
InhaltTeilnehmer am Seminar studieren grundlegende Papiere aus dem Bereich Computational Science und tragen darüber (auf Englisch) in einem 40-minütigen Vortrag vor. Vor der Präsentation soll der Vortrag (bzgl. Struktur, Inhalt, Darstellung) mit dem verantwortlichen Professor besprochen werden. Der Vortrag muss in einer Weise gegeben werden, dass ihn die anderen Seminarteilnehmer verstehen können und etwas lernen können. Teilnahme während des ganzen Semesters ist vorgeschrieben.
Skriptkeines
LiteraturPapiere werden in der ersten Semesterwoche verteilt.
252-5704-00LAdvanced Methods in Computer Graphics Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 24
W2 KP2SM. Gross, O. Sorkine Hornung
KurzbeschreibungThis seminar covers advanced topics in computer graphics with a focus on the latest research results. Topics include modeling, rendering,
animation, physical simulation, computational photography, and others.
LernzielThe goal is to obtain an in-depth understanding of actual problems and
research topics in the field of computer graphics as well as improve
presentation and critical analysis skills.
Vertiefung in Distributed Systems
Kernfächer der Vertiefung in Distributed Systems
NummerTitelTypECTSUmfangDozierende
227-0558-00LPrinciples of Distributed Computing Information W6 KP2V + 2U + 1AR. Wattenhofer
KurzbeschreibungWe study the fundamental issues underlying the design of distributed systems: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.
LernzielDistributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your new multi-core laptop. This course introduces the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We will cover a fresh topic every week.
InhaltDistributed computing models and paradigms, e.g. message passing, shared memory, synchronous vs. asynchronous systems, time and message complexity, peer-to-peer systems, small-world networks, social networks, sorting networks, wireless communication, and self-organizing systems.

Distributed algorithms, e.g. leader election, coloring, covering, packing, decomposition, spanning trees, mutual exclusion, store and collect, arrow, ivy, synchronizers, diameter, all-pairs-shortest-path, wake-up, and lower bounds
SkriptAvailable. Our course script is used at dozens of other universities around the world.
LiteraturLecture Notes By Roger Wattenhofer. These lecture notes are taught at about a dozen different universities through the world.

Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6

Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest.
The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8

Disseminatin of Information in Communication Networks
Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger.
Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2

Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Frank Thomson Leighton.
Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1-55860-117-1

Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8
Voraussetzungen / BesonderesCourse pre-requisites: Interest in algorithmic problems. (No particular course needed.)
Wahlfächer der Vertiefung in Distributed Systems
NummerTitelTypECTSUmfangDozierende
252-0312-00LUbiquitous Computing Information W3 KP2VF. Mattern
KurzbeschreibungUbiquitous computing integrates tiny wirelessly connected computers and sensors into the environment and everyday objects. Main topics: The vision of ubiquitous computing, trends in technology, smart cards, RFID, Personal Area Networks (Bluetooth), sensor networks, location awareness, privacy and security, application areas, economic and social impact.
LernzielThe vision of ubiquitous computing, trends in technology, smart cards, RFID, Personal Area Networks (Bluetooth), sensor networks, location awareness, privacy and security, application areas, economic and social impact.
SkriptCopies of slides will be made available
LiteraturWill be provided in the lecture. To put you in the mood:
Mark Weiser: The Computer for the 21st Century. Scientific American, September 1991, pp. 94-104
252-0807-00LInformation Systems Laboratory Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 16

Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 Kreditpunkte über Laboratorien erarbeitet werden. Diese Labs gelten nur für das Masterstudium. Weitere Laboratorien werden auf dem Beiblatt aufgeführt.
W10 KP9PM. Norrie
KurzbeschreibungThe purpose of this laboratory course is to practically explore modern techniques to build large-scale distributed information systems. Participants will work in groups of three or more students, and develop projects in several phases.
LernzielThe students will gain experience of working with technologies used in the design and development of information systems.
InhaltFirst week: Kick-off meeting and project assignment
Second week: Meeting with the project supervisor to discuss the goals and scope of the project.
During the semester: Individual group work. Each team member should contribute to the project roughly about 10h/week, excluding any necessary reading or self-studying (e.g. the time spent to learn a new technology). In addition, it is expected that each team can meet with their supervisor on a regular basis.
End of semester: Final presentation.
252-0817-00LDistributed Systems Laboratory Information
Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 Kreditpunkte über Laboratorien erarbeitet werden. Weitere Laboratorien werden auf dem Beiblatt aufgeführt.
W10 KP9PG. Alonso, F. Mattern, T. Roscoe, R. Wattenhofer
KurzbeschreibungEntwicklung und / oder Evaluation eines umfangreicheren praktischen Systems mit Technologien aus dem Gebiet der verteilten Systeme. Das Projekt kann aus unterschiedlichen Teilbereichen (von Web-Services bis hin zu ubiquitären Systemen) stammen; typische Technologien umfassen drahtlose Ad-hoc-Netze oder Anwendungen auf Mobiltelefonen.
LernzielErwerb praktischer Kenntnisse bei Entwicklung und / oder Evaluation eines umfangreicheren praktischen Systems mit Technologien aus dem Gebiet der verteilten Systeme.
InhaltEntwicklung und / oder Evaluation eines umfangreicheren praktischen Systems mit Technologien aus dem Gebiet der verteilten Systeme. Das Projekt kann aus unterschiedlichen Teilbereichen (von Web-Services bis hin zu ubiquitären Systemen) stammen; typische Technologien umfassen drahtlose Ad-hoc-Netze oder Anwendungen auf Mobiltelefonen. Zu diesem Praktikum existiert keine Vorlesung. Bei Interesse bitte einen der beteiligten Professoren oder einen Assistenten der Forschungsgruppen kontaktieren.
263-3501-00LAdvanced Computer Networks Information W5 KP2V + 2UT. Roscoe, P. M. Stüdi
KurzbeschreibungThis course covers a set of advanced topics in computer networks. The focus is on principles, architectures, and protocols used in modern networked systems, such as the Internet itself, wireless and mobile networks, and large-scale peer-to-peer systems.
LernzielThe goals of the course is to build on basic networking course material in providing an understanding of the tradeoffs and existing technology in building large, complex networked systems, and provide concrete experience of the challenges through a series of lab exercises.
InhaltThe focus of the course is on principles, architectures, and protocols used in modern networked systems. Topics include: wireless networks and mobility issues at the network and transport layer (Mobile IP and micromobility protocols, TCP in wireless environments). Mobile phone networks. Overlay networks, flat routing protocols (DHTs), and peer-to-peer architectures. The Border Gateway Protocol (BGP) in practice.
263-3700-00LUser Interface Engineering Information W4 KP2V + 1UO. Hilliges
KurzbeschreibungAn in-depth introduction to the core concepts of post-desktop user interface engineering. Current topics in UI research, in particular non-desktop based interaction, mobile device interaction, augmented and mixed reality, and advanced sensor and output technologies.
LernzielStudents will learn about fundamental aspects pertaining to the design and implementation of modern (non-desktop) user interfaces. Students will understand the basics of human cognition and capabilities as well as gain an overview of technologies for input and output of data. The core competency acquired through this course is a solid foundation in data-driven algorithms to process and interpret human input into computing systems. 

At the end of the course students should be able to understand and apply advanced hardware and software technologies to sense and interpret user input. Students will be able to develop systems that incorporate non-standard sensor and display technologies and will be able to apply data-driven algorithms in order to extract semantic meaning from raw sensor data.
InhaltUser Interface Engineering covers theoretical and practical aspects relating to the design and implementation of modern non-standard user interfaces. A particular area of interest are machine-learning based algorithms for input recognition in advanced non-desktop user interfaces, including UIs for mobile devices but also Augmented Reality UIs, gesture and multi-modal user interfaces. 

The course covers three main areas:
I) Basic principles of human cognition and perception (and their application for UIs)
II) (Hardware) technologies for user input sensing
III) Data-driven methods for input recognition (gestures, speech, etc.)

Specific topics include: 
* Model Human Processor (MHP) model - prediction of task completion times.
* Fitts' Law - measure of information load on human motor and cognitive system during user interaction.
* Touch sensor technologies (capacitive, resistive, force sensing etc).
* Data-driven algorithms for user input recognition:
- SVMs for classification and regression
- Randomized Decision Forests for gesture recognition and pose estimation
- Markov chains and HMMs for gesture and speech recognition
- Optical flow and other image processing and computer vision techniques
- Input filtering (Kalman)
* Applications of the above in HCI research
SkriptSlides and other materials will be available online. Lecture slides on a particular topic will typically not be made available prior the completion of that lecture.
LiteraturA detailed reading list will be made available on the course website.
Voraussetzungen / BesonderesPrerequisites: proficiency in a programming language such as C, programming methodology, problem analysis, program structure, etc. Normally met through an introductory course in programming in C, C++, Java.

The following courses are strongly recommended as prerequisite:
* "Human Computer Interaction"
* "Machine Learning"
* "Visual Computing" or "Computer Vision"

The course will be assessed by a written Midterm and Final examination in English. No course materials or electronic devices can be used during the examination. Note that the examination will be based on the contents of the lectures, the associated reading materials and the exercises.
Seminar in Distributed Systems
NummerTitelTypECTSUmfangDozierende
252-3600-02LUbiquitous Computing Seminar Information W2 KP2SF. Mattern, O. Hilliges
KurzbeschreibungSeminar zu unterschiedlichen Themen aus den Bereichen Pervasive Computing, Ubiquitous Computing, Mensch-Maschine-Interaktion, Verteilte Systeme und verwandter Gebiete.
LernzielErwerb von Kenntnissen zu unterschiedlichen aktuellen Themen aus den Bereichen Pervasive Computing, Ubiquitous Computing, Mensch-Maschine Interaktion Verteilte Systeme und verwandter Gebiete.
263-3830-00LSoftware Defined Networking: The Data Centre Perspective Information W2 KP2ST. Roscoe
KurzbeschreibungSoftware Defined Networks (SDN) is a change supported not only by research but also industry and redifens how traditional network management and configuration is been done.
LernzielThrough review and discussion of literature on an exciting new trend in networking, the students get the opportunity to get familiar with one of the most promising new developments in data centre connectivity, while at the same time they can develop soft skills related to the evaluation and presentation of professional content.
InhaltSoftware Defined Networks (SDN) is a change supported not only by research but also industry and redifens how traditional network management and configuration is been done. Although much has been already investigated and there are already functional SDN-enabled switches there are many open questions ahead of the adoption of SDN inside and outside the data centre (traditional or cloud-based). With a series of seminars we will reflect on the challenges, adoption strategies and future trends of SDN to create an understanding how SDN is affecting the network operators' industry.
LiteraturThe seminar is based on recent publications by academia and industry. Links to the publications are placed on the Seminar page and can be downloaded from any location with access to the ETH campus network.
Voraussetzungen / BesonderesThe seminar bases on active and interactive participation of the students.
227-0126-00LAdvanced Topics in Networked Embedded Systems Information Belegung eingeschränkt - Details anzeigen
Number of participants limited to 12.
W2 KP1SO. Saukh, J. Beutel, L. Thiele
KurzbeschreibungThe seminar will cover advanced topics in networked embedded systems. A particular focus are cyber-physical systems and sensor networks in various application domains.
LernzielThe goal is to get a deeper understanding on leading edge technologies in the discipline, on classes of applications, and on current as well as future research directions.
InhaltThe seminar enables Master students, PhDs and Postdocs to learn about latest breakthroughs in wireless sensor networks, networked embedded systems and devices, and energy-harvesting in several application domains, including environmental monitoring, tracking, smart buildings and control. Participants are requested to actively participate in the organization and preparation of the seminar.
227-0559-00LSeminar in Distributed Computing Information W2 KP2SR. Wattenhofer
KurzbeschreibungIn this seminar participating students present and discuss recent research papers in the area of distributed computing. The seminar consists of algorithmic as well as systems papers in distributed computing theory, peer-to-peer computing, ad hoc and sensor networking, or multi-core computing.
LernzielIn the last two decades, we have experienced an unprecedented growth in the area of distributed systems and networks; distributed computing now encompasses many of the activities occurring in today's computer and communications world. This course introduces the basics of distributed computing, highlighting common themes and techniques. We study the fundamental issues underlying the design of distributed systems: communication, coordination, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.

In this seminar, students present the latest work in this domain.

Seminar language: English
InhaltDifferent each year. For details see: www.disco.ethz.ch/courses.html
SkriptSlides of presentations will be made available.
LiteraturPapers.
The actual paper selection can be found on www.disco.ethz.ch/courses.html.
Vertiefung in Information Security
Kernfächer der Vertiefung in Information Security
NummerTitelTypECTSUmfangDozierende
252-0407-00LCryptography Information W7 KP3V + 2U + 1AU. Maurer
KurzbeschreibungFundamentals and applications of cryptography. Cryptography as a mathematical discipline: reductions, constructive cryptography paradigm, security proofs. The discussed primitives include cryptographic functions, pseudo-randomness, symmetric encryption and authentication, public-key encryption, key agreement, and digital signature schemes. Selected cryptanalytic techniques.
LernzielThe goals are:
(1) understand the basic theoretical concepts and scientific thinking in cryptography;
(2) understand and apply some core cryptographic techniques and security proof methods;
(3) be prepared and motivated to access the scientific literature and attend specialized courses in cryptography.
InhaltSee course description.
Skriptyes.
Voraussetzungen / BesonderesFamiliarity with the basic cryptographic concepts as treated for
example in the course "Information Security" is required but can
in principle also be acquired in parallel to attending the course.
Wahlfächer der Vertiefung in Information Security
NummerTitelTypECTSUmfangDozierende
252-0408-00LCryptographic Protocols Information W5 KP2V + 2UU. Maurer, M. Hirt
KurzbeschreibungThe course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
LernzielIndroduction to a very active research area with many gems and paradoxical
results. Spark interest in fundamental problems.
InhaltThe course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
Skriptthe lecture notes are in German, but they are not required as the entire
course material is documented also in other course material (in english).
Voraussetzungen / BesonderesA basic understanding of fundamental cryptographic concepts
(as taught for example in the course Information Security or
in the course Cryptography) is useful, but not required.
263-4600-00LFormal Methods for Information Security Information W4 KP2V + 1US. Radomirovic, M. Torabi Dashti
KurzbeschreibungThe course focuses on formal methods for the modelling and analysis of security and privacy concerns in critical systems, ranging from access control policies to cryptographic protocols.
LernzielThe students will learn the key ideas and theoretical foundations of formal modelling and analysis of security protocols and policies. The students will complement their theoretical knowledge by solving practical exercises and using various related tools.
InhaltThe lecture treats formal methods for the modelling and analysis of security-critical systems.

The first part of the lecture focuses on access control policies in centralized and distributed settings. Access control policies are an integral part of modern Internet services; examples include single sign-on endpoints, distributed trust management in social Websites, and peer-to-peer networks. The lectures cover the formal foundations of authorization systems, and their applications to the synthesis and analysis of access control policies. We will also study a few notable existing models, such as XACML, DKAL and PBel.

The second part of the lecture concentrates on cryptographic protocols. Cryptographic protocols (such as SSL/TLS, SSH, Kerberos, SAML single-sign on, and IPSec) form the basis for secure communication and business processes. Numerous attacks on published protocols show that the design of cryptographic protocols is extremely error-prone. A rigorous analysis of these protocols is therefore indispensable. The lecture covers the theoretical basis for the formal modeling and analysis of such protocols. Specifically, we discuss their operational semantics, the formalization of security properties, and techniques and algorithms for their verification. In addition to the classical security properties for confidentiality and authentication, we will study privacy properties and the fairness property in contract signing. The accompanying tutorials provide an opportunity to apply the theory and tools to concrete protocols.
Seminar in Information Security
NummerTitelTypECTSUmfangDozierende
252-4800-00LQuantum Information and Cryptography Information W2 KP2SS. Wolf
KurzbeschreibungEs werden verschiedene Themen im Grenzgebiet der Bereiche Quantenphysik, Informationstheorie und Kryptographie behandelt.
LernzielThemen im Grenzgebiet der Bereiche Quantenphysik, Informationstheorie und Kryptographie werden behandelt.
Vertiefung in Information Systems
Kernfächer der Vertiefung in Information Systems
NummerTitelTypECTSUmfangDozierende
252-0374-00LWeb Engineering Information W6 KP2V + 2U + 1AM. Norrie
KurzbeschreibungThe course teaches students about the basic principles of web engineering by examining the various technologies used in modern web sites in detail together with the step-by-step processes used to develop state-of-the art web sites.
LernzielThe goals of the course are that students should be able to:
- systematically develop state-of-the-art web sites using a range of technologies, platforms and frameworks in common use
- understand the role of different technologies and how they are combined in practice
- analyse requirements and select appropriate technologies, platforms and frameworks
InhaltThe first half of the course will introduce the various technologies used in state-of-the-art web sites together with the step-by-step development process. From the beginning, we will cater for access from multiple devices such as mobile phones and tablets as well as desktop browsers and show how technologies such as HTML5, CSS3 and JavaScript can be used to support rich forms of interaction.

In the second half of the course, we will look at how various platforms and frameworks are used to support web site development. We will start by examining the model behind modern content management platforms such as WordPress and showing how web sites with dynamic content can be systematically developed using these platforms. This will be followed by looking at the more traditional programming approaches by first introducing the Java web technology stack and then a modern web application framework. Finally, we will present model-driven approaches to web engineering.

The material covered in lectures will be supported by a series of practical exercises that will take the students through the development processes.
Wahlfächer der Vertiefung in Information Systems
NummerTitelTypECTSUmfangDozierende
252-0312-00LUbiquitous Computing Information W3 KP2VF. Mattern
KurzbeschreibungUbiquitous computing integrates tiny wirelessly connected computers and sensors into the environment and everyday objects. Main topics: The vision of ubiquitous computing, trends in technology, smart cards, RFID, Personal Area Networks (Bluetooth), sensor networks, location awareness, privacy and security, application areas, economic and social impact.
LernzielThe vision of ubiquitous computing, trends in technology, smart cards, RFID, Personal Area Networks (Bluetooth), sensor networks, location awareness, privacy and security, application areas, economic and social impact.
SkriptCopies of slides will be made available
LiteraturWill be provided in the lecture. To put you in the mood:
Mark Weiser: The Computer for the 21st Century. Scientific American, September 1991, pp. 94-104
252-0355-00LObject Databases Information W4 KP2V + 1UA. K. de Spindler
KurzbeschreibungThe course examines the principles and techniques of providing data management in object-oriented programming environments. After introducing the basics of object storage and management, we will cover semantic object models and their implementation. Finally, we discuss advanced data management services such as version models for temporal and engineering databases and for software configuration.
LernzielThe goal of this course is to extend the student's knowledge of database technologies towards object-oriented solutions. Starting with basic principles, students also learn about commercial products and research projects in the domain of object-oriented data management. Apart from getting to know the characteristics of these approaches and the differences between them, the course also discusses what application requirements justify the use of object-oriented databases. Therefore, it educates students to make informed decisions on when to use what database technology.
InhaltThe course examines the principles and techniques of providing data management in object-oriented programming environments. It is divided into three parts that cover the road from simple object persistence, to object-oriented database management systems and to advanced data management services. In the first part, object serialisation and object-relational mapping frameworks will be introduced. Using the example of the open-source project db4o, the utilisation, architecture and functionality of a simple object-oriented database is discussed. The second part of the course is dedicated to advanced topics such as industry standards and solutions for object data management as well as storage and index technologies. Additionally, advanced data management services such as version models for temporal and engineering databases as well as for software configuration are discussed. In the third and last part of the course, an object-oriented data model that features a clear separation of typing and classification is presented. Together with the model, its implementation in terms of an object-oriented database management system is discussed also. Finally, an extension of this data model is presented that allows context-aware data to be managed.
Voraussetzungen / BesonderesPrerequisites: Knowledge about the topics of the lectures "Introduction to Databases" and "Information Systems" is required.
252-0807-00LInformation Systems Laboratory Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 16

Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 Kreditpunkte über Laboratorien erarbeitet werden. Diese Labs gelten nur für das Masterstudium. Weitere Laboratorien werden auf dem Beiblatt aufgeführt.
W10 KP9PM. Norrie
KurzbeschreibungThe purpose of this laboratory course is to practically explore modern techniques to build large-scale distributed information systems. Participants will work in groups of three or more students, and develop projects in several phases.
LernzielThe students will gain experience of working with technologies used in the design and development of information systems.
InhaltFirst week: Kick-off meeting and project assignment
Second week: Meeting with the project supervisor to discuss the goals and scope of the project.
During the semester: Individual group work. Each team member should contribute to the project roughly about 10h/week, excluding any necessary reading or self-studying (e.g. the time spent to learn a new technology). In addition, it is expected that each team can meet with their supervisor on a regular basis.
End of semester: Final presentation.
252-3005-00LIntroduction to Natural Language Processing Information W4 KP2V + 1UE. Alfonseca Cubero, M. Ciaramita
KurzbeschreibungThis course presents an introduction to general topics and techniques used in natural language processing today, primarily focusing on statistical approaches. The course provides an overview of the primary areas of research in language processing as well as a detailed exploration of the models and techniques used both in research and in commercial natural language systems.
LernzielThe objective of the course is to learn the basic concepts in the statistical processing of natural languages. The course will be project-oriented so that the students can also gain hands-on experience with state-of-the-art tools and techniques.
InhaltThis course presents an introduction to general topics and techniques used in natural language processing today, primarily focusing on statistical approaches. The course provides an overview of the primary areas of research in language processing as well as a detailed exploration of the models and techniques used both in research and in commercial natural language systems.
LiteraturLectures will be presented from the Jurafsky and Martin text accompanied by related technical papers where necessary.
263-5200-00LData Mining: Learning from Large Data Sets Information
Findet dieses Semester nicht statt.
The course will be offered again in the autumn semester 2015.
W4 KP2V + 1UA. Krause
KurzbeschreibungMany scientific and commercial applications require insights from massive, high-dimensional data sets. This courses introduces principled, state-of-the-art techniques from statistics, algorithms and discrete and convex optimization for learning from such large data sets. The course both covers theoretical foundations and practical applications.
LernzielMany scientific and commercial applications require us to obtain insights from massive, high-dimensional data sets. In this graduate-level course, we will study principled, state-of-the-art techniques from statistics, algorithms and discrete and convex optimization for learning from such large data sets. The course will both cover theoretical foundations and practical applications.
InhaltTopics covered:
- Dealing with large data (Data centers; Map-Reduce/Hadoop; Amazon Mechanical Turk)
- Fast nearest neighbor methods (Shingling, locality sensitive hashing)
- Online learning (Online optimization and regret minimization, online convex programming, applications to large-scale Support Vector Machines)
- Multi-armed bandits (exploration-exploitation tradeoffs, applications to online advertising and relevance feedback)
- Active learning (uncertainty sampling, pool-based methods, label complexity)
- Dimension reduction (random projections, nonlinear methods)
- Data streams (Sketches, coresets, applications to online clustering)
- Recommender systems
Voraussetzungen / BesonderesPrerequisites: Solid basic knowledge in statistics, algorithms and programming. Background in machine learning is helpful but not required.
Seminar in Information Systems
NummerTitelTypECTSUmfangDozierende
252-3002-00LAlgorithms for Database Systems Information W2 KP2SP. Widmayer, A. Khan
KurzbeschreibungQuery processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithms for database systems.
252-3100-00LComputer Supported Cooperative Work Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 18
W2 KP2SM. Norrie
KurzbeschreibungIm Forschungsbereich "computerunterstütztes kooperatives Arbeiten" (CSCW) steht die Zusammenarbeit von Benutzern mittels EDV-Technologie im Mittelpunkt des Interesses. Es handelt sich dabei um multidisziplinäre Forschung welche soziale, theoretische, praktische und technische Aspekte von Zusammenarbeit mit einschliesst.
Lernzielsee above
Vertiefung in Software Engineering
Kernfächer der Vertiefung in Software Engineering
Im FS15 wird keine Veranstaltung in dieser Kategorie angeboten.
Wahlfächer der Vertiefung in Software Engineering
NummerTitelTypECTSUmfangDozierende
252-0268-00LConcepts of Concurrent Computation Information W7 KP3V + 2U + 1AS. Nanz
KurzbeschreibungConcurrent programming is one of the major challenges in software development. The "Concepts of Concurrent Computation" course explores important models of concurrency, with a special emphasis on concurrent object-oriented programming and process calculi.
LernzielAfter completing this course, students will understand the principles and techniques of concurrent programming, supporting theories allowing formal reasoning about concurrent systems, and advances in concurrent object-oriented programming.
InhaltTopics include:

Overview
- Concurrent and parallel programming
- Multitasking and multiprocessing
- Shared-memory and distributed-memory multiprocessing
- Notion of process and thread
- Performance of concurrent systems

Approaches to concurrent programming
- Issues: data races, deadlock, starvation
- Synchronization algorithms
- Semaphores
- Monitors
- Java and .NET multithreading

Concurrent object-oriented programming: the SCOOP model
- Processors; handling an object
- Synchronous and asynchronous feature calls
- Design by Contract in a concurrent context
- Separate objects and entities
- Accessing separate objects; validity rules
- Synchronization: waiting, reserving, preconditions as wait conditions, Wait by Necessity
- Examples and applications

Programming approaches to concurrency
- Message-passing vs. shared-memory communication
- Language examples: Ada, Polyphonic C#, Erlang (Actors), X10, Linda, Cilk and others.
- Lock-free programming
- Software Transactional Memory

Reasoning about concurrent programs
- Properties of concurrent programs
- Temporal logic
- Process calculi: CCS and coalgebra
- Petri nets
- Proofs of concurrent programs
Literatur- Bertrand Meyer and Sebastian Nanz: Course textbook (draft)
- Mordechai Ben-Ari: Principles of Concurrent and Distributed Programming. Prentice Hall, 2006
- Maurice Herlihy and Nir Shavit: The Art of Multiprocessor Programming. Morgan Kaufmann, 2008
- Gregory R. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming. Addison Wesley, 1999
Voraussetzungen / BesonderesThe course's lectures are of two different kinds: the Tuesday session is a traditional lecture; the Wednesday session is devoted to seminar talks by the student participants, based on research papers related to the topics of the course. The research papers to be presented will be assigned at the start of the course.
263-2300-00LHow To Write Fast Numerical Code Information
Prerequisite: Master student, solid C programming skills.
W6 KP3V + 2UM. Püschel
KurzbeschreibungThis course introduces the student to the foundations and state-of-the-art techniques in developing high performance software for numerical functionality such as linear algebra and others. The focus is on optimizing for the memory hierarchy and for special instruction sets. Finally, the course will introduce the recent field of automatic performance tuning.
LernzielSoftware performance (i.e., runtime) arises through the interaction of algorithm, its implementation, and the microarchitecture the program is run on. The first goal of the course is to provide the student with an understanding of this interaction, and hence software performance, focusing on numerical or mathematical functionality. The second goal is to teach a general systematic strategy how to use this knowledge to write fast software for numerical problems. This strategy will be trained in a few homeworks and semester-long group projects.
InhaltThe fast evolution and increasing complexity of computing platforms pose a major challenge for developers of high performance software for engineering, science, and consumer applications: it becomes increasingly harder to harness the available computing power. Straightforward implementations may lose as much as one or two orders of magnitude in performance. On the other hand, creating optimal implementations requires the developer to have an understanding of algorithms, capabilities and limitations of compilers, and the target platform's architecture and microarchitecture.

This interdisciplinary course introduces the student to the foundations and state-of-the-art techniques in high performance software development using important functionality such as linear algebra functionality, transforms, filters, and others as examples. The course will explain how to optimize for the memory hierarchy, take advantage of special instruction sets, and, if time permits, how to write multithreaded code for multicore platforms. Much of the material is based on state-of-the-art research.

Further, a general strategy for performance analysis and optimization is introduced that the students will apply in group projects that accompany the course. Finally, the course will introduce the students to the recent field of automatic performance tuning.
263-2810-00LAdvanced Compiler Design Information W7 KP3V + 2U + 1AT. Gross
KurzbeschreibungThis course covers advanced topics in compiler design: SSA intermediate representation and its use in optimization, just-in-time compilation, profile-based compilation, exception handling in modern programming languages.
LernzielUnderstand translation of object-oriented programs, opportunities and difficulties in optimizing programs using state-of-the-art techniques (profile-based compilation, just-in-time compilation, runtime system interaction)
InhaltThis course builds conceptually on Compiler Design (a basic class for advanced undergraduates), but this class is not a prerequisite. Students should however have a solid understanding of basic compiler technology.

The focus is on handling the key features of modern object-oriented programs. We review implementations of single and multiple inheritance (incl. object layout, method dispatch) and optimization opportunities.

Specific topics: intermediate representations (IR) for optimizing compilers, static single assignment (SSA) representation, constant folding, partial redundancy optimizations, profiling, profile-guided code generation. Special topics as time permits: debugging optimized code, multi-threading, data races, object races, memory consistency models, programming language design. Review of single inheritance, multiple inheritance, object layout, method dispatch, type analysis, type propagation and related topics.

This course provides another opportunity to explore software design in a medium-scale software project.
LiteraturAho/Lam/Sethi/Ullmann, Compilers - Principles, Techniques, and Tools (2nd Edition). In addition, papers as provided in the class.
Voraussetzungen / BesonderesA basic course on compiler design is helpful but not mandatory. Student should have programming skills/experience to implement an optimizer (or significant parts of an optimizer) for a simple object-oriented language. The programming project is implemented using Java.
263-2910-00LProgram Analysis Information W4 KP2V + 1UM. Vechev
KurzbeschreibungModern program analysis techniques are the predominant approach for automatically reasoning about real world programs -- its techniques have been applied in a vast range of application domains.

The course provides an introduction to the fundamental principles, applications, and research trends of modern program analysis.
LernzielThe course has 4 main objectives:

* Understand the foundational principles behind program analysis techniques.

* Understand how to apply these principles to build practical, working analyzers for real world problems.

* Understand how to combine these techniques with other approaches (e.g. machine learning techniques) to build powerful end-to-end reasoning systems, not possible otherwise.

* Gain familiarity with the state-of-the-art in the area and the future research trends in the next 5-10 years.
InhaltThe last decade has seen an explosion in modern program analysis techniques. These techniques are increasingly being used to reason about a vast range of computational paradigms including:

* finding security violations in web and mobile applications such as JavaScript and Android
* practical type checking and inference (e.g. Facebook's recently released Flow analyzer).
* combinations with machine learning techniques for learning from massive programming data guiding prediction of program properties and prediction of new code.
* establishing properties of biological systems (e.g. DNA computation)
* finding serious errors in systems software (e.g. Linux kernel, device drivers, file systems)
* automatic discovery of new algorithms (e.g. concurrent data structures, distributed algorithms) and end-user programming.
* compilers for domain specific languages
* architecture-driven reasoning of concurrent software (e.g. Intel's x86, ARM, IBM's Power).

This course will provide a comprehensive introduction to modern, state-of-the-art program analysis concepts, principles and research trends, including:

* Static & Dynamic Analysis:
- concepts: memory safety, type checking and inference, typestate, concurrency analysis, abstract interpretation (domains, soundness, precision, fixed points)
- frameworks: Valgrind, FastTrack, EventRacer, Apron, PPL, Facebook's Flow analyzer.

* Statistical program reasoning:
- concepts: combining analysis with statistical models (e.g. Language models, Bayesian networks, Neural networks, etc)
- frameworks: Slang, JSNice (http://jsnice.org)

* Predicate abstraction:
- concepts: Graf-Saidi, Boolean programs, lazy abstraction
- frameworks: Microsoft's SLAM for C programs, Fender

* Symbolic execution:
- concepts: SMT, concolic execution
- frameworks: S2E, KLEE, Sage

* Security Analysis:
- concepts: static + dynamic combination
- example: malware detection

* Pointer analysis:
- concepts: Andersen's, Steensgaard's analysis
- frameworks: Soot, LLVM, WALA

* Program synthesis:
- concepts: L*, version spaces, PBE, CEGIS
- frameworks: Sketch, AGS, SmartEdit, ReSynth

* Applications of Analysis & Synthesis:
- GPU programs, security errors, device drivers, concurrent algorithms, end-user programming.

To gain a deeper understanding of how to apply these techniques in practice, the course will involve a small hands-on programming project where based on the principles introduced in class, the students will build a program reasoning engine (e.g. analysis, predictions) for a modern programming language.
SkriptThe lectures notes will be distributed in class.
LiteraturDistributed in class.
Voraussetzungen / BesonderesThis course is aimed at both graduate (M.Sc., PhD) students as well as advanced undergraduate students.
252-0284-00LJava and C # in depth Information
Findet dieses Semester nicht statt.
W5 KP2V + 1U + 1ANoch nicht bekannt
KurzbeschreibungJava and C#, both similar and each with its own characteristics, are important languages with wide applications. This course goes into the depth of both languages, each considered for itself but also in comparison with the other.
LernzielThis course provides students with an in-depth understanding of:

- The language design philosophy behind Java.
- The language design philosophy behind C#.
- The key language mechanisms of both languages, and how to use them.
- The main properties differentiating the languages.
InhaltIntroduction, object-oriented concepts.
Frameworks overview and in-the-small language features.
Classes, objects, inheritance, polymorphism.
Packages/assemblies, abstract classes and interfaces.
Exceptions and genericity.
Reflection.
Threads and Concurrency.
Persistence.
Web Services.
Voraussetzungen / BesonderesThe course is particularly intended for students already having a knowledge of an object-oriented programming language (one of the two listed, or another one such as Eiffel).
252-0286-00LSystem Construction Information
Findet dieses Semester nicht statt.
The course will be offered again in the autumn semester 2015.
W4 KP2V + 1Ukeine Angaben
KurzbeschreibungMain goal is teaching knowledge and skills needed for building custom operating systems and runtime environments. Relevant topics are studied at the example of sufficiently simple systems that have been built at our Institute in the past, ranging from purpose-oriented single processor real-time systems up to generic system kernels on multi-core hardware.
LernzielThe lecture's main goal is teaching of knowledge and skills needed for building custom operating systems and runtime environments.

The lecture intends to supplement more abstract views of software construction, and to contribute to a better understanding of "how it really works" behind the scenes.
InhaltCase Study 1: Embedded System
- Safety-critical and fault-tolerant monitoring system
- Based on an auto-pilot system for helicopters

Case Study 2: Multi-Processor Operating System
- Universal operating system for symmetric multiprocessors
- Shared memory approach
- Based on Language-/System Codesign (Active Oberon / A2)

Case Study 3: Custom designed Single-Processor System
- RISC Single-processor system designed from scratch
- Hardware on FPGA
- Graphical workstation OS and compiler (Project Oberon)

Case Study 4: Custom-designed Multi-Processor System
- Special purpose heterogeneous system on a chip
- Masssively parallel hard- and software architecture based on message passing
- Focus: dataflow based applications
SkriptPrinted lecture notes will be delivered during the lecture. Slides will also be available from the lecture homepage.
Seminar in Software Engineering
NummerTitelTypECTSUmfangDozierende
263-2100-00LResearch Topics in Software Engineering Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 22
W2 KP2ST. Hoefler
KurzbeschreibungThis seminar introduces students to fundamental results in parallel programming and design. Students will study and present research papers that span topics in both theory and practice, ranging from foundations parallel computing to applications. The focus will be on fundamental lower and upper bounds, thus, many papers will be dated. Students need a solid mathematical background.
LernzielAt the end of the course, the students should be familiar with a broad range of key research results in the area of parallel computing, know how to read and assess papers in the area, and be able to highlight practical examples/applications, limitations of existing work, and outline potential improvements.
InhaltA selection of research papers with a focus on foundations of parallel computing/programming.
LiteraturThe publications to be presented will be announced on the seminar home page at least one week before the first session.
Voraussetzungen / BesonderesPapers will be distributed in the first session.
Vertiefung in Theoretical Computer Science
Kernfächer der Vertiefung in Theoretical Computer Science
NummerTitelTypECTSUmfangDozierende
252-0407-00LCryptography Information W7 KP3V + 2U + 1AU. Maurer
KurzbeschreibungFundamentals and applications of cryptography. Cryptography as a mathematical discipline: reductions, constructive cryptography paradigm, security proofs. The discussed primitives include cryptographic functions, pseudo-randomness, symmetric encryption and authentication, public-key encryption, key agreement, and digital signature schemes. Selected cryptanalytic techniques.
LernzielThe goals are:
(1) understand the basic theoretical concepts and scientific thinking in cryptography;
(2) understand and apply some core cryptographic techniques and security proof methods;
(3) be prepared and motivated to access the scientific literature and attend specialized courses in cryptography.
InhaltSee course description.
Skriptyes.
Voraussetzungen / BesonderesFamiliarity with the basic cryptographic concepts as treated for
example in the course "Information Security" is required but can
in principle also be acquired in parallel to attending the course.
252-0491-00LSatisfiability of Boolean Formulas - Combinatorics and Algorithms Information W7 KP3V + 2U + 1AE. Welzl
KurzbeschreibungBasics (CNF, resolution), extremal properties (probabilistic method, derandomization, Local Lemma, partial satisfaction), 2-SAT algorithms (random walk, implication graph), NP-completeness (Cook-Levin), cube (facial structure, Kraft inequality, Hamming balls, covering codes), SAT algorithms (satisfiability coding lemma, Paturi-Pudlák-Zane, Hamming ball search, Schöning), constraint satisfaction.
LernzielStudying of advanced methods in algorithms design and analysis, and in discrete mathematics along a classical problem in theoretical computer science.
InhaltSatisfiability (SAT) is the problem of deciding whether a boolean formula in propositional logic has an assignment that evaluates to true. SAT occurs as a problem and is a tool in applications (e.g. Artificial Intelligence and circuit design) and it is considered a fundamental problem in theory, since many problems can be naturally reduced to it and it is the 'mother' of NP-complete problems. Therefore, it is widely investigated and has brought forward a rich body of methods and tools, both in theory and practice (including software packages tackling the problem).
This course concentrates on the theoretical aspects of the problem. We will treat basic combinatorial properties (employing the probabilistic method including a variant of the Lovasz Local Lemma), recall a proof of the Cook-Levin Theorem of the NP-completeness of SAT, discuss and analyze several deterministic and randomized algorithms and treat the threshold behavior of random formulas.
In order to set the methods encountered into a broader context, we will deviate to the more general set-up of constraint satisfaction and to the problem of proper k-coloring of graphs.
SkriptThere exists no book that covers the many facets of the topic. Lecture notes covering the material of the course will be distributed.
LiteraturHere is a list of books with material vaguely related to the course. They can be found in the textbook collection (Lehrbuchsammlung) of the Computer Science Library:

George Boole, An Investigation of the Laws of Thought on which are Founded the Mathematical Theories of Logic and Probabilities, Dover Publications (1854, reprinted 1973).
Peter Clote, Evangelos Kranakis, Boolean Functions and Computation Models, Texts in Theoretical Computer Science, An EATCS Series, Springer Verlag, Berlin (2002).
Nadia Creignou, Sanjeev Khanna, Madhu Sudhan, Complexity Classifications of Boolean Constrained Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Applications, SIAM (2001).
Harry R. Lewis, Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall (1998).
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, (1995).
Uwe Schöning, Logik für Informatiker, BI-Wissenschaftsverlag (1992).
Uwe Schöning, Algorithmik, Spektrum Akademischer Verlag, Heidelberg, Berlin (2001).
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston (1997).
Klaus Truemper, Design of Logic-based Intelligent Systems, Wiley-Interscience, John Wiley & Sons, Inc., Hoboken (2004).
Voraussetzungen / BesonderesLanguage: The course will be given in German if nobody expresses preference for English. All accompanying material (lecture notes, web-page, etc.) is supplied in English.
Prerequisites: The course assumes basic knowledge in propositional logic, probability theory and discrete mathematics, as it is supplied in the first two years of the Bachelor Studies at ETH.
Outlook: There will be a follow-up seminar, SAT, on the topic in the subsequent semester (attendance of this course will be a prerequisite for participation in the seminar). There are ample possibilities for theses of various types (Master-, etc.).
Wahlfächer der Vertiefung in Theoretical Computer Science
NummerTitelTypECTSUmfangDozierende
252-0408-00LCryptographic Protocols Information W5 KP2V + 2UU. Maurer, M. Hirt
KurzbeschreibungThe course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
LernzielIndroduction to a very active research area with many gems and paradoxical
results. Spark interest in fundamental problems.
InhaltThe course presents a selection of hot research topics in cryptography. The choice of topics varies and may include provable security, interactive proofs, zero-knowledge protocols, secret sharing, secure multi-party computation, e-voting, etc.
Skriptthe lecture notes are in German, but they are not required as the entire
course material is documented also in other course material (in english).
Voraussetzungen / BesonderesA basic understanding of fundamental cryptographic concepts
(as taught for example in the course Information Security or
in the course Cryptography) is useful, but not required.
252-1403-00LEinführung in die Quanteninformatik Information W3 KP2GS. Wolf
KurzbeschreibungNach einer Einführung wichtiger Grundbegriffe der Quantenphysik, wie etwa Überlagerung, Interferenz und Verschränkung, werden verschiedene Themen behandelt: Quantenalgorithmen, Teleportation, Quanten-Kommunikationskomplexität und "Pseudo-Telepathie", Quantenkryptographie sowie die Grundzüge der Quanten-Informationstheorie.
LernzielDas Ziel dieser Vorlesung ist es, mit den wichtigsten Begriffen vetraut zu werden,
welche fuer die Verbindung zwischen Information und Physik wichtig sind. Der Grundformalismus des Quantenphysik soll erarbeitet, und der Einsatz der entsprechenden Gesetze fuer die Informationsverarbeitung verstanden werden. Insbesondere sollen wichtige Algorithmen dargelegt und analysiert werden, wie der Grover- sowie der Shor-Algorithmus.
InhaltGemäss Landauer kann Information und ihre Verarbeitung nicht völlig losgelöst von der physikalischen Repräsentation betrachtet werden. Die Quanteninformatik befasst sich mit den Konsequenzen und Möglichkeiten der quantenphysikalischen Gesetze für die Informationsverarbeitung. Nach einer Einführung wichtiger Grundbegriffe der Quantenphysik, wie etwa Überlagerung, Interferenz und Verschränkung, werden verschiedene Themen behandelt: Quantenalgorithmen, Teleportation, Quanten-Kommunikationskomplexität und "Pseudo-Telepathie", Quantenkryptographie sowie die Grundzüge der Quanten-Informationstheorie.
252-1424-00LModels of Computation Information W6 KP2V + 2U + 1AM. Cook
KurzbeschreibungThis course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more.
Lernzielsee above
InhaltThis course surveys many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Graph Automata, Circuits, Tilings, Lambda Calculus, Fractran, Chemical Reaction Networks, Hopfield Networks, String Rewriting Systems, Tag Systems, Diophantine Equations, Register Machines, Primitive Recursive Functions, and more.
263-4100-00LRandomized Algorithms and Probabilistic Methods: Advanced Topics Information W5 KP2V + 1U + 1AJ. Lengler, K. Bringmann, T. S. Luria
KurzbeschreibungAdvanced introduction to random walks.
LernzielStudents will learn some advances techniques to analyze random walks, and they will see some examples of how algorithms make use of random walks. To successfully complete this course students need to be able to apply the acquired techniques and use random walks as a tool for designing algorithms.
InhaltThe lecture gives an advanced introduction to random walks. We treat methods to analyze them, and applications in which random walks are used. Some open problems will be discussed as well.
Topics:
- drift analysis
- rapidly mixing random walks
- random sampling and/or approximate counting e.g. of triangulations, latin squares
- expander graphs
- volume estimation of convex bodies
- differential equation method
Voraussetzungen / BesonderesRandomized Algorithms and Probabilistic Methods, or a similar course
401-3052-05LGraph Theory Information W5 KP2V + 1UB. Sudakov
KurzbeschreibungBasic notions, . Trees, spanning trees, Caley formula, Vertex and edge connectivity, blocks, 2-connectivity, Maders theorem, Mengers theorem,
Euleraing graphs, Hamilton cycle, Dirac theorem, Matchings, theorem of Hall, Konig, Tutte, Planar graph, Euler's formula, Basic non-planar graphs,
Graph colorings, greedy, brooks theorem, 5-colorings of planar graphs
LernzielThe students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems.
SkriptLecture will be only at the blackboard.
LiteraturWest, D.: "Introduction to Graph Theory"
Diestel, R.: "Graph Theory"

Further literature links will be provided in the lecture.
Voraussetzungen / BesonderesNOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms.
401-3903-11LGeometric Integer Programming Information W6 KP2V + 1UR. Weismantel
KurzbeschreibungInteger programming is the task of minimizing a linear function over all the integer points in a polyhedron. This lecture introduces the key concepts of an algorithmic theory for solving such problems.
LernzielThe purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
InhaltKey topics are:
- lattice theory and the polynomial time solvability of integer optimization problems in fixed dimension,
- the theory of integral generating sets and its connection to totally dual integral systems,
- finite cutting plane algorithms based on lattices and integral generating sets.
Skriptnot available, blackboard presentation
LiteraturBertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005.
Schrijver: Theory of linear and integer programming, Wiley, 1986.
Voraussetzungen / Besonderes"Mathematical Optimization" (401-3901-00L)
401-4904-00LCombinatorial Optimization Information W6 KP2V + 1UR. Zenklusen
KurzbeschreibungCombinatorial Optimization deals with efficiently finding a provably strong solution among a finite set of options. This course discusses key combinatorial structures and techniques to design efficient algorithms for combinatorial optimization problems. We put a strong emphasis on polyhedral methods, which proved to be a powerful and unifying tool throughout combinatorial optimization.
LernzielThe goal of this lecture is to get a thorough understanding of various modern combinatorial optimization techniques with an emphasis on polyhedral approaches. Students will learn a general toolbox to tackle a wide range of combinatorial optimization problems.
InhaltKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
SkriptNot available.
Literatur- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.
Voraussetzungen / BesonderesThis course builds upon "Mathematical Optimization" (401-3901-00L), which is a prerequisite for taking this lecture.
263-4205-00LPolynomials Information
Findet dieses Semester nicht statt.
W4 KP2V + 1UE. Welzl
KurzbeschreibungAlgebraic methods belong among the most powerful and succesful mathematical tools in computer science and discrete mathematics. The course covers a number of results, some of them fairly recent, whose proofs illustrate general techniques.
LernzielExtending the knowledge of mathematical methods that proved useful in recent research related to theoretical computer science. The students should understand several successful ideas of applying the properties of multivariate polynomials to various problems.
InhaltFrom the wide area of algebraic methods, we focus mainly on applications of polynomials, and we will encounter some of the elementary concepts of algebraic geometry. Here are some of the main themes: Dimension arguments using spaces of polynomials. Matchings and determinants. Randomized testing of polynomial identities. Space partitions using polynomials and geometric incidence theorems. "Contagious vanishing" arguments, geometry of lines in space.
SkriptOne part of the lecture will follow the book "Thirty-three miniatures" by J. Matousek. The rest will be based on recent research papers and on a book in preparation by Larry Guth.
LiteraturJ. Matousek: Thirty-three miniatures, Amer. Math. Soc. 2010
Seminar in Theoretical Computer Science
NummerTitelTypECTSUmfangDozierende
252-3002-00LAlgorithms for Database Systems Information W2 KP2SP. Widmayer, A. Khan
KurzbeschreibungQuery processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithms for database systems.
252-4102-00LSeminar on Randomized Algorithms and Probabilistic Methods Information W2 KP2SA. Steger
KurzbeschreibungThe aim of the seminar is to study papers which bring the students to the forefront of today's research topics. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA15).
LernzielRead papers from the forefront of today's research; learn how to give a scientific talk.
Voraussetzungen / BesonderesThe seminar is open for both students from mathematics and students from computer science. As prerequisite we require that you passed the course Randomized Algorithms and Probabilistic Methods (or equivalent, if you come from abroad).
252-4202-00LSeminar in Theoretical Computer Science Information W2 KP2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov
KurzbeschreibungPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
LernzielTo get an overview of current research in the areas covered by the involved research groups. To present results from the literature.
252-4302-00LSeminar Algorithmic Game Theory Information W2 KP2SP. Widmayer, M. Mihalak
KurzbeschreibungIn the seminar we will get familiar with the current original research in the area of algorithmic game theory by reading and presenting selected research papers in that area.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation.
InhaltStudy and understanding of selected topics of current interest in algorithmic game theory such as: Complexity Results (class PPAD, PLS, NP), Sponsored Search, Approximation Algorithms via Algorithmic Game Theory, Price of Anarchy, New paradigms of computation (e.g., envy-fee, truthful), Mechanism Design.
LiteraturSelected research articles.
Voraussetzungen / BesonderesYou must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases).
252-4800-00LQuantum Information and Cryptography Information W2 KP2SS. Wolf
KurzbeschreibungEs werden verschiedene Themen im Grenzgebiet der Bereiche Quantenphysik, Informationstheorie und Kryptographie behandelt.
LernzielThemen im Grenzgebiet der Bereiche Quantenphysik, Informationstheorie und Kryptographie werden behandelt.
263-4203-00LGeometry: Combinatorics and Algorithms Information W2 KP2SB. Gärtner, M. Hoffmann, E. Welzl
KurzbeschreibungThis seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.
LernzielEach student is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

* getting an overview of the related literature;
* understanding and working out the background/motivation:
why and where are the questions addressed relevant?
* understanding the contents of the paper in all details;
* selecting parts suitable for the presentation;
* presenting the selected parts in such a way that an audience
with some basic background in geometry and graph theory can easily understand and appreciate it.
Voraussetzungen / BesonderesTo attend the seminar, some knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" or a comparable course is strongly encouraged.
Vertiefung in Visual Computing
Kernfächer der Vertiefung in Visual Computing
Im FS15 wird keine Veranstaltung in dieser Kategorie angeboten.
Wahlfächer der Vertiefung in Visual Computing
NummerTitelTypECTSUmfangDozierende
252-0526-00LStatistical Learning Theory Information W4 KP2V + 1UJ. M. Buhmann
KurzbeschreibungThe course covers advanced methods of statistical learning :
PAC learning and statistical learning theory;variational methods and optimization, e.g., maximum entropy techniques, information bottleneck, deterministic and simulated annealing; clustering for vectorial, histogram and relational data; model selection; graphical models.
LernzielThe course surveys recent methods of statistical learning. The fundamentals of machine learning as presented in the course "Introduction to Machine Learning" are expanded and in particular, the theory of statistical learning is discussed.
Inhalt# Boosting: A state-of-the-art classification approach that is sometimes used as an alternative to SVMs in non-linear classification.
# Theory of estimators: How can we measure the quality of a statistical estimator? We already discussed bias and variance of estimators very briefly, but the interesting part is yet to come.
# Statistical learning theory: How can we measure the quality of a classifier? Can we give any guarantees for the prediction error?
# Variational methods and optimization: We consider optimization approaches for problems where the optimizer is a probability distribution. Concepts we will discuss in this context include:

* Maximum Entropy
* Information Bottleneck
* Deterministic Annealing

# Clustering: The problem of sorting data into groups without using training samples. This requires a definition of ``similarity'' between data points and adequate optimization procedures.
# Model selection: We have already discussed how to fit a model to a data set in ML I, which usually involved adjusting model parameters for a given type of model. Model selection refers to the question of how complex the chosen model should be. As we already know, simple and complex models both have advantages and drawbacks alike.
# Reinforcement learning: The problem of learning through interaction with an environment which changes. To achieve optimal behavior, we have to base decisions not only on the current state of the environment, but also on how we expect it to develop in the future.
Skriptno script; transparencies of the lectures will be made available.
LiteraturDuda, Hart, Stork: Pattern Classification, Wiley Interscience, 2000.

Hastie, Tibshirani, Friedman: The Elements of Statistical Learning, Springer, 2001.

L. Devroye, L. Gyorfi, and G. Lugosi: A probabilistic theory of pattern recognition. Springer, New York, 1996
Voraussetzungen / BesonderesRequirements:

basic knowledge of statistics, interest in statistical methods.

It is recommended that Introduction to Machine Learning (ML I) is taken first; but with a little extra effort Statistical Learning Theory can be followed without the introductory course.
252-0538-00LShape Modeling and Geometry Processing Information W4 KP2V + 1UO. Sorkine Hornung, D. Panozzo
KurzbeschreibungThis course covers some of the latest developments in geometric modeling and digital geometry processing. Topics include surface modeling based on triangle meshes, mesh generation, surface reconstruction, mesh fairing and simplification, discrete differential geometry and interactive shape editing.
LernzielThe students will learn how to design, program and analyze algorithms and systems for interactive 3D shape modeling and digital geometry processing.
InhaltRecent advances in 3D digital geometry processing have created a plenitude of novel concepts for the mathematical representation and interactive manipulation of geometric models. This course covers some of the latest developments in geometric modeling and digital geometry processing. Topics include surface modeling based on triangle meshes, mesh generation, surface reconstruction, mesh fairing and simplification, discrete differential geometry and interactive shape editing.
SkriptSlides and course notes
Voraussetzungen / BesonderesPrerequisites:
Introduction to Computer Graphics, experience with C++ programming. Some background in geometry or computational geometry is helpful, but not necessary.
252-0570-00LGame Programming Laboratory Information
Im Masterstudium können zusätzlich zu den Vertiefungsübergreifenden Fächern nur max. 10 Kreditpunkte über Laboratorien erarbeitet werden. Diese Labs gelten nur für das Masterstudium. Weitere Laboratorien werden auf dem Beiblatt aufgeführt.
W10 KP9PB. Sumner
KurzbeschreibungDas Ziel dieses Kurses ist ein vertieftes Verständnis der Technologie und der Programmierung von Computer-Spielen. Die Studierenden entwerfen und entwickeln in kleinen Gruppen ein Computer-Spiel und machen sich so vertraut mit der Kunst des Spiel-Programmierens.
LernzielDas Ziel dieses neuen Kurses ist es, die Studenten mit der Technologie und der Kunst des Programmierens von modernen dreidimensionalen Computerspielen vertraut zu machen.
InhaltDies ist ein neuer Kurs, der auf die Technologie von modernen dreidimensionalen Computerspielen eingeht. Während des Kurses werden die Studenten in kleinen Gruppen ein Computerspiel entwerfen und entwickeln. Der Schwerpunkt des Kurses wird auf technischen Aspekten der Spielentwicklung wie Rendering, Kinematographie, Interaktion, Physik, Animation und KI liegen. Zusätzlich werden wir aber auch Wert auf kreative Ideen für fortgeschrittenes Gameplay und visuelle Effekte legen.

Der Kurs wird als „Labor“ durchgeführt. Anstelle von traditionellen Vorträgen und Übungen wird der Kurs in einen praktischen, hands-on Ansatz durchgeführt. Wir treffen uns einmal wöchentlich um technische Aspekte zu besprechen und den Fortschritt der Entwicklung zu verfolgen. Wir planen das XNA Game Studio Express von Microsoft zu verwenden, eine Ansammlung von Bibliotheken und Werkzeugen um die Spieleentwicklung zu erleichtern. Die Entwicklung wird zunächst auf dem PC stattfinden, das Spiel wird dann im weiteren Verlauf auf der Xbox 360 Konsole eingesetzt.

Am Ende des Kurses werden die Resultate öffentlich präsentiert.
SkriptOnline XNA Dokumentation.
Voraussetzungen / BesonderesDie Anzahl der Teilnehmer wird begrenzt sein.

Voraussetzung für die Teilnahme sind:

- Gute Programmierkenntnisse (Java, C++, C#, o.ä.)

- Erfahrung in Computergrafik: Teilnehmer sollten mindestens die Vorlesung Visual Computing besucht haben. Wir empfehlen auch noch die weiterführenden Kurse Introduction to Computer Graphics, Surface Representations and Geometric Modeling, und Physically-based Simulation in Computer Graphics.
252-0579-00L3D Photography Information W4 KP3GM. Pollefeys, T. Sattler
KurzbeschreibungThe goal of this course is to provide students with a good understanding of how 3D object shape and appearance can be estimated from images and videos. The main concepts and techniques will be studied in depth and practical algorithms and approaches will be discussed and explored through the exercises and a course project.
LernzielAfter attending this course students should:
1. Understand the concepts that allow recovering 3D shape from images.
2. Have a good overview of the state of the art in 3D photography
3. Be able to critically analyze and asses current research in the area
4. Implement components of a 3D photography system.
InhaltThe course will cover the following topics a.o. camera model and calibration, single-view metrology, triangulation, epipolar and multi-view geometry, two-view and multi-view stereo, structured-light, feature tracking and matching, structure-from-motion, shape-from-silhouettes and 3D modeling and applications.
252-5705-00LImage Synthesis Information W6 KP5GW. Jarosz, W. A. Jakob
KurzbeschreibungThis course covers advanced topics in rendering and image synthesis.
LernzielThe goal is to get a broader knowledge of rendering algorithms and an in-depth understanding of advanced topics in rendering. Students will learn about the principles of how light interacts with a scene, and how to translate the associated image formation problem into efficient rendering algorithms. Since this is an upper-level coarse, a focus is placed on state of the art techniques and recent trends in research.
InhaltThis course expands upon the rendering foundation taught in the Computer Graphics course.

We assume a basic knowledge of ray tracing and shading, and expand significantly on the physics of light transport, discuss the rendering equation, and focus significant time on advanced techniques to enhance the realism and lower the computational cost of rendered images.

Starting from a review of the physics underlying a range of complex light transport effects (depth-of-field, soft shadows, global illumination, participating media, subsurface scattering), we discuss how to leverage various mathematical tools (e.g. density estimation, Monte Carlo sampling, Markov Chain Monte Carlo) to obtain a range of state-of-the-art rendering algorithms (including variants of path tracing, photon mapping, and Metropolis light transport).

The course includes a rendering competition where students create a realistic image of their choosing using the rendering software they develop in the course.
LiteraturStudents will read from the course text books, as well as rendering research papers.
Voraussetzungen / BesonderesCalculus and linear algebra, basic concepts of algorithms and data structures, programming skills in C++, Computer Graphics core course, Visual Computing core course
263-3700-00LUser Interface Engineering Information W4 KP2V + 1UO. Hilliges
KurzbeschreibungAn in-depth introduction to the core concepts of post-desktop user interface engineering. Current topics in UI research, in particular non-desktop based interaction, mobile device interaction, augmented and mixed reality, and advanced sensor and output technologies.
LernzielStudents will learn about fundamental aspects pertaining to the design and implementation of modern (non-desktop) user interfaces. Students will understand the basics of human cognition and capabilities as well as gain an overview of technologies for input and output of data. The core competency acquired through this course is a solid foundation in data-driven algorithms to process and interpret human input into computing systems. 

At the end of the course students should be able to understand and apply advanced hardware and software technologies to sense and interpret user input. Students will be able to develop systems that incorporate non-standard sensor and display technologies and will be able to apply data-driven algorithms in order to extract semantic meaning from raw sensor data.
InhaltUser Interface Engineering covers theoretical and practical aspects relating to the design and implementation of modern non-standard user interfaces. A particular area of interest are machine-learning based algorithms for input recognition in advanced non-desktop user interfaces, including UIs for mobile devices but also Augmented Reality UIs, gesture and multi-modal user interfaces. 

The course covers three main areas:
I) Basic principles of human cognition and perception (and their application for UIs)
II) (Hardware) technologies for user input sensing
III) Data-driven methods for input recognition (gestures, speech, etc.)

Specific topics include: 
* Model Human Processor (MHP) model - prediction of task completion times.
* Fitts' Law - measure of information load on human motor and cognitive system during user interaction.
* Touch sensor technologies (capacitive, resistive, force sensing etc).
* Data-driven algorithms for user input recognition:
- SVMs for classification and regression
- Randomized Decision Forests for gesture recognition and pose estimation
- Markov chains and HMMs for gesture and speech recognition
- Optical flow and other image processing and computer vision techniques
- Input filtering (Kalman)
* Applications of the above in HCI research
SkriptSlides and other materials will be available online. Lecture slides on a particular topic will typically not be made available prior the completion of that lecture.
LiteraturA detailed reading list will be made available on the course website.
Voraussetzungen / BesonderesPrerequisites: proficiency in a programming language such as C, programming methodology, problem analysis, program structure, etc. Normally met through an introductory course in programming in C, C++, Java.

The following courses are strongly recommended as prerequisite:
* "Human Computer Interaction"
* "Machine Learning"
* "Visual Computing" or "Computer Vision"

The course will be assessed by a written Midterm and Final examination in English. No course materials or electronic devices can be used during the examination. Note that the examination will be based on the contents of the lectures, the associated reading materials and the exercises.
252-5706-00LMathematical Foundations of Computer Graphics and Vision Information W4 KP2V + 1UJ.‑C. Bazin, C. Öztireli
KurzbeschreibungThis course presents the fundamental mathematical tools and concepts used in computer graphics and vision. Each theoretical topic is introduced in the context of practical vision or graphic problems, showcasing its importance in real-world applications.
LernzielThe main goal is to equip the students with the key mathematical tools necessary to understand state-of-the-art algorithms in vision and graphics. In addition to the theoretical part, the students will learn how to use these mathematical tools to solve a wide range of practical problems in visual computing. After successfully completing this course, the students will be able to apply these mathematical concepts and tools to practical industrial and academic projects in visual computing.
InhaltThe theory of each mathematical concept or tool will be introduced and we will then showcase their practical utility in a variety of different applications in computer graphics and vision. The course will cover topics in sampling, reconstruction, optimization, differentiation, quadrature and spectral methods. Applications will include 3D surface reconstruction, structure from motion, camera pose estimation, image editing, character animation, ray tracing, architectural design and shape recognition.
227-1034-00LComputational Vision Information W6 KP2V + 1UD. Kiper, K. A. Martin
KurzbeschreibungIn diesem Kurs studieren wir die neuronalen Prozesse, welche die visuelle Wahrnehmung unterstützen. Wir lernen, wie visuelle Signale in der Netzhaut, dem CGN und im visuellen Kortex vearbeitet werden. Wir studieren die Morphologie und funktionelle Architektur der visuellen neuralen Netzwerke, die für Wahrnehmung von Form, Farbe, Bewegung, und Dreidimensionalität verantwortlich sind.
LernzielThis course considers the operation of circuits in the process of neural computations. The evolution of neural systems will be considered to demonstrate how neural structures and mechanisms are optimised for energy capture, transduction, transmission and representation of information. Canonical brain circuits will be described as models for the analysis of sensory information. The concept of receptive fields will be introduced and their role in coding spatial and temporal information will be considered. The constraints of the bandwidth of neural channels and the mechanisms of normalization by neural circuits will be discussed.
The visual system will form the basis of case studies in the computation of form, depth, and motion. The role of multiple channels and collective computations for object recognition will
be considered. Coordinate transformations of space and time by cortical and subcortical mechanisms will be analysed. The means by which sensory and motor systems are integrated to allow for adaptive behaviour will be considered.
InhaltThis course considers the operation of circuits in the process of neural computations. The evolution of neural systems will be considered to demonstrate how neural structures and mechanisms are optimised for energy capture, transduction, transmission and representation of information. Canonical brain circuits will be described as models for the analysis of sensory information. The concept of receptive fields will be introduced and their role in coding spatial and temporal information will be considered. The constraints of the bandwidth of neural channels and the mechanisms of normalization by neural circuits will be discussed.
The visual system will form the basis of case studies in the computation of form, depth, and motion. The role of multiple channels and collective computations for object recognition will
be considered. Coordinate transformations of space and time by cortical and subcortical mechanisms will be analysed. The means by which sensory and motor systems are integrated to allow for adaptive behaviour will be considered.
263-5200-00LData Mining: Learning from Large Data Sets Information
Findet dieses Semester nicht statt.
The course will be offered again in the autumn semester 2015.
W4 KP2V + 1UA. Krause
KurzbeschreibungMany scientific and commercial applications require insights from massive, high-dimensional data sets. This courses introduces principled, state-of-the-art techniques from statistics, algorithms and discrete and convex optimization for learning from such large data sets. The course both covers theoretical foundations and practical applications.
LernzielMany scientific and commercial applications require us to obtain insights from massive, high-dimensional data sets. In this graduate-level course, we will study principled, state-of-the-art techniques from statistics, algorithms and discrete and convex optimization for learning from such large data sets. The course will both cover theoretical foundations and practical applications.
InhaltTopics covered:
- Dealing with large data (Data centers; Map-Reduce/Hadoop; Amazon Mechanical Turk)
- Fast nearest neighbor methods (Shingling, locality sensitive hashing)
- Online learning (Online optimization and regret minimization, online convex programming, applications to large-scale Support Vector Machines)
- Multi-armed bandits (exploration-exploitation tradeoffs, applications to online advertising and relevance feedback)
- Active learning (uncertainty sampling, pool-based methods, label complexity)
- Dimension reduction (random projections, nonlinear methods)
- Data streams (Sketches, coresets, applications to online clustering)
- Recommender systems
Voraussetzungen / BesonderesPrerequisites: Solid basic knowledge in statistics, algorithms and programming. Background in machine learning is helpful but not required.
Seminar in Visual Computing
NummerTitelTypECTSUmfangDozierende
252-5704-00LAdvanced Methods in Computer Graphics Information Belegung eingeschränkt - Details anzeigen
Maximale Teilnehmerzahl: 24
W2 KP2SM. Gross, O. Sorkine Hornung
KurzbeschreibungThis seminar covers advanced topics in computer graphics with a focus on the latest research results. Topics include modeling, rendering,
animation, physical simulation, computational photography, and others.
LernzielThe goal is to obtain an in-depth understanding of actual problems and
research topics in the field of computer graphics as well as improve
presentation and critical analysis skills.
Wahlfächer in der Informatik
Als Wahlfächer in der Informatik gelten alle angebotenen Kurse im Master-Studiengang des D-INFK.
NummerTitelTypECTSUmfangDozierende
252-0820-00LCase Studies from Practice Information W4 KP2V + 1UM. Brandis
KurzbeschreibungThe course is designed to provide students with an understanding of "real-life" challenges from business settings and teach them how to address these.
LernzielBy using case studies that are based on actual IT projects, students will learn how to deal with complex, not straightforward problems. It will help them to apply their theoretical Computer Science background in practice and will teach them fundamental principles of IT management and challenges with IT in practice.
InhaltThe course consists of multiple lectures about general IT management topics held by Marc Brandis and case studies provided by guest lecturers from either IT companies or IT departments of a diverse range of companies.
Presenting companies so far include Deloitte (how to develop innovative technology solutions for a luxury retailer), Selfnation (lessons learned from a startup company), Credit Suisse (investment banking case), HP (business continuity management), 28msec (product pricing in a software startup company), Open Web Technology (strategic choices in software development), and Marc Brandis Strategic Consulting (various).
263-0600-00LResearch in Computer Science Belegung eingeschränkt - Details anzeigen
Nur für MSc Informatik.
W5 KP11AProfessor/innen
KurzbeschreibungSelbständige Projektarbeit unter der Leitung eines Informatik-Professors / einer Informatik-Professorin.
LernzielProject done under supervision of a professor in the Department of Computer Science.
Voraussetzungen / BesonderesNur Studierende, die eine der folgenden Bedingungen erfüllen, können mit einem Research Projekt beginnen:
a) 1 Lab (Interfokus Kurs) und 1 Kernfokus Kurs
b) 2 Kernfokus Kurse
c) 2 Labs (Interfokus Kurse)

Eine Aufgabenbeschreibung muss zu Beginn des Projekts beim Studiensekretariat eingereicht werden.
272-0300-00LAlgorithmik für schwere Probleme Information
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik A n i c h t !
W4 KP2V + 1UJ. Hromkovic, H.‑J. Böckenhauer, D. Komm
KurzbeschreibungDiese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme.
Eine umfassende Reflexion über die Bedeutung der vorgestellten Ansätze für den Informatikunterricht an Gymnasien begleitet den Kurs.
LernzielAuf systematische Weise eine Übersicht über die Methoden zur Lösung schwerer Probleme kennen lernen.
InhaltZuerst wird der Begriff der Berechnungsschwere erläutert (für die Informatikstudierenden wiederholt). Dann werden die Methoden zur Lösung schwerer Probleme systematisch dargestellt. Bei jeder Algorithmenentwurfsmethode wird vermittelt, was sie uns garantiert und was sie nicht sichern kann und womit wir für die gewonnene Effizienz bezahlen.
SkriptUnterlagen und Folien werden zur Verfügung gestellt.
LiteraturJ. Hromkovic: Algorithmics for Hard Problems, Springer 2004.

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006.

F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010.
272-0302-00LApproximations- und Online-Algorithmen Information W4 KP2V + 1UH.‑J. Böckenhauer, D. Komm
KurzbeschreibungDiese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.
LernzielAuf systematische Weise einen Überblick über die verschiedenen Entwurfsmethoden von approximativen Verfahren für schwere Optimierungsprobleme und Online-Probleme zu gewinnen. Methoden kennenlernen, die Grenzen dieser Ansätze aufweisen.
InhaltApproximationsalgorithmen sind einer der erfolgreichsten Ansätze zur Behandlung schwerer Optimierungsprobleme. Dabei untersucht man die sogenannte Approximationsgüte, also das Verhältnis der Kosten einer berechneten Näherungslösung und der Kosten einer (nicht effizient berechenbaren) optimalen Lösung.
Bei einem Online-Problem ist nicht die gesamte Eingabe von Anfang an bekannt, sondern sie erscheint stückweise und für jeden Teil der Eingabe muss sofort ein entsprechender Teil der endgültigen Ausgabe produziert werden. Die Güte eines Algorithmus für ein Online-Problem misst man mit der competitive ratio, also dem Verhältnis der Kosten der berechneten Lösung und der Kosten einer optimalen Lösung, wie man sie berechnen könnte, wenn die gesamte Eingabe bekannt wäre.

Inhalt dieser Lerneinheit sind
- die Klassifizierung von Optimierungsproblemen nach der erreichbaren Approximationsgüte,
- systematische Methoden zum Entwurf von Approximationsalgorithmen (z. B. Greedy-Strategien, dynamische Programmierung, LP-Relaxierung),
- Methoden zum Nachweis der Nichtapproximierbarkeit,
- klassische Online-Probleme wie Paging oder Scheduling-Probleme und Algorithmen zu ihrer Lösung,
- randomisierte Online-Algorithmen,
- Entwurfs- und Analyseverfahren für Online-Algorithmen,
- Grenzen des "competitive ratio"- Modells und Advice-Komplexität als eine Möglichkeit, die Komplexität von Online-Problemen genauer zu messen.
LiteraturDie Vorlesung orientiert sich teilweise an folgenden Büchern:

J. Hromkovic: Algorithmics for Hard Problems, Springer, 2004

A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998

D. Komm: Advice and Randomization in Online Computation, 2012
401-3632-00LComputational Statistics Information W10 KP3V + 2UM. Mächler, P. L. Bühlmann
Kurzbeschreibung"Computational Statistics" deals with modern methods of data analysis (aka "data science") for prediction and inference. An overview of existing methodology is provided and also by the exercises, the student is taught to choose among possible models and about their algorithms and to validate them using graphical methods and simulation based approaches.
LernzielGetting to know modern methods of data analysis for prediction and inference.
Learn to choose among possible models and about their algorithms.
Validate them using graphical methods and simulation based approaches.
InhaltDas Schliessen von beobachteten Daten auf komplexe Modelle ist ein zentrales Thema der rechnerorientierten Statistik. Die Modelle sind oft unendlich-dimensional und die statistischen Verfahren deshalb Computer-intensiv.
Als Grundlage wird die klassische multiple Regression eingeführt. Danach werden einige nichtparametrische Verfahren für die Regression und die Klassifikation vorgestellt: Kernschätzer, glättende Splines, Regressions-/Klassifikationsbäume, additive Modelle, Projection Pursuit und evtl. Neuronale Netze, wobei einige davon gut interpretierbar und andere für genaue Prognosen geeignet sind. Insbesondere werden auch die Problematik des Fluchs der Dimension und die stochastische Regularisierung diskutiert. Nebst dem Anpassen eines (komplexen) Modells werden auch die Evaluation, Güte und Unsicherheit von Verfahren und Modellen anhand von Resampling, Bootstrap und Kreuz-Validierung behandelt.

In den Übungen wird mit dem Statistik-Paket R (http://www.R-project.org) gearbeitet. Es werden dabei auch praxis-bezogene Probleme bearbeitet.
Skriptlecture notes are available online; see
http://stat.ethz.ch/education/ (-> "Computational Statistics").
Literatur(see the link above, and the lecture notes)
Voraussetzungen / BesonderesBasic "applied" mathematical calculus and linear algebra.
At least one semester of (basic) probability and statistics.
272-0301-00LMethoden zum Entwurf von zufallsgesteuerten Algorithmen Information
Findet dieses Semester nicht statt.
Diese Lerneinheit beinhaltet die Mentorierte Arbeit Fachwissenschaftliche Vertiefung mit pädagogischem Fokus Informatik B n i c h t !
W4 KP2V + 1UJ. Hromkovic
KurzbeschreibungDie Studierenden sollen die Entwicklung unserer Vorstellung über Zufall und dessen Rolle verfolgen. Mit Grundkenntnissen der Wahrscheinlichkeitstheorie und grundlegender Arithmetik sollen sie entdecken, dass Zufallssteuerung ein Mittel zur Erreichung unglaublicher Effizienz von Prozessen werden kann. Das Ziel ist, die Methodik des Entwurfs von zufallsgesteuerten Algorithmen zu vermitteln.
LernzielThematische Schwerpunkte
- Modellierung und Klassifizierung von randomisierten Algorithmen
- Die Methode der Überlistung des Gegners: Hashing und randomisierte Online-Algorithmen
- Die Methode der Fingerabdrücke: Kommunikationsprotokolle
- Die Methode der häufigen Zeugen: randomisierter Primzahltest von Solovay und Strassen
- Wahrscheinlichkeitsverstärkung durch Wiederholung
- Randomisierte Algorithmen für Optimierungsprobleme
SkriptJ. Hromkovic: Randomisierte Algorithmen, Teubner 2004.

J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006.

J.Hromkovic: Algorithmics for Hard Problems, Springer 2004.
LiteraturJ. Hromkovic: Randomisierte Algorithmen, Teubner 2004.

J.Hromkovic: Design and Analysis of Randomized Algorithms. Springer 2006.

J.Hromkovic: Algorithmics for Hard Problems, Springer 2004.
Freie Wahlfächer
Den Studierenden steht das gesamte Lehrangebot auf Masterl Level der ETH Zürich, der EPF Lausanne und der Universität Zürich zur individuellen Auswahl offen. Lerneinheiten der übrigen Schweizer Universitäten können - nur nach vorgängiger Genehmigung durch den Studiendelegierten - ebenfalls gewählt werden.

Weitere Details entnehmen Sie bitte Art. 31 des Studienreglementes 2009 für den Master-Studiengang Informatik.
Industriepraktikum
NummerTitelTypECTSUmfangDozierende
252-0700-00LIndustriepraktikum Information Belegung eingeschränkt - Details anzeigen
Nur für MSc Informatik.
W0 KPexterne Veranstalter
KurzbeschreibungIndustriepraktikum in einem Informatikbetrieb, welcher vom Departement Informatik als Praktikumsfirma anerkannt ist. Mindestens 10 Wochen Vollzeitbeschäftigung.
LernzielDas Ziel der mindestens 10- wöchigen Praxis ist es, Studierenden die industriellen Arbeitsumgebungen näher zu bringen. Während dieser Zeit bietet sich ihnen die Gelegenheit, in aktuelle Projekte der Gastinstitution involviert zu werden.
Voraussetzungen / BesonderesVor Beginn des Industriepraktikums muss die Aufgabenstellung zur Bewilligung vorgelegt werden. Nach Abschluss wird eine Arbeitsbestätigung verlangt.
Pflichtwahlfach Geistes-, Sozial- und Staatswissenschaften
» siehe Studiengang GESS-Pflichtwahlfächer
Master-Arbeit
NummerTitelTypECTSUmfangDozierende
263-0800-00LMaster's Thesis Information Belegung eingeschränkt - Details anzeigen
Zur Master-Arbeit wird nur zugelassen, wer:
a. das Bachelor-Studium erfolgreich abgeschlossen hat;
b. allfällige Auflagen für die Zulassung zum Master-Studiengang erfüllt hat;
c. in der Kategorie "Vertiefungsübergreifende Fächer" sind 12 KP;
d. und in der Kategorie "Vertiefungsfächer" sind 26 KP erarbeitet.
O30 KP64DProfessor/innen
KurzbeschreibungSelbständige Bearbeitung eines Informatik-Projekts unter der Leitung eines/einer Informatik-Professors/-Professorin. Dauer: 6 Monate.
LernzielSelbständig, strukturiert und wissenschaftlich zu arbeiten unter der Leitung eines/einer Informatik Professors/Professorin.