Laskennanvaativuusteorian projektityö

Laskennanvaativuusteorian projektityö on vapaaehtoinen 1 ov:n (laudatur-tason) työ, joka käsittelee tärkeitä laskennanvaativuusteoriaan liittyviä asioita. Jos olet kiinnostunut, projektityö voidaan laajentaa myös 2ov:n työksi, esim. koodaamalla totetuksen johonkin ongelmista 1-3 (+ toteutuksen aikavaativuusanalyysi). Kerro, jos olet kiinnostunut tästä vaihtoehdosta!

Ilmoita joka tapauksessa, mikäli haluat suorittaa projektityön, niin lisään sinut projektityön postituslistalle, jossa voitte kysellä ja saada ohjausta/vihjeitä työn suorittamisesta.

Työ löytyy täältä pdf:nä

Project work on theory of computational complexity

The project work on theory of computational complexity is 1 credit unit volunteer project about important topics in theory of computational complexity. If you are interested the work can be enlargened into 2 cu's work by e.g. implementing some problem (problem 1 is at least suitable for that). Tell if you are interested about this possibility!

Tell anyway if you are taking the project work so I can add your into mailing list of the project work and you can ask questions and get answers/hints byt the list. The project work can be found here as pdf

Kirjallisuutta/Literature

• Orponen, P.: Laskennan vaativuusteoriaa. Laskennanteoria-luentomonisteen luku 7.
  (Orposen vanha moniste, kopiot saa Wilhelmiinalta. Tiivis suomenkielinen esitys, jolla pärjää periaatteessa yksinäänkin, joskisn kirjoista voi lukea aina lisää.)
• Sudkamp, T.A. Languages and Machines. An Introduction to the Theory of Computer Science. Chapters 14-15.
  Really comprehensive representation, slightly mathematical.
• Sipser, M. Introduction to the Theory of Computation.
  Chapters 7-9 cover the topics really well.
• Lewis, H.R. & Papadimitriou, C.H. Elements of the Theory of Computation.
  The 1st edition, chapter 7 covers the whole area well, the 2nd edition, chapters 6 and 7 cover the NP-stuff well but nothing else.
• Hopcroft, J.E., Motwani, R., Ulman, J.D. Introduction to Automata Theory, Languages, and Computation.
  Chapters 10 (and 11) cover the NP-stuff well, but nothing else.
• Kinber, E. & Smith, C. Theory of Computing. A Gentle Introduction.
  Chapter 6: NP-stuff briefly and clearly, but nothing else.