Search result: Catalogue data in Autumn Semester 2016

Computer Science Teaching Diploma Information
More informations at : Link
Computer Science as First Subject
Additional Requirements (ETH-Masterstudents in PHYS/MATH/CSE)
Part 1
NumberTitleTypeECTSHoursLecturers
252-0057-00LTheoretical Computer Science Information O8 credits4V + 2U + 1AJ. Hromkovic
AbstractConcepts to cope with: a) what can be accomplished in a fully automated fashion (algorithmically solvable) b) How to measure the inherent difficulty of tasks (problems) c) What is randomness and how can it be useful? d) What is nondeterminism and what role does it play in CS? e) How to represent infinite objects by finite automata and grammars?
ObjectiveLearning the basic concepts of computer science along their historical development
ContentThis lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems.

The main topics of the lecture are:

- alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks
- finite automata, regular and context-free grammars
- Turing machines and computability
- complexity theory and NP-completeness
- design of algorithms for hard problems
Lecture notesThe lecture is covered in detail by the textbook "Theoretical Computer Science".
LiteratureBasic literature:

1. J. Hromkovic: Theoretische Informatik. 5th edition, Springer Vieweg 2014.

2. J. Hromkovic: Theoretical Computer Science. Springer 2004.

Further reading:

3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley 2006.
5. I. Wegener: Theoretische Informatik. Teubner.

More exercises and examples in:

6. A. Asteroth, Ch. Baier: Theoretische Informatik
Prerequisites / NoticeDuring the semester, two non-obligatory test exams will be offered.
252-0061-00LSystems Programming and Computer Architecture Information O8 credits4V + 2U + 1AT. Roscoe
AbstractIntroduction to computer architecture and system programming:

Instruction sets, storage hiearchies, runtime structures with an
emphasis on computers as engines for the execution of compiled
programs. Interaction between system software and the hardware.
Problems that arise from the final respresentation, performance
measurement and tuning, and program portability issues are covered.
ObjectiveThe objective is to allow students to understand all aspects of the
execution of compiled (C) programs on modern architectures -- the
instruction set, the storage resources (registers, stack, memory),
input/output, the impact of compiler decisions, and the interaction
between the operating system and hardware. Two main themes are
correctness issues (esp. those that arise from the finite
representation of data) and performance issues (incl. measurement and
tuning issues). The interface to the operating system is discussed to
prepare for subsequent classes on more advanced systems topics.

The two key goals are:

1) To equip students with a thorough understanding of how to
write correct programs that run fast on modern computer, and
2) How to write correct and efficient low-level systems code.

This course does not cover how to design or build a processor or
computer.
ContentThis course provides an overview of "computers" as a
platform for the execution of (compiled) computer programs. This
course provides a programmer's view of how computer systems execute
programs, store information, and communicate. The course introduces
the major computer architecture structures that have direct influence
on the execution of programs (processors with registers, caches, other
levels of the memory hierarchy, supervisor/kernel mode, and I/O
structures) and covers implementation and representation issues only
to the extend that they are necessary to understand the structure and
operation of a computer system.

The course attempts to expose students to the practical issues that
affect performance, portability, security, robustness, and
extensibility. This course provides a foundation for subsequent
courses on operating systems, networks, compilers and many other
courses that require an understanding of the system-level
issues. Topics covered include: machine-level code and its generation
by optimizing compilers, address translation, input and output,
trap/event handlers, performance evaluation and optimization (with a
focus on the practical aspects of data collection and analysis).
LiteratureThe course is based in part on "Computer Systems: A Programmer's Perspective" (2nd Edition) by R. Bryant and D. O'Hallaron, with some additional material.
Prerequisites / Notice252-0024-00L Parallel Programming,
252-0014-00L Digital Circuits
252-0026-00LAlgorithms and Data Structures Information O7 credits3V + 2U + 1AP. Widmayer, M. Püschel
AbstractThis course is about fundamental algorithm design paradigms, classic algorithmic problems, and data structures. The connection between algorithms and data structures is explained for geometric and graph problems. For this purpose, fundamental graph theoretic concepts are introduced.
ObjectiveAn understanding of the design and analysis of fundamental algorithms and data structures.
ContentEs werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt.
LiteratureTh. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
  •  Page  1  of  1