Search result: Catalogue data in Spring Semester 2009

Computer Science Master Information
Basic Courses and Electives
Electives
NumberTitleTypeECTSHoursLecturers
251-0222-00LCompiler Design IW6 credits2V + 2UT. Gross, F. T. Schneider
AbstractThis course uses compilers as example to expose modern software development techniques.
Compiler organization. Lexical analysis. Top-down parsing via recursive descent, table-driven parsers, bottom-up parsing. Symboltables, semantic checking. Code generation for a simple RISC machine: conditionals, loops, procedure calls, simple register allocation techniques.
ObjectiveLearn principles of compiler design, gain practical experience designing and implementing a medium-scale software system.
ContentThis course uses compilers as example to expose modern software development techniques. The course introduces the students to the fundamentals of compiler construction. Students will implement a simple yet complete compiler for an object-oriented programming language for a realistic target machine. Students will learn the use of appropriate tools (parser generators); the implementation language is Java. Throughout the course, students learn to apply their knowledge of theory (automata, grammars, stack machines, program transformation) and well-known programming techniques (module definitions, design patterns, frameworks, software reuse) in a software project.
Specific topics: Compiler organization. Lexical analysis. Top-down parsing via recursive descent, table-driven parsers, bottom-up parsing. Symboltables, semantic checking. Code generation for a simple RISC machine: expression evaluation, straight line code, conditionals, loops, procedure calls, simple register allocation techniques. Storage allocation on the stack, parameter passing, runtime storage management, heaps. Special topics as time permits: introduction to global dataflow and its application to register allocation, instruction scheduling.
LiteratureAho/Lam/Sethi/Ullmann, Compilers - Principles, Techniques, and Tools (2nd Edition)

Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997
Prerequisites / NoticePrerequisites:
Prior exposure to modern techniques for program construction, knowledge of at least one processor architecture at the assembly language level.
251-0268-00LConcurrent Programming 2: Concurrent Object-Oriented ProgrammingW5 credits2V + 1UB. Meyer
AbstractPresentation of advanced techniques of object-oriented programming in a concurrent environment, with a course project. See Web page for details.
ObjectiveThis course explores the application of object-oriented concepts to the programming of concurrent applications. It reviews a variety of approaches but particularly concentrates on the Eiffel SCOOP model and on .NET mechanisms of application domains and remoting. It covers applications to multithreading, distribution, Web services and real-time, as well as formal reasoning about concurrent systems.
ContentObject Technology has interesting potential applications to concurrency, distribution, real-time and Web services. In practice, a number of obstacles have prevented O-O techniques from repeating in the concurrent world the success they have now achieved in the sequential world. This course explores the connections between the object-oriented and concurrent programming paradigms, discussing the problems that arise in the process of attempting to merge them. It reviews the main existing approaches to concurrent O-O computation, including both widely used libraries for multi-threading in Java and .NET and more theoretical frameworks, with a particular emphasis on the SCOOP model. It also provides some of the formal background for discussing the correctness of concurrent O-O applications. A course project applies the ideas to a concrete example. Overview
- Concurrent and parallel programming
- Distributed programming
- Client-server programming
- Internet, Web Services
- Specific issues of embedded and real-time concurrency

Approaches to concurrent programming
- Notion of process, thread and application domain
- Message passing versus variable sharing
- Data consistency issues
- Enforcing synchronization: semaphores, monitors, barriers, etc.
- Java and .NET multithreading

Formal models of concurrency
- Computation versus observation
- Interesting properties of concurrent programs
- Concurrent calculi: CSP and Ada, CCS, the Pi-calculus, ...

Concurrency and Object-Orientation
- Language issues
- Processes versus objects
- Synchronizing objects

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
- Avoiding deadlock: The Business Card principle
- Interrupting a reservation: duels and priorities
- Mapping the processors to physical resources
- Examples and applications

