Transcript PPT
CS120: Lecture 1 MP Johnson Hunter College [email protected] agenda • • • • Admin Syllabus Survey Data, storage, representation admin • • • • • • Sessions: 9:48-11:26am / 11:36-1:14pm HW 224 Class page Email Text OHs tba Grading – Hw (written, prog., labs) – O(6) ~ 45% – Exams – 20% + 25% – Class partic/quizzes – 10% • Start or end of class • Attendance is required – 80% Core Class topics 1 2 Breadth-first tour of CS Data – – – 3 How computers work – 4 Machines networks, Internet, OS 1 2 5 6 storage Representation of knowledge) Compression (JPG, MP3) HTML FTP, SSH Algorithms – good ones? Programming / SE / data structures Advanced/optional • • • • • • AI Hardware Crypto Unsolvable problems Search Engines Social/political issues? • Other topics? • Some parts of class will be challenging • Many will be applied/topical – read Slashdot/Digg Survey 1. 2. 3. 4. 5. 6. Name Email (clearly!!) Grade-level Major Why taking class Topics you’re most interested in Q: What are comps? • A: machines that compute • Q: compute what? • A: the output of some algorithm • Alg: list of instructions / recipe – Abstract but unambiguous (how?) – Much more later • Egs: long division algorithm, gcd, sorting Long (pre)history • • • • • Abacus (3000BC) – just storage Pascal (1600s) – addition Leibniz (1600s/1700s) – math Babbage Diff. gin (1800s) – math Babbage An. Gin – punched cards • All these were mechanical (gears, etc.) – Difficult to make reliable & fast & cheap 20th C: electronics • Circuits, transistors, etc. • Mach 1, ENIAC, UNIVAC (1940s) - room-sized • Since then: “just” miniaturization • Mainframes supercomps, minis PCs (“micros”): early 80s on • All “essentially” same: – Run many programs (v. arcade machine) – These programs impl. Algs (tho in diff. langs) – They store, rep, use data Today: data • CS = abstraction + reduction – “that’s so reductive” • • • • In CS, all data is numbers, All numbers are bits (0/1) / bools (F/T) Bit = binary digit boolean ~ George Boole (1800s) Bool logic/algebra • • • • Vals: F, T Ops: and, or, xor, not Draw truth tables Xor intuit: soup or sald • Can write exprs • Exprs can nest Bool expr eg • Suppose A ~ empl A is working, B, C • Suppose want: should always be exactly one empl working • Q: If we only know bool logic, how to test? • Q: how to write a “program” for this in bool logic? • (A & ~B & ~C) | … • (A xor B) & … • (A | B | C) … Q: How to compute/eval this? • We now understand bool ops, so we could perform each op ourselves – A gp of female workers in WWII were called “computers” • Bad: too slow, error-prone • Funda strength of comps: can do some (v. simple) things v. fast strategy • Don’t: create a special machine to comp whole expr/function/program • Do: create a little machine for each component, then combine – Forget about software for now! • How? First, bool ops gates gates Gates elec circuit • No one of these is v. interesting • But two big insights: – Can create an implement gate electronically • 0/1 low/high current – Gates can be combined to produce powerful computations / representations • electronic circuits / chips • Draw circuits for each expr • Of course, want software (non-kickable) • For that we need a compiler… Reading for next week: wiki entries on boolean logic and two’s complete (through section 2 only) Circuits as memory • Flipflop: special circuit that can store data – 1 bit per FF To store, send pulse in top or bottom (0 is ddf) Go through