this
is a summer course on fundamentals of formal methods and proof technologies in the proof assistant PVS.
foils and
exercises for the short course at ITIV.
Computational
Complexity and Computability (Complexidade Computacional e Computabilidade):
Offered by the Graduate Program of the Departamento de Matemática, First Semester 2010
(Prof. Mauricio Ayala Rincón)
this is a semester course
for mathematics and computer science graduate students on foundations of theory of complexity: the study of why some problems are so hard to solve by computers and, in general, the classification of problems with respect to the necessary computational resources of its solutions. Turing Machines are reviewed introducing the classic computational complexity
classes according to the use of computational (time/space) resources. Relations
between computational complexity classes are studied from the structural
point of view. NP-complete and PSPACE-complete problems are
examined. Also, probabilistic algorithms, that result from approximate solution for intratable problems, as well as the corresponding probabilistic classes are considered.
Bibliography:
- S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
- S. Homer and A. L. Selman, Computability and Complexity Theory, Texts in Computer Science, Springer, 2001.
- D.P. Bovet and P. Crescenzi, Introduction
to the Theory of Complexity, C.A.R. Hoare Series Editor. Prentice-Hall,
1994.
- J.L. Balcázar and J. Díaz and J. Gabarró,
Structural Complexity I, EATCS monographs on Theoretical Computer
Science. Springer, econd edition, 1995.
- C.H. Papadimitriou, Computational Complexity,
Addison-Wesley Publishing Company, 1994.
Details
of the last program of the course, second semester 2005 (in Portuguese) (postscript) (PDF)
Analysis of Algorithms
(Análise de Algoritmos)
Offered by the Undergraduate Program of the Departamento de Matemática, First Semester 2009
(Prof. Mauricio Ayala Rincón)
this
is a semester course for mathematic and computer science undergraduate
students on design and analysis of computer algorithms. Regularly, simple
computer data structures and a collection of efficient algorithms for classical
computer science problems, such as sorting, searching, string pattern matching,
graph theory problems, mathematical problems, etc. are studied. Also, basic
computer programming techniques are presented: divide and conquer, dynamic
programming, etc. The course includes a brief introduction on algorithmic
complexity classes and parallel models of computation.
Didactic material of the course, semester 2009/I
Introduction to Formal Logic (313998 Introdução à Lógica Formal)
Offered by the Graduate Program of the Departamento de Matemática, First Semester 2009
(Prof. Mauricio Ayala Rincón)