Tietojenkäsittelyteoria

Laskettavuusteoriaa (ratkeavat ja ratkeamattomat ongelmat, rekursioteorian alkeita). Laskennan vaativuusteoriaa (NP-täydellisyys, vaativuusmittojen ja -luokkien ominaisuuksia, kombinaatiopiirit, Kolmogorov-kompleksisuus). Satunnaisalgoritmeista. NP-täydellisten ongelmien approksimointiteoriaa. Kryptologiaa.

Esitiedot

Kurssit Johdatus diskreettiin matematiikkaan, Todennäköisyyslaskenta, Algebra sekä Automaatit ja kieliopit, tai vastaavat tiedot. Myös kurssin Matemaattinen logiikka tiedoista on hyötyä.

Kurssikuvaus

Harjoitustehtävät

Tehtävät 1 (html, ps)
Tehtävät 2 (html, ps)
Tehtävät 3 (html, ps)
Tehtävät 4 (html, ps)
Tehtävät 5 (html, ps)
Tehtävät 6 (html, ps)
Tehtävät 7 (html, ps)
Tehtävät 8 (html, ps)
Tehtävät 9 (html, ps)
Tehtävät 10 (html, ps)
Tehtävät 11 (html, ps)
Tehtävät 12 (html, ps)
Tehtävät 13 (html, ps)
Kirjallisuutta (luokittain vaativuusjärjestyksessä)

Yleisteokset

E. Gurari, An Introduction to the Theory of Computation. Computer Science Press 1989.
B. Moret, The Theory of Computation. Addison-Welsey 1998.
J. Gruska, Foundations of Computing. Thomson Computer Press 1997.
J. Savage, Models of Computation: Exploring the Power of Computing. Addison-Wesley 1998.
U. Schöning, R. Pruim, Gems of Theoretical Computer Science. Springer-Verlag 1998.

Käsikirjat

M. Atallah (ed.), Algorithms and Theory of Computation Handbook. CRC Press 1999.
J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity. Elsevier/MIT Press 1990.

Laskettavuusteoria

M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall 1972.
N. Pippenger, Theories of Computability. Cambridge University Press 1997.
H. Rogers, Jr., Theory of Recursive Functions and Effective Computability. McGraw-Hill 1967 (MIT Press 1987).
P. Odifreddi, Classical Recursion Theory 1-2. Elsevier 1989/1999.

Laskennan vaativuusteoria

M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. 1979.
D. Bovet, P. Crescenzi, Introduction to the Theory of Complexity. Prentice-Hall 1994.
C. Papadimitriou, Computational Complexity. Addison-Wesley 1994.
J. Balcázar, J. Díaz, J. Gabarró, Structural Complexity 1-2. Springer-Verlag 1988/1990.
C. Yap, Theory of Complexity Classes, Volume 1.Oxford University Press, to appear.
M. Li, P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Ed. Springer-Verlag 1997.
I. Wegener, The Complexity of Boolean Functions. Wiley/Teubner 1987.
H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag 1999.

Satunnaisalgoritmit

R. Motwani, P. Raghavan, Randomized Algorithms. Cambridge University Press 1995.
H. Habib et al. (eds.), Probabilistic Methods for Algorithmic Discrete Mathematics. Springer-Verlag 1998.

NP-täydellisten ongelmien approksimointi

V. Vazirani, Approximation Algorithms. Springer-Verlag, to appear.
G. Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag 1999.
D. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems. PWS Publishing 1996.
S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems. ECCC Monographs 1994.
M. Sudan, Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. Springer-Verlag 1995.
E. Mayr et al. (eds.), Lectures on Proof Verification and Approximation Algorithms. Springer-Verlag 1998.

Kryptologia

B. Schneier, Applied Cryptography, 2nd Ed. John Wiley & Sons 1996.
A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography. CRC Press 1997.
A. Salomaa, Public-Key Cryptography, 2nd Ed. Springer-Verlag 1996.
O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer-Verlag 1999.
O. Goldreich, Foundations of Cryptography (Fragments of a Book). ECCC Monographs 1995.
M. Luby, Pseudo-Randomness and Cryptographic Applications. Princeton University Press 1993.

Linkkejä

Organisaatioita

ACM SIGACT
DIMACS
DIMATIA
EATCS
SIAM Activity Group on Discrete Mathematics

Konferensseja

CCC 2000
STOC 2000
FOCS 2000
ICALP 2000
DIMACS Workshop on Intrinsic Complexity of Computation

Sähkölehtiä

Riippumattomat:
Chicago Journal of Theoretical Computer Science
Discrete Mathematics and Theoretical Computer Science
ECCC - The Electronic Colloquium on Computational Complexity
The Electronic Journal of Combinatorics

Tieteelliset seurat:
ACM Digital Library
IEEE/CS Digital Library
IEEE Journals
Journal of the ACM
SIAM Journal on Computing
SIAM Journal on Discrete Mathematics
SIGACT News Online

Kaupalliset:
Acta Informatica
Combinatorica
Computational Complexity
Discrete Applied Mathematics
Information and Computation
Information Processing Letters
Journal of Complexity
Journal of Computer and System Sciences
Journal of Cryptology
Random Structures & Algorithms
Theoretical Computer Science
Theory of Computing Systems

Bibliografioita, kotisivuja, hakukoneita

Uutisryhmä comp.theory
Comp.Theory FAQ
STOC Bibliography
FOCS Bibliography
GI-FG Komplexität
TCS Virtual Address Book
Theoretical Computer Science on the Web
CORA Complexity Papers

Kurssikokeet kevät 2000:

1. välikoe 1.3.2000: Tehtävät(html, ps)
2. välikoe 20.4.2000: Tehtävät(html, ps)
Kurssin tulokset

Loppukokeet:

Kommentit: orponen@math.jyu.fi
Muutettu viimeksi: 21.10.2000