Extensions and open problems
- Real-time and embedded extensions
- Timing contracts
- Proofs of SCOOP programs
Prerequisites / NoticePrerequisites:
It is strongly suggested to precede this course with the Winter Semester course "Prinzipien des Concurrent Programming" (Link)
251-0286-00LSystem ConstructionW5 credits2V + 1UJ. Gutknecht
AbstractThe lecture's goal is teaching of knowledge and skills needed for building custom operating systems and runtime environments. Relevant topics will be studied in detail at the example of sufficiently simple systems that have been built at the Institute in the past, ranging from purpose-oriented single processor real-time systems up to generic system kernels for Symmetric Multi Processors.
ObjectiveThe lecture's goal is teaching of knowledge and skills needed for building custom operating systems and runtime environments.
ContentThis lecture revives a tradition of the Computer Systems Institute. Its main goal is teaching of knowledge and skills needed for building custom operating systems and runtime environments. Relevant topics will be studied in detail at the example of sufficiently simple systems that have been built at the Institute in the past, ranging from purpose-oriented single processor real-time systems up to generic system kernels for SMPs (Symmetric Multi Processors). The lectuire intends to supplement more abstract views of software construction, and to contribute to a better understanding of "how it really works" behind the scenes.
251-0312-00LUbiquitous ComputingW4 credits2VF. Mattern
AbstractUbiquitous 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, Bluetooth, sensor networks, location awareness, application areas and business issues, privacy.
ObjectiveThe vision of ubiquitous computing, trends in technology, smart cards, RFID, Bluetooth, sensor networks, location awareness, application areas and business issues, privacy.
ContentUnter dem Begriff "Ubiquitous Computing" wird die Allgegenwärtigkeit von kleinsten, miteinander drahtlos vernetzten Computern verstanden, die unsichtbar in beliebige Alltagsgegenstände eingebaut werden oder an diese angeheftet werden können. Mit Sensoren ausgestattet, können sie die Umwelt des Gegenstandes erfassen oder diesen mit Informationsverarbeitungs- und Kommunikationsfähigkeiten ausstatten, was den Gegenständen eine neue, zusätzliche Qualität verleiht.
Die Visionen von "smart devices" und einer umfassenden Informatisierung und Vernetzung fast beliebiger Dinge des Alltages scheinen in den nächsten wenigen Jahren aus technischer Sicht tatsächlich realisierbar. Damit einher geht ein Paradigmenwechsel in den Informatik-Anwendungen: weg vom PC und dem Computer als Werkzeug, hin zum "computing without computers".
Die Vorlesung gibt einerseits einen Überblick über die relevanten Basistechnologien und Teilgebiete, geht andererseits aber auch auf speziellere Themen (z.B. location awareness, Privacy, Sicherheitsproblematik) ein. Unter anderem werden auch aktuelle Forschungsprojekte und Trends vorgestellt.
Lecture notesCopies of slides
LiteratureWird in der Vorlesung bekanntgegeben. Zur Einstimmung:
Mark Weiser: The Computer for the 21st Century. Scientific American, September 1991, pp. 94-104
251-0316-00LWeb Services and Service Oriented Architectures Restricted registration - show details W6 credits2V + 1U + 1PG. Alonso
AbstractThe course explores the architecture of large, distributed information systems from the point of view of "services" and "service oriented" languages and architectures. The course will cover the most important specifications, discuss their use in practice, and analyze the strengths and weaknesses of service orientation.
ObjectiveAt the end of the course, students will have gained a wider perspective on distributed information systems and the architecture of enterprise systems. The course focuses on practical aspects rather than on theoretical issues and emphasizes project work so that the students gain hands-on experience on modern tools and systems.
ContentService orientation is a new paradigm for building large software systems where the interfaces are defined using standard specifications and he interactions are loosely coupled. The course will focus on specifications such as SOAP, WSDL, UDDI, WS-Security, WS-Reliability, BPEL, REST as well as on the applications of these specifications in real use cases. The course has a strong project component and there will also be talks from industry to illustrate the practical relevance of the material covered in the course.
LiteratureReference text (available at the D-INFK library and the ETHZ library):

