آکادمیک

آکادمیک

اسلاید 1: عنوان ارائهاساتید راهنما :نام استاد اولنام استاد دومارائه دهنده : وحید باقیبهمن ۱۳۹۹دانشگاه تهرانپردیس دانشکده های فنیدانشکده علوم مهندسیمهندسی کامپیوتر – الگوریتم ها و محاسبات

اسلاید 2: Department of Algorithms and ComputationSchool of Engineering ScienceCollege of EngineeringUniversity of TehranWinter 2019Test SubjectPresentation by : Vahid Baghi

اسلاید 3: mode of computationdeterministic modeParameters for a Complexity Classnondeterministic mode

اسلاید 4: Time is Tape DependentTheorem : Let 𝑡 𝑛 be a function , where 𝑡 𝑛 >𝑛 .Then every 𝑡 𝑛 time multitape Turing machine has an equivalent 𝑂(𝑡 2 (𝑛)) time single-tape Turing machine.Transition Logic⊔ 10∞ ⊔#001#011#10∞⊔ 0 11∞⊔ 0 01Transition Logic110

اسلاید 5: Proper Complexity FunctionsDefinitionThere exists a TM M that outputs exactly 𝑓 𝑛 symbols on input 1 𝑛 and runs in time O(𝑓 𝑛 +𝑛) and space O(𝑓 𝑛 )f is a proper complexity function if :∀𝑛 :𝑓 𝑛 ≥𝑓(𝑛−1) For Example : log 𝑛 , 𝑛 , 𝑛 2 ,…

اسلاید 6: A complexity class is a set of classes of decision problems (or languages) with the same worst-case complexityComplexity ClassesDTIME or TIME is the computational resource of computation time for a deterministic Turing machineDTIME DSPACE DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine