Declarative Programming (DP) is an approach that makes it possible to write concise and at the same time very efficient programs. This paradigm is becoming more and more important as declarative programs are much easier to execute in parallel, on multi-core computers or distributed computer networks, than traditional imperative programs. The two main branches of DP are logic and functional programming, with LISP and Prolog as the representative programming languages.
The course gives an introduction to logic programming and Prolog using both lectures and hands-on lab sessions. No knowledge of other programming languages is required. The course also explores constraint logic programming, an extension of Prolog for efficiently solving specific problem classes. We use puzzles, such as Sudoku, as motivating examples; we show how to develop both puzzle solvers and puzzle generators. The course concludes with an outlook on the practice of declarative programming in general: languages, implementations and applications.
Proposed literature: Clocksin, W.F., Mellish, C.S.: Programming in Prolog using the ISO standard, Springer Verlag, 2003.
Peter Szeredi (born 1949) is an Associate Professor at the Budapest University of Technology and Economics. Between 1972 and 2003, he worked for several software R&D companies in Hungary. In the mid 1970s he authored the first Hungarian Prolog interpreter, and led the development of the MProlog system, a pioneering Hungarian software product sold worldwide in the 1980s. He worked as a research fellow at UK universities (Manchester and Bristol, 1987-1990) and at the Swedish Institute of Computer Science (1998-1999). His main research fields are semantic technologies, as well as logic and constraint programming. He edited and co-authored a textbook on the Semantic Web to be published by Cambridge University Press. He is the author or co-author of about 90 peer-reviewed publications, including 14 books and book chapters. He is the Chair of the Special Interest Group on Artificial Intelligence of the John von Neumann Computer Society. He received several academic awards and is among the 15 researchers recognized by the Association of Logic Programming as "Founders of the field of Logic Programming".
Graphs are fairly general structures that often come up naturally in everyday problems and, in particular, in problems of information technology. We believe that the best strategy for developing an ability to recognize and handle these problems successfully is to study graph theory for its own sake as a branch of pure mathematics. This course offers a fast introduction to the basic concepts of graph theory as well as a more detailed discussion of some of its classical topics. No prior knowledge of graph theory is needed, but some basic mathematical maturity is expected for this course.
Proposed literature: R. Diestel, Graph Theory, 3rd Edition, Springer-Verlag, Heidelberg, 2005. or Béla Bollobás, Modern Graph Theory, Springer-Verlag, Heidelberg, Corr. 2nd printing 2002. Additional useful reading: M. Aigner, G. Ziegler, Proofs from the Book, Springer-Verlag, Heidelberg, 1998.
Gábor Simonyi (born 1963) is a research fellow at the Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences and a part-time professor at the Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics. As a high school student he won a gold medal at the International Mathematical Olympiad in 1981. As an undergraduate he studied electrical engineering and he received his Ph.D. in mathematics in 1991 from the Hungarian Academy of Sciences. Simonyi spent a year at Rutgers University as a DIMACS postdoc in 1992-93 and has also had visiting appointments in Canada, France, Germany and Italy. He is the author of more than 30 papers and a chapter of the book "Perfect Graphs" published by John Wiley and Sons in 2001. In 1998-2001 he served as managing editor of the international journal Combinatorica. He has been teaching graph theory at the Budapest Semesters of Mathematics for several years. His Erdős number is 2.
Combinatorial optimization is the art and science of finding the best solution out of a large but finite set of possible solutions. While in most practical applications scanning through all cases is only a theoretical possibility due to the enormous number of them, combinatorial optimization offers more sophisticated methods and algorithms resulting in reasonable running times. One of the most powerful tools of combinatorial optimization is linear and integer programming; this is a general framework capable of modeling and efficiently solving many problems arising in real-life applications. The objective of this course is to get acquainted with the basic notions and methods of this theory and use it for various applications.
Dávid Szeszlér (born 1975) is an associate professor of the Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics (BME). In 1997 he was awarded as "Excellent Teacher of the Department", based on student feedback surveys. He graduated from Eötvös Loránd University as a mathematics teacher and English language technical translator in 1998. He obtained his Ph.D. in the field of VLSI routing in 2005; in the same year, he was awarded the "Farkas Gyula prize" of the János Bolyai Mathematical Society for applications of mathematics. His Erdős number is 3.
The first important question that we answer in this course is: Is there an algorithm for any problem? If there is an algorithm, can we implement it by a given computational model? It turns out that there are some interesting problems that seem to be much more difficult than others. Another question addressed in the course is what happens if we have limited resources. Time and space are limited for computation in real life.
Scientists over centuries have tried to solve some difficult algorithmic problems, but sometimes they fail. Is it the case that they are not clever enough? Or is there no algorithm at all? Is there something in between these two possibilities?
If we wish to answer these questions, we should have a theoretical model for computing. In the beginning of the course we introduce the most important model, the Turing machine, which is considered to be the model of an everyday computer. Then we study various complexity classes, with special emphasis on polynomially solvable and on NP-complete problems.
Proposed literature: Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology, 2006
Gyula Y. Katona (born 1965) is an associate professor of the Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics (BME). He graduated from the Eötvös Loránd University as a mathematician in 1991. Receiving his Ph.D. in mathematics in 1997 from the Hungarian Academy of Sciences, Katona spent two years at Ibaraki University, Japan. He also had a visiting appointment for a year at Arizona State University. He is the author of more than 25 papers and a co-author of a university textbook on discrete mathematics. He has been teaching Theory of Computing at the Budapest Semesters of Mathematics for several years. His Erdős number is 2.
