Shared Flashcard Set

Details

Midterm I
CS 107 HP
101
Computer Science
02/23/2010

Term
 information
Definition
 (human-centric def: what passes between us when we communicate) the removal of uncertainty or suppression of randomness
Term
 isomorphism
Definition
 map associating symbols with what they represent- any isomorphism can encode any meaning, key is in construction/maintenance of map. this is the basis of coding.
Term
Definition
 choice of symbol/physical representation for an idea; the need to invent new symbols or symbols that take time/space; hand #s, roman numerals grow in proportion to #
Term
 rules for good codes
Definition
 1) should not need to invent new symbols to encode new things1a) should be a fixed alphabet2) should be efficient- size doesn't grow with thing encoded- many things encoded in small space- length(d) about= its info content
Term
 combinatorics
Definition
 the # of combinations that can be made out of a set # of things. N symbols, code of length d, N^d combinations
Term
 combinatorial explosion
Definition
 # of items that can be encoded explodes as length of code increases- efficient code
Term
 vector
Definition
 combinatorial code that uses #s- (#, #) <#, #, #>. length of vector corresponds to dimension in space
Term
 the more improbable an event..
Definition
Term
 message
Definition
 identifies one object out of a set
Term
 shannon's measurement of info content
Definition
 how many y/n questions does it take to identify? pres approval has 7 questions, or 7 bits
Term
 evolution defined through information theory
Definition
 accumulation of useful information- to create an improbable event like the organization of atoms into an organism
Term
 evolution defined through information theory
Definition
 accumulation of useful information- to create an improbable event like the organization of atoms into an organism. not possible w/out some kind of info storage
Term
 jacquard loom
Definition
 improbable event of weaving complex pattern into cloth- info not in loom, but punched cards-->1st computers
Term
 computation
Definition
 encoding in some medium, transforming the encoding via rules. any time info transformed in precisely determined way, computation takes place
Term
 hobbes
Definition
 the body is a machine, the mind is not separate from the body
Term
 leibniz
Definition
 arithmetic can be performed by machine- invented one, based on pedometer
Term
 boole
Definition
 logical reasoning can be performed by a machine (boolean arithmetic)
Term
 1st true computer
Definition
 babbage's analytical engine, born of difference engine- key was to separate sequence of operations from machines (create a program). store (storage) + mill (arithmetic) + program
Term
Definition
 the first programmer
Term
 mechanically computable
Definition
 1) set out in finite terms exact instructions 2) produce desire result in finite steps 3) could be carried out by human and pencil 4) demands no insight/ingenuity on part of human
Term
 church-turing thesis
Definition
 any mechanically computable function can be completed on turing machine
Term
 UTM
Definition
 has a fixed set of states and can simulate any TM. reads the description of the encoded TM, acts like the encoded TM operating on the input
Term
 what it means to be universal
