Siirry pääsisältöön
MyCourses MyCourses
  • Koulut
    Insinööritieteiden korkeakoulu (ENG) Kauppakorkeakoulu (BIZ) Kemian tekniikan korkeakoulu (CHEM) – Oppaita opiskelijalle (CHEM) – Raportinkirjoitusohje (CHEM) Perustieteiden korkeakoulu (SCI) Sähkötekniikan korkeakoulu (ELEC) Taiteiden ja suunnittelun korkeakoulu (ARTS) Kielikeskus Avoin yliopisto Kirjasto Aalto-yliopiston pedagoginen koulutus UNI (tentit) Sandbox
  • CORONAVIRUS INFO
    Koronavirus - tietoa opiskelijalle Coronavirus - information for students Coronavirus - information för studerande Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia Effects of the coronavirus on studies: questions and answers Coronaviruset och studierna: frågor och svar Corona help for teachers
  • Palvelulinkit
    MyCourses - Ohjeita opettajille - Varaa online aika digitaalisen opetuksen asiantuntijalta (opetttajille) - Opetuksen digitaaliset työvälineet - Opetuksen tietosuojaa opettajille - Ohjeita opiskelijoille - Työtila opinnäyteohjaukseen WebOodi Into-opiskelijaportaali Courses.aalto.fi Kirjasto- ja tietopalvelut - Tiedonhakijan oppaat - Imagoa / Avoin tiede ja kuvien käyttö Tietotekniikkapalvelut Kampuskartat - Etsi tiloja ja tarkista rakennusten aukioloajat Ruokalistat.net AYY Aalto-yliopiston ylioppilaskunta Aallon yhteisötori
  • ALLWELL?
    Opiskelutaidot Tukea opiskeluun Starting Point of Wellbeing AllWell?-opiskeluhyvinvointikyselystä
  •   ‎(fi)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Käytät vierailijatunnusta (Kirjaudu)

close

CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017

  1. Etusivu
  2. Kurssit
  3. perustieteide...
  4. tietotekniika...
  5. cs-e4530 - co...
Kurssiesite

Yleinen

  • Yleinen

    Yleinen

    

    Course Information


    Lectures

    Mondays and Wednesdays 10-12 T3
    First lecture: 9th January

    Classroom sessions

    Tuesdays 14-16 A211
    First session; 17th January

    Lecturer

    Chris Purcell

    Teaching Assistants

    Janne Korhonen, Tuomo Lempiäinen

    Topics

    Models of computation: Turing machines, RAM machines, Boolean
    circuits
    Modes of computation: deterministic, nondeterministic, parallel,
    randomised, alternating
    Basic notions of computational complexity: complexity measures and
    complexity classes, hierarchy theorems, reductions between problems,
    completeness
    Central complexity classes: P, NP, PSPACE, NC, polynomial time
    hierarchy, etc.
    Design of completeness proofs, especially for NP-completeness
    Applications and extensions: approximability, counting, games,
    cryptographic protocols

    Learning Outcomes

    Once you have taken the course, you master the key complexity
    classes, their underlying models of computation, and
    relationships.
    You are able to formalise and abstract from a given computational
    task relevant computational problems and argue that they belong
    to appropriate complexity classes.
    You understand the concept of reductions and how it can be used
    to order problems by their computational complexity. You are able
    to show using reductions that a problem is complete for a central
    complexity class (such as NP) and you understand the
    importance and implications of such a result.
    You are familiar with the concepts of randomised, approximation,
    and parallel computation and aware of related complexity classes
    and their relation to other complexity classes and their models of
    computation.

    • icon for activity News forum Keskustelualue
    • icon for activity Yleinen keskustelu Keskustelualue

Kurssin etusivu

Kurssin etusivu

Seuraava osio

Materiaalit►
Ohita
Tulevat tapahtumat
Ladataan Ei tulevia tapahtumia
Siirry kalenteriin...
  • CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017
  • Osiot
  • Yleinen
  • Materiaalit
  • Tehtävät
  • Etusivu

Aalto logo

Tuki / Support
  • MyCourses help
  • mycourses(at)aalto.fi
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten

Käytät vierailijatunnusta (Kirjaudu)
  • Koulut
    • Insinööritieteiden korkeakoulu (ENG)
    • Kauppakorkeakoulu (BIZ)
    • Kemian tekniikan korkeakoulu (CHEM)
    • – Oppaita opiskelijalle (CHEM)
    • – Raportinkirjoitusohje (CHEM)
    • Perustieteiden korkeakoulu (SCI)
    • Sähkötekniikan korkeakoulu (ELEC)
    • Taiteiden ja suunnittelun korkeakoulu (ARTS)
    • Kielikeskus
    • Avoin yliopisto
    • Kirjasto
    • Aalto-yliopiston pedagoginen koulutus
    • UNI (tentit)
    • Sandbox
  • CORONAVIRUS INFO
    • Koronavirus - tietoa opiskelijalle
    • Coronavirus - information for students
    • Coronavirus - information för studerande
    • Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia
    • Effects of the coronavirus on studies: questions and answers
    • Coronaviruset och studierna: frågor och svar
    • Corona help for teachers
  • Palvelulinkit
    • MyCourses
    • - Ohjeita opettajille
    • - Varaa online aika digitaalisen opetuksen asiantuntijalta (opetttajille)
    • - Opetuksen digitaaliset työvälineet
    • - Opetuksen tietosuojaa opettajille
    • - Ohjeita opiskelijoille
    • - Työtila opinnäyteohjaukseen
    • WebOodi
    • Into-opiskelijaportaali
    • Courses.aalto.fi
    • Kirjasto- ja tietopalvelut
    • - Tiedonhakijan oppaat
    • - Imagoa / Avoin tiede ja kuvien käyttö
    • Tietotekniikkapalvelut
    • Kampuskartat
    • - Etsi tiloja ja tarkista rakennusten aukioloajat
    • Ruokalistat.net
    • AYY Aalto-yliopiston ylioppilaskunta
    • Aallon yhteisötori
  • ALLWELL?
    • Opiskelutaidot
    • Tukea opiskeluun
    • Starting Point of Wellbeing
    • AllWell?-opiskeluhyvinvointikyselystä
  •   ‎(fi)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