CMPT 120 Study Guide - Final Guide: Linear Search, Integer Factorization, Halting Problem

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 120
• Professor: Steven Pearce

Document Summary

System in which program are written to find an answer, able to solve any computational problem given enough time and space. Hypothetical device representation computing machine to help computing scientists understand the limits of mechanical computation - mathematical model. Used to analyze the general properties of computers (theoretical abilities and limitations of a computer) Theory device that manipulates symbols on a strip of tape according to table of rules (the program) to stimulate to logic of computers. Deterministic: basic computer that uses a fixed set of rules to determine future actions. Non-deterministic: works in parallel to prescribe more than one action for one solution. Branch of theory of computation that focuses on classifying computational problems according to their inherent difficulty and relating those classes to each other. Central study on size of problem, measuring their difficulty to solve in terms of time calculated as a function of the size (n) of the instance.