Web Services Concepts, Architectures and Applications
Gustavo Alonso, Fabio Casati, Harumi Kuno, Vijay Machiraju
Springer Verlag 2004
ISBN 3-540-44008-9
251-0374-00LWeb EngineeringW5 credits2V + 1UM. Norrie
AbstractStarting with basic technologies of Web Engineering, this course will introduce the necessary knowledge to develop dynamic web applications using scripting and programming languages. After an overview of common Web Engineering architectures, model-based approaches and CASE tools will be introduced. Finally, methodologies for context-aware web sites will be discussed.
ObjectiveThe course teaches students about the basic principles of web engineering by examining various tools, technologies and methodologies to support the systematic development of state-of-the-art web sites. Starting with the basic web technologies, the first part of the course builds on these in a step-by-step manner to arrive at the rich variety and mix of technologies in use today. This includes both clients and server-side technologies to support dynamic web content as well as support for access from a range of client devices. The second part of the course covers frameworks, tools and methods to support state-of-the-art web sites, showing how these build on the various technologies covered in the first half of the course.
ContentBasic Technologies (HTTP, HTML, CSS, XML), Dynamic Web Sites (CGI, JavaScript, PHP, Servlets), Web Architectures, Model-based Approaches (WebML, UWE, Hera), Context-aware Web Engineering (personalisation, internationalisation, mobile access)
Prerequisites / NoticeThis course is held in English.
251-0376-00LData WarehousesW5 credits2V + 1UD. Kossmann, C. Binnig
AbstractArchitecture of Data Warehouses, Data Models (e.g., star and snowflake schemas), SQL extensions (data cube, pivot tables, etc.), implementation techniques, query optimization, data mining, data cleaning, time series, continuous queries, systems, probabilistic databases.
Objective
251-0383-00LNetworked Information SystemsW6 credits2V + 1U + 1AN. Tatbul Bitim
AbstractThis course explores the fundamental concepts in design and implementation of networked information systems, with a special emphasis on issues related to data management. In addition to the classical topics of distributed information systems, we will also study modern applications involving the web, peer-to-peer systems, sensor networks, and data stream processing, to name a few.
ObjectiveThe purpose of this course is to teach students the fundamental concepts of distributed data management systems and their current application in various modern settings. The students will also gain some practical experience in building distributed data management applications through a programming project.
Prerequisites / NoticePrerequisite: 252-0060-00 Introduction to Database Systems, or similar basic knowledge.
251-0408-00LCryptographic ProtocolsW6 credits2V + 2UU. Maurer, M. Hirt
AbstractThe 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.
ObjectiveEinblick in ein hochaktuelles Forschungsgebiet mit vielen Rosinen und paradoxen Resultaten. Förderung der Freude an grundlegenden Fragestellungen.
ContentDiese Vorlesung gibt einen genauen Einblick in hochaktuelle Themen des Forschungsgebiets Kryptographie. Die Themenwahl richtet sich nach den neusten Entwicklungen. Mögliche Themen sind beweisbar sichere Verschlüsselung, Secret Sharing, interaktive Beweise, Zero-kowledge Protokolle, sichere Multi-Party Berechnungen, digitale Abstimmungen, etc.
Lecture notesja
Prerequisites / NoticeHilfreich für das Verständnis der Vorlesung sind Grundlagenkenntnisse in Kryptographie (z.B. von den Lehrveranstaltungen Information Security und/oder Cryptography).
251-0466-00LE-Privacy: Privacy in the Electronic SocietyW5 credits2V + 1UG. Karjoth, J. Camenisch
AbstractThis course provides an in-depth look into privacy laws and regulations as well as into technologies for achieving privacy in an electronic world.
Objective
ContentPrivacy issues have been the subject of public debates since years. In particular, as new technologies are developed, they increasingly raise privacy concerns - the World Wide Web, wireless location-based services, and RFID chips are just a few examples. Thus, the need for privacy-aware policies, regulations, and techniques has been widely recognized by law makers, regulators, and the media. As a result, businesses are under pressure to draft privacy policies, chief privacy officers are becoming essential members of many organizations, and companies are taking pro-active steps to avoid the potential reputation damage of a privacy mistake.This course provides an in-depth look into privacy laws and regulations as well as into technologies for achieving privacy in an electronic world.
Prerequisites / NoticeBasic knowledge of cryptology is recommended to follow some of the topics of this course.
251-0470-00LSecurity and Fault-Tolerance in Distributed SystemsW5 credits2V + 1UC. Cachin
AbstractMethods for building dependable and secure distributed systems. Focus on fault-tolerant, distributed and cryptographic protocols; group communication, reliable broadcast, distributed cryptosystems, Byzantine agreement, resilient services, and secure storage systems.
ObjectiveThe course presents principles and fundamental methods, and shows how they are applied to real-world systems.
ContentTentative List of Topics

