"raskeltarvutatavad" - 1 õppematerjal

Programmeerimiskeel

1016 / 10-23 = ca = 1039korda .universumielueajooksulsuudaksvalgusläbidakõigielektronideraadiusikokkuca (1016 *1080 ) / 10-23 = ca = 10119korda ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 19 Mõistlikud ja rasked probleemid •Polünomiaalne ajaline keerukus .Algoritm on polünomiaalne kui ta onO( nd) mingi täisarvud korral .Polünomiaalseid algoritme peetakse efektiivseteks .Nad lahendavad ülesande tavaliselt mõistliku ajaga! •Raskeltarvutatavad probleemid .probleemid, millel pole teada polünomiaalset algoritmi ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 20 P ja NP klassi probleemid Otsustus probleemide klass •Klassi P jaoks on olemas determineeritud Turingi masin, mis lõpetab töö polünomiaalse aja jooksul •Klassi NP puhul on olemas mittedetermineeritud Turingi masin, mis lõpetab töö polünomiaalse aja jooksul ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 21 Oraakliga Turingi masin