What we have learnt in this courseCOS116: Instructor Sanjeev Arora05/01/08Roughly three parts of the courseLectures 1-10, Lab 1-5: Expand your notion of “computation”.• Scribbler• Pseudocode• Game of life, cellular automata, physical systems (weather, twister..)• Web, networks, websearch, datamining.• Turing-Post programs (universal programs, undecidability)• Digital sound and musicControlling Scribbler’s behavior Scribbler Control Panel(uses “pseudocode”)Steps in solving a computational task •Design an algorithm: A precise,unambiguous description for how to compute a solution.•Express algorithm in pseudocode.•Turn pseudocode into computer program. Pseudocode: Workaround for Computing’s Tower of Babel;shares features with most programming languages. (Mainfeatures: basic arithmetic operations; “conditional branching” (if-then-else); loops (do for; do while ())Creating new worlds (“simulation”)(game of life, weather, twisters…)Steps:• Figure out the “rules” for particles’ actions (how their ‘state” evolves with time)• Figure out how to write the code for changes undergoneby a particle in one time step.•Simulation = one big “Do for” loop.How do we measure the “speed” of an algorithm?•Ideally, should be independent of:–machine–technologyAnswer: Count number of elementary steps.Example: Binary search on a sortedarray of n numbers takes 4 log n steps.(Also studied other notions of “search”including data mining and web search.)What are limits of computation?•1 dimensional unlimited scratchpad (“infinite”)•Only symbols are 0/1 (tape has a finite number of 1s)•Can only scan/write one symbol per step•Program looks like •We believe this simple modelcan simulate all physically realizable computational models.(“Church Turing Thesis.”)1. PRINT 0 2. GO LEFT 3. GO TO STEP 1 IF 1 SCANNED 4. PRINT 1 5. GO RIGHT 6. GO TO STEP 5 IF 1 SCANNED 7. PRINT 1 8. GO RIGHT 9. GO TO STEP 1 IF 1 SCANNED 10. STOP The Doubling ProgramExamples of “undecidable” problems•Given a starting configuration of Game of Life, and a specific cell index, say (11, 15),decided if that cell ever gets occupied.•Given a program and an input for it, decide if the program ever halts when run on that input.• Given a mathematical statement, decide if it has a proofin the standard axiomatic framework for math.Other ideas encountered: proof by contradiction, self-reproducing programs, the possibility that manysimply described systems may have no succinct “theories.”Lectures 11-16; Labs 6-7: Looking inside current computers• Boolean logic• Circuits (combinational, and sequential)• Finite state machine (the “controller”) • CPUs and computer organization. • Silicon chips; microprocessors; Moore’s Law• Caching and MultitaskingBoolean logic(Three Representations)Boolean Expression E = S AND DTruth table:Value of E for every possible D, S. TRUE=1; FALSE= 0.001011110000ESDBoolean CircuitESDHow circuits get “memory”SRMR-S Flip FlopSynchronous Sequential Circuit(aka Clocked Sequential Circuit)CLOCKINPUTSCombinational CircuitMemory(flip-flops)Also studied: Finite State MachinesModern Computer (simplified view):FSM controlling a memory bankProgram (in binary)stored in memoryMemory RegistersArithmetic and Logic Unit(ALU)Control FSMLots of Custom HardwareInstruction PointerRAMLibrarian arrangementReserves“Most popular” shelf: 20% most popular booksDiskMemoryCacheTop 4%CPUComputerOften, today’s computers have even more levels of caching“80-20 Rule”•Building reliability on top of unreliable protocols.(retransmission, timeout, etc.)• Decentralized control. (cs.princeton.edu : DNS physical routing )• Reliance on kindness of strangers.Internet: Main themesScience behind modern computersLasers; used in chip manufacturing,fiber optic cablesSemiconductors: rely on quantum mechanics. Chips manufactured bya “photography”-like technique.Touched upon: Moore’s law (hows and whys)Lectures 16-24; Labs 7-10: New Concepts that arose from study of computers and computation• WWW and the Internet • Efficient computations, P vs NP, NP-completeness• Cryptography; Zero Knowledge Proofs• Viruses/Worms/Zombies/Cybersecurity• Machine Learning• Artificial intelligence.The P vs NP Question•P: problems for which solutions can be found in polynomial time (nc where c is a fixed integer and n is “input size”). Example: Rumor Mill•NP: Decision problems for which a “yes” solutioncan be verified in polynomial time.•Question: Is P = NP? “Can we automate brilliance?”(Note: Choice of computational model ---Turing-Post, pseudocode, C++ etc. --- irrelevant.)NP-complete problems: The “hardest” problems of NP.Viruses and WormsAutomated ways of breaking in;Use self-replicating programs.Studied how and why people create these(“botnets”). No real solution in sight except eternal vigilanceCryptography•Creating problems can be easier than solving them (eg “factoring”)•Difference between seeing information and making sense of it(e.g., one-time pad, zero-knowledge proofs)•Role of randomness in the above•Ability of 2 complete strangers to exchange secret information(public key cryptosystems)Machine learning, AIMachine learning: less ambitious. Make computerdo sort of intelligent tasks in very limited domains(understanding images, speech recognition, etc.)Key idea: learning algorithm that is “trained” withlarge amounts of Data.AI: try to create more general intelligence.One measure of success: Turing Test.Simulation argument for feasibility of AI.Searle’s argument why strong AI is impossibleCryptographyGenerally accepted fact about AIProgramming all necessary knowledge into computers ishopeless.Only hope : General purpose Learning AlgorithmsMany years of learningApproach already successful in restricted domains:Deep Blue, Google, Automated Stock Trading, Checking X-rays.Thoughts about Deep Blue• Tremendous computing power (ability to “look ahead” several moves)• Programmed by a team containing chess grandmasters.• Had access to huge database of past chess games.• Used machine learning tools on database to hone its skills.“Human-machine computing”Another example of human-computer computing…Olde dream: “central repository of knowledge; allfacts at your finger-tips.How it happened:100s of millions of people created “content” for their ownpleasure.Powerful
View Full Document
Unlocking...