1. Introduction
2. Dependability Concepts
3. Quorums
4. Registers and Shared Memory
5. Consensus and Broadcast
6. View-synchronous Group Communication
7. Distributed Cryptography
8. Byzantine Agreement
9. Service Replication
10. Data Storage
251-1408-00LGraphs and AlgorithmsW6 credits2V + 1U + 1AA. Steger, D. Hefetz
AbstractConnectivity (block decomposition, Menger), Matching for bipartite graphs (Hall, König, Hopcroft-Karp algorithm, Hungarian method), Hamilton cycles (Dirac), Planar graphs (Euler’s formula, 5-coloring, planarity testing (in quadratic time)), Graph Coloring (Greedy, Brooks, Vizing, Hadwiger’s conjecture), Extremal Graph Theory (Ramsey, Turan)
Objective
251-1414-00LSystem SecurityW6 credits2V + 2US. Capkun, G. Caronni, N. Weiler
AbstractThe first part of the lecture covers individual system's aspects starting with tamperproof or tamperresistant hardware in general over operating system related security mechanisms to application software systems, such as host based intrusion detection systems. In the second part, the focus is on system design and methodologies for large projects.
ObjectiveIn this lecture, students learn about the security requirements and capabilities that are expected from modern hardware, operating systems and other software environments. An overview of available technologies, algorithms and standards is given, with which these requirements can be met.
ContentThe first part of the lecture covers individual system's aspects starting with tamperproof or tamperresistant hardware in general over operating system related security mechanisms to application software systems such as host based intrusion detetction systems. The main topics covered are: tamper resistant hardware, CPU support for security, protection mechanisms in the kernel, file system security (permissions / ACLs / network filesystem issues), IPC Security, mechanisms in more modern OS, such as Capabilities and Zones, Libraries and Software tools for security assurance, etc.

In the second part, the focus is on system design and methodologies for large projects. The main question answered is how to get a large secure system. Topics include: patch management, common software faults (buffer overflows, etc.), writing secure software (design, architecture, QA, testing), compiler-supported security, langauge-supported security (java...), logging and auditing (BSM audit, dtrace, ...), cryptographic support, TCG, secure file systems, dos/windows/ windowsXP security issues.

Along the lectures, model cases will be elaborated and evaluated in the exercises.
251-1424-00LModels of ComputationW6 credits2V + 1U + 1AM. Cook
AbstractThis course will survey many different models of computation: Turing Machines, Cellular Automata, Finite State Machines, Stack Machines, Graph Automata, Lambda Calculus, Fractran, Tiling Systems, Chemical Reaction Systems, Hopfield Networks, Boltzmann Machines, Neural Networks, Circuits, Graphical Models, Boolean Algebra, String Rewriting Systems, Semigroups, Quantum Waves, etc.
Objective
251-1426-00LApproximation Algorithms and Semidefinite ProgrammingW8 credits3V + 2UB. Gärtner, J. Matousek
AbstractOver the last fifteen years, semidefinite programming has become an important tool for approximate solutions of hard combinatorial problems. In this lecture, we introduce the foundations of semidefinite programming, and we present some of its applications in (but not only in) approximation algorithms.
Objective
251-0526-00LStatistical Learning TheoryW5 credits2V + 1UJ. M. Buhmann
AbstractThe 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.
ObjectiveThe 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.
Content# 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.
Lecture notesno script; transparencies of the lectures will be made available.
LiteratureDuda, 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
Prerequisites / NoticeRequirements:

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 Advanced Topics in Machine Learning can be followed without the introductory course.
251-0532-00LBio-Inspired Optimization and DesignW5 credits2V + 1UE. Zitzler, P. Koumoutsakos
AbstractThis lecture focuses on the foundations of bio-inspired optimization. The exercises will be oriented towards the implementation of these concepts to design applications.
ObjectiveYou are familiar with the foundations of optimization and with different randomized search algorithms, in particular bio-inspired ones.

You will be able to design, implement, and tune basic and advanced bio-inspired optimization techniques for tackling complex, large-scale applications.

You will be able to evaluate different search algorithms and implementations.

You are aware of the theoretical foundations of bio-inspired optimization, know the limitations as well as potential advantages and disadvantages of specific design concepts.
ContentBiologically-inspired computation is an umbrella term for different
computational approaches that are based on principles or models of
biological systems. This class of methods such as evolutionary algorithms,
ant colony optimization, and swarm intelligence complements traditional
techniques in the sense that the former can be applied to large-scale
applications where little is known about the underlying problem and
where the latter approaches encounter difficulties. Therefore, bio-inspired
methods are becoming increasingly important in face of the complexity of
today's demanding applications, and accordingly they have been successfully
used in various fields ranging from computer engineering and mechanical
engineering to chemical engineering and molecular biology.

