# Suchergebnis: Katalogdaten im Frühjahrssemester 2015

Informatik Master | ||||||

Vertiefungsfächer | ||||||

Vertiefung in Information Systems | ||||||

Kernfächer der Vertiefung in Information Systems | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |
---|---|---|---|---|---|---|

252-0374-00L | Web Engineering | W | 6 KP | 2V + 2U + 1A | M. Norrie | |

Kurzbeschreibung | The 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. | |||||

Lernziel | The 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 | |||||

Inhalt | The 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 | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

252-0312-00L | Ubiquitous Computing | W | 3 KP | 2V | F. Mattern | |

Kurzbeschreibung | Ubiquitous 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. | |||||

Lernziel | 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. | |||||

Skript | Copies of slides will be made available | |||||

Literatur | Will 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-00L | Object Databases | W | 4 KP | 2V + 1U | A. K. de Spindler | |

Kurzbeschreibung | The 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. | |||||

Lernziel | The 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. | |||||

Inhalt | The 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 / Besonderes | Prerequisites: Knowledge about the topics of the lectures "Introduction to Databases" and "Information Systems" is required. | |||||

252-0807-00L | Information Systems Laboratory 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. | W | 10 KP | 9P | M. Norrie | |

Kurzbeschreibung | The 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. | |||||

Lernziel | The students will gain experience of working with technologies used in the design and development of information systems. | |||||

Inhalt | First 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-00L | Introduction to Natural Language Processing | W | 4 KP | 2V + 1U | E. Alfonseca Cubero, M. Ciaramita | |

Kurzbeschreibung | This 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. | |||||

Lernziel | The 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. | |||||

Inhalt | This 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. | |||||

Literatur | Lectures will be presented from the Jurafsky and Martin text accompanied by related technical papers where necessary. | |||||

263-5200-00L | Data Mining: Learning from Large Data Sets Findet dieses Semester nicht statt. The course will be offered again in the autumn semester 2015. | W | 4 KP | 2V + 1U | A. Krause | |

Kurzbeschreibung | Many 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. | |||||

Lernziel | Many 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. | |||||

Inhalt | Topics 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 / Besonderes | Prerequisites: Solid basic knowledge in statistics, algorithms and programming. Background in machine learning is helpful but not required. | |||||

Seminar in Information Systems | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

252-3002-00L | Algorithms for Database Systems | W | 2 KP | 2S | P. Widmayer, A. Khan | |

Kurzbeschreibung | Query processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases. | |||||

Lernziel | Develop an understanding of selected problems of current interest in the area of algorithms for database systems. | |||||

252-3100-00L | Computer Supported Cooperative Work Maximale Teilnehmerzahl: 18 | W | 2 KP | 2S | M. Norrie | |

Kurzbeschreibung | Im 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. | |||||

Lernziel | see 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 | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

252-0268-00L | Concepts of Concurrent Computation | W | 7 KP | 3V + 2U + 1A | S. Nanz | |

Kurzbeschreibung | Concurrent 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. | |||||

Lernziel | After 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. | |||||

Inhalt | Topics 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 / Besonderes | The 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-00L | How To Write Fast Numerical Code Prerequisite: Master student, solid C programming skills. | W | 6 KP | 3V + 2U | M. Püschel | |

Kurzbeschreibung | This 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. | |||||

Lernziel | Software 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. | |||||

Inhalt | The 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-00L | Advanced Compiler Design | W | 7 KP | 3V + 2U + 1A | T. Gross | |

Kurzbeschreibung | This 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. | |||||

Lernziel | Understand 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) | |||||

Inhalt | This 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. | |||||

Literatur | Aho/Lam/Sethi/Ullmann, Compilers - Principles, Techniques, and Tools (2nd Edition). In addition, papers as provided in the class. | |||||

Voraussetzungen / Besonderes | A 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-00L | Program Analysis | W | 4 KP | 2V + 1U | M. Vechev | |

Kurzbeschreibung | Modern 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. | |||||

Lernziel | The 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. | |||||

Inhalt | The 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. | |||||

Skript | The lectures notes will be distributed in class. | |||||

Literatur | Distributed in class. | |||||

Voraussetzungen / Besonderes | This course is aimed at both graduate (M.Sc., PhD) students as well as advanced undergraduate students. | |||||

252-0284-00L | Java and C # in depth Findet dieses Semester nicht statt. | W | 5 KP | 2V + 1U + 1A | Noch nicht bekannt | |

Kurzbeschreibung | Java 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. | |||||

Lernziel | This 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. | |||||

Inhalt | Introduction, 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 / Besonderes | The 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-00L | System Construction Findet dieses Semester nicht statt. The course will be offered again in the autumn semester 2015. | W | 4 KP | 2V + 1U | keine Angaben | |

Kurzbeschreibung | Main 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. | |||||

Lernziel | The 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. | |||||

Inhalt | Case 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 | |||||

Skript | Printed lecture notes will be delivered during the lecture. Slides will also be available from the lecture homepage. | |||||

Seminar in Software Engineering | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

263-2100-00L | Research Topics in Software Engineering Maximale Teilnehmerzahl: 22 | W | 2 KP | 2S | T. Hoefler | |

Kurzbeschreibung | This 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. | |||||

Lernziel | At 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. | |||||

Inhalt | A selection of research papers with a focus on foundations of parallel computing/programming. | |||||

Literatur | The publications to be presented will be announced on the seminar home page at least one week before the first session. | |||||

Voraussetzungen / Besonderes | Papers will be distributed in the first session. | |||||

Vertiefung in Theoretical Computer Science | ||||||

Kernfächer der Vertiefung in Theoretical Computer Science | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

252-0407-00L | Cryptography | W | 7 KP | 3V + 2U + 1A | U. Maurer | |

Kurzbeschreibung | Fundamentals 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. | |||||

Lernziel | The 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. | |||||

Inhalt | See course description. | |||||

Skript | yes. | |||||

Voraussetzungen / Besonderes | Familiarity 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-00L | Satisfiability of Boolean Formulas - Combinatorics and Algorithms | W | 7 KP | 3V + 2U + 1A | E. Welzl | |

Kurzbeschreibung | Basics (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. | |||||

Lernziel | Studying of advanced methods in algorithms design and analysis, and in discrete mathematics along a classical problem in theoretical computer science. | |||||

Inhalt | Satisfiability (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. | |||||

Skript | There exists no book that covers the many facets of the topic. Lecture notes covering the material of the course will be distributed. | |||||

Literatur | Here 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 / Besonderes | Language: 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 | ||||||

Nummer | Titel | Typ | ECTS | Umfang | Dozierende | |

252-0408-00L | Cryptographic Protocols | W | 5 KP | 2V + 2U | U. Maurer, M. Hirt | |

Kurzbeschreibung | The 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. | |||||

Lernziel | Indroduction to a very active research area with many gems and paradoxical results. Spark interest in fundamental problems. | |||||

Inhalt | The 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. | |||||

Skript | the 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 / Besonderes | A 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-00L | Einführung in die Quanteninformatik | W | 3 KP | 2G | S. Wolf | |

Kurzbeschreibung | 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. | |||||

Lernziel | Das 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. | |||||

Inhalt | Gemä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-00L | Models of Computation | W | 6 KP | 2V + 2U + 1A | M. Cook | |

Kurzbeschreibung | This 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. | |||||

Lernziel | see above | |||||

Inhalt | This 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. |

- Seite 2 von 4 Alle