Definition
 means to store fixed set of symbols (tape, means to perform simple operations on those symbols (execution unit), means to follow precisely defined set of instructions
Term
 true computer
Definition
 has universality, can store a set of #s or symbols, perform operatiosn on them, and follow arbitrary set of instructions
Term
 algorithm
Definition
 set of instructions that solves particular problem (a recipe) crucial elements: specified set of inputs, set of steps w/ clear beginning end, appropriately specific and feasible, eventually stops, must be executed by machine, work for all inputs. fastest algorithm is the best
Term
 relationship bt size of text of a program and time it takes to run
Definition
 there is no simple relationship
Term
 algorithmic complexity
Definition
 expression describing # of steps needed as function of problem size
Term
 # steps grows more slowly;faster;much faster;in proportion to input size
Definition
 logarithmic;polynomial;exponential;linear complexity
Term
 Travelling Salesperson Problem
Definition
 there are n! paths, which makes complexity even worse than exponential. like the knapsack problem this is the best we've got.
Term
 NP Complete
Definition
 computationally unfeasible, currently. if we could solve one we could solve them all
Term
 the self-reference of the halting problem
Definition
 if P halts, B doesn't, if P doesn't, B does- if B doesn't, B does
Term
 noncomputable problems reveal deep truths about computation
Definition
 can be self-referential, can resist analysis
Term
 analog; digital
Definition
 continuous, infinite inputs, no separation from noise & entropy; finite, discrete set of inputs- put into binary, easy to identify noise
Term
 noise; entropy
Definition
 the addition of error in copying info; the tendency for things to become disordered
Term
 stable pattern
Definition
 information pattern that is relatively permanent or common. digital copying allows stable information patterns
Term
 one of the simplest forms of computing
Definition
 information copying
Term
 rules of the utm ecosystem
Definition
 utms move randomly from tape to tape, can read or write more than one tape, fixed amount of tape, error sometimes occur
Term
 UTM ecology: program R
Definition
 write program R on a tape- a self-replicating program
Term
 programs x, y and z
Definition
 write x on each of two tapes (fecundity); write y on a tape, then check to make sure it was written correctly (copy-fidelity); if tape has z, re-write to refresh it (longevity)
Term
 selfishness in UTM ecology
Definition
 hoarding tapes, outcompeting neighbors for tapes
Term
 separate copies of pattern are
Definition
 indistinguishable- not the tape itself that matters, but the pattern on it
Term
 simple self-replications
Definition
 machine that can only copy itself in the absence of mutations
Term
 cellular automaton
Definition
 array of cels that have two states + simple set of rules for updating cell states over time. 2^8 (256) possible rule sets- 256 ways ca might evolve in time
Term
 four classes of CA rule behavior
Definition
 uniformity (all black/white/simple patterns); structure (nested patterns of considerable complexity); chaos (no predictable patterns); local structure (mixture of things happening locally with background simple patterns)
Term
 fundamental fact of nature
Definition
 simple computations can yield unexpected, surprising results
Term
 heat
Definition
 pattern that emerges when molecules move randomly- can't observe by looking at one molecule
Term
 ca rule 90
Definition
 nested- interesting bc contains itself- portion is rescaled version of whole thing
Term
 ca rule 30; 110
Definition
 chaos; local structure
Term
 game of life as ex of emergence
Definition
 existence of gliders/shooters shows properties not built in- high level properties can't be predicted from low-level ones
Term
 emergence defines disciplinary boundaries
Definition
 physics-> chem, chem->bio, bio->anthro, antro->philosophy/lit/art
Term
 emergence's relationship to noncomputability
Definition
 cannot tell by looking at rules whether interesting properties will emerge. also the only way to find out for all programs p "does p do x" is to run program p. computation is inscrutable!
Term
 fredkin's hypothesis
Definition
 what underlies the wave/particle level of physics? the universe is a computer
Term
 key to emergence of life on earth
Definition
 discovery by nature of how to extract and efficiently encode information- had only atoms/molecules to work with
Term
 life= metabolism;reproduction
Definition
 obtaining energy from environment to break dwon raw materials into building blocks and construct/repair body & structure; make approximate copies of one's self
Term
 von neumann's theory
Definition
 constructive, copying and control machines creates self-replicating machine+blueprint. gets corrupted and carries corruption
Term
 reactions
Definition
 collisions of molecules, leading to rearrangement of atoms into new molecules- depends on molecule shape
Term
 catalyst
Definition
 molecule whose presence accelerates reaction without being changed
Term
 polymer
Definition
 molecule made by stringing many small units from fixed set. long chains, define molecules shape and can carry info. sugar, amino acid, nucleotide- 3 polymers imp in life
Term
 autocatlysis
Definition
 how self-replicating info could arise. molecule that catalyzes own reaction. was probably rna
Term
 nucleotides
Definition
 consist of backbone+base, always read 5->3, bases can bond to each other (A to U or G to C)
Term
 rna
Definition
 AUGC- elaborate structure, carry info, self-replication possible
Term
 rna templated polymerization
Definition
 catalyst that causes copying of any other rna molecule- a tape copying turing machine
Term
 matter living when
Definition
 interacts w/ environment, resists entropy
Term
 miller-urey experiment
Definition
 evidence for rna world in prebiotic world- put methane, ammonia, hydrogen, water + electric current, found organic compounds
Term
 evidence for rna world
Definition
 Catalytic and autocatalytic RNA can be produced in lab, Key cellular reactions are still catalyzed by RNA in nature, Even simpler replicators could have predated RNA
Term
 federation
Definition
 collection of molec that together are capable of more efficient replication- ex ribozymes that catalyze nucleotide production- beginnings of the cell
Term
 self organization
Definition
 no machine needed, as in membranes
Term
 proteins
Definition
 polymers with 20 possible subunits- much greater variety of molecule shapes available with their existence
Term
 dna
Definition
 improves longevity, much more stable, thymine instead of cytosine allows error correction
Term
 metabolic machinery
Definition
 bacteria, archaea, eucaryotes- different ribosome, energy production different
Term
 information processing machinery
Definition
 bacteria (unshielded chromosomes) and archaea & eucaryotes (histones, promoters)
Term
 alternate definitions of life
Definition
 nasa- information first: self-sustained chemical capable of darwinian evolution. sagan- metabolism first: localized region increases in order through cycles driven by energy flow
Term
 myoglobin
Definition
 first protein we learned a lot about- transports oxygen in lower animals (we use hemoglobin)
Term
 pepsin
Definition
 digestion. digests whatever contacts- deactivated while in cell until stomach
Term
 myosin and actin, bathed in ATP
Definition
 myosin flexes- millions of molecules together make a muscle fiber
Term
 aperiodic
Definition
 doesn't repeat- high information content. as in, chromosomes
Term
 sizes of things
Definition
 eukaryotes->prokaryotes->viruses->proteins->small molecules->atoms
Term
 antibody
Definition
 defense. several flexible arms-adaptive. 2 to 10 binding sites, 10^15 in our blood
Term
 insulin
Definition
 communication. describes amount of sugar in blood, tells organs what to do. small distinctive shape, difficult folding problem
Term
 collagen
Definition
 structure- triple helix. tendons, skin, organs
Term
 machinery construction
Definition
 protein folding is a problem for cells- misfolding->alzheimers, sickle cell disease. folding environments chaperone folding
Term
 darwin vs mendel
Definition
 darwin said inherited traits are fluid, children get mixtures. mendel said at least some are discrete- traits inherited in numerical ratios, each parent passes half. genetic info is digital.
Term
 oswald avery
Definition
 shows pneumonia's virulence changed by altering dna- implicates dna as material of heredity
Term
 dna replication is obvious
Definition
 because of the structure- two strands with paired bases
Term
 origin of replication
Definition
 part of dna where unzipping starts
Term
 primer
Definition
 shows where replication should start from by creating tags
Term
 extra inheritence
Definition
 protein structure of dna inherited in egg cell
Term
 the blueprints
Definition
 dna transcribed to rna, rna translated to proteins (takes place in ribosome outside nucleus)
Term
 gene
Definition
 code for a single protein. many genes on each dna strand. specific markers show start/stop of genes
Term
 transfer rna (tRNA)
Definition
 code embodied in tRNA. amino acid on one end, anticodon on other. 20 kinds, one for each amino acid
Term
 ribosome
Definition
 two parts lock together with mRNA in between. decoding happens here
Term
 cell has achieved
Definition
 remarkable separation of information and machinery
Term
 subunit
Definition
 responsible for info flow. finds mRNA, matches codons with anticodons.
Term
 error resistance of gene encoding
Definition
 many more codes than amino acids
Term
 homeosis (bateson)
Definition
 process of making two things similar. allows single evolutionary advance to be used over and over. transformation of repeating structures can be basis for emergence of new species.
Term
 embryogensis
Definition
 how embryo forms. timing and place of gene expression is a control problem
Term
 sequence of control
Definition
 start at first instruction, proceed in order unless instructed otherwise. tedium fixed with subroutines
Term
 subroutine
Definition
 instruction that presumes certain level of knowledge-packaged set of instructions that can be used in mult. programs/places/times
Term
 homeobox
Definition
 gene where "run subroutine" command is found. every multicellular animal has this 180 base pair sequence in common. part of transcription factor
Term