This lecture focuses on the foundations of bio-inspired computation
with an emphasis on their application to optimization. The exercises will be
oriented towards the implementation of these concepts to realistic applications.
Lecture notesLecture notes will be provided in the course of the semester.
251-0538-00LSurface Representations and Geometric ModelingW5 credits2V + 1UM. Pauly
AbstractThis course covers some of the latest developments in geometric modeling and surface representations. Topics include surface modeling based on triangle meshes, mesh generation, subdivision schemes, mesh fairing and simplification, multiresolution methods, and interactive shape editing.
ObjectiveIntroduction to geometric modeling and digital surface processing. The exercises will complement the course material with implementations of the main processing algorithms.
ContentRecent 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 surface representations. Topics include surface modeling based on triangle meshes, mesh generation, subdivision schemes, mesh fairing and simplification, multiresolution methods, and interactive shape editing.
Lecture notesslides and course notes
Prerequisites / NoticePrerequisites:
Introduction to Computer Graphics, experience with C++ programming. Some background in geometry or computational geometry is helpful, but not necessary.
251-0548-00LSoftware for Numerical Linear AlgebraW6 credits2V + 2U
AbstractThis is an advanced class for people who already have knowledge about algorithms of numerical lineare algebra and now wonder about subtle details that make a difference in practice. Typically, a student attended graduate classes on numerical analysis such as "Large Scale Eigenvalue Methods" and "Sparse Linear Systems Solving."
ObjectiveThe aim of this course is to show how numerical algorithms are implemented correctly and efficiently.
We follow this agenda by discussing various important algorithms of numerical linear algebra.
ContentExamples, mainly from numerical linear algebra are used to show how algorithms are implemented
correctly and efficiently in floating-point arithmetic.
In the first part, the exact computation of eigenvalues and eigenvectors, as well as singular values and
singular vectors of dense matrices is discussed. In the second part, sparse matrices are treated first.
Then we present an introduction to iterative methods for large sparse matrix eigenvalue problems
and systems of linear equations. In particular the eigensolver package ARPACK amd the implementation
of the well-known methods CG, MinRes, and GMRes is discussed. Finally, in the third part, parallel
algorithms are treated.
The course is given in German unless there are requests to use English.
Lecture notesScripts or notes on the various parts will be provided.
LiteratureBackground information:

[1] C. D. Meyer: Matrix Analysis and Applied Linear Algebra

Theory:

[1] A. J. Laub: Matrix Analysis for Scientists and Engineers, SIAM 2004

[2] N. J. Higham: Accuracy and Stability of Numerical Algorithms, SIAM 2002

[3] G. Dahlquist and A. Bjorck: Numerical Methods in Scientific Computing, SIAM 2008

[4] F. Chaitin-Chatelin & V. Fraysse:
"Lectures on Finite Precision Computations", SIAM 1996

Algorithms:

[1] L. Komzsik:
"The Lanczos Method: Evolution and Application", SIAM 2003

[2] Y. Saad:
"Iterative Methods for Sparse Linear Systems", SIAM 2003

[3] T. Davis:
"Direct Methods for Sparse Linear Sysyems", SIAM 2006

[4] I. Duff, A. Erisman, J. Reid:
"Direct Methods for Sparse Matrices", Oxford UP 1986

[5] Z. Bai et al:
"Templates for the Solution of Algebraic Eigenvalue Problems", SIAM 2000

[6] S. Goedecker & A. Hoisie:
"Performance Optimization of Numerically Intensive Codes", SIAM 2001
Prerequisites / NoticeFinal exam at end of semester.
251-0564-00LScientific VisualizationW5 credits2V + 1UR. Peikert
AbstractScientific visualization is the application of computer graphics to the visual analysis and interactive exploration of scientific data which have typically spatial or spatio-temporal domain. Such datasets arise in engineering, natural and medical sciences, and are generated by simulation, measurement or imaging techniques.
ObjectiveBecoming familiar with the fundamental methods and some advanced techniques of scientific visualization. Being able to apply visualization to measurement or simulation data and to correctly interpret visualization results.
ContentThis course covers advanced topics in Scientific Visualization, including: contouring and isosurfaces, direct volume rendering, visualization of flow and vector fields, texture advection, feature extraction, topological methods, information visualization, visualization software, and hot topics of current research.
  •  Page  1  of  3 Next page Last page     All