Tik-79.194 Tietojenkäsittelyteorian seminaari
Ohjelma kevät 2001

Viikko 3: Johdanto (IN)

Viikko 4: Laskennallisesti vaativat ongelmat (IN)

Viikko 5: Ei seminaaria

Viikko 6:

Riku Saikkonen (opp: Soininen)

• B. Selman, D.G. Mitchell, and H.J. Levesque. Generating hard satisfiability problems, AIJ 81 (1996) 1-2, 17-30.
• J.M. Crawford and L.D. Auton. Experimental Results on the Crossover Point in Random 3SAT, AIJ 81 (1996) 1-2, 31-57.

Viikko 7:

Teemu Hirsimäki (opp: Saikkonen)

David G. Mitchell and Hector J. Levesque. Some Pitfalls for Experimenters with Random SAT, AIJ 81 (1996) 1-2, 111-125.

Rauni Pääkkönen (opp: Saikkonen)

J. W. Freeman. Hard Random 3-SAT Problems and the Davis-Putnam Procedure, AIJ 81 (1996) 1-2, 183-198.

Viikko 8: Ei seminaaria (Hiihtoloma)

Viikko 9:

Petteri Kaski (opp: Hirsimäki, Pääkkönen)

R. Schrag and J. M. Crawford, Implicates and Prime Implicates in Random 3SAT, AIJ 81 (1996) 1-2, 199-222.

Viikko 10: (Seminaari peruutettu sairastumisen vuoksi)

Viikko 11:

Johan Wallen (opp: Hirsimäki, Pääkkönen)

J. C. Pemberton and W. Zhang. Epsilon-Transformation: Exploiting Phase Transitions to Solve Combinatorial Optimization Problems, AIJ 81 (1996) 1-2, 297-325.

Viikko 12:

Tuomo Pyhälä (opp: Wallen)

T. Hogg. Refining the Phase Transition in Combinatorial Search, AIJ 81 (1996) 1-2, 127-154.

Viikko 13: Ei seminaaria

Viikko 14: Ei seminaaria

Viikko 15: Pääsiäisloma

Viikko 16:

Timo Soininen (opp: Pyhälä)

C. Gomes, B. Selman, N. Crato, and H. Kautz. Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, J. of Automated Reasoning, 24 (2000) 1/2, 67-100.

Viikko 17:

Teemu Hirsimäki (opp: Kaski)

Scott H. Clearwater and Tad Hogg. Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms, AIJ 81 (1996) 1-2, 327-347.

Rauni Pääkkönen (opp: Kaski)

W. Zhang and R. E. Korf. A Study of Complexity Transitions on the Asymmetric Traveling Salesman Problem, AIJ 81 (1996) 1-2, 223-239.