《whatis our enc - 副本》由会员分享，可在线阅读，更多相关《whatis our enc - 副本（31页珍藏版）》请在金锄头文库上搜索。
1、What is our IENC produced?Sang Baichuan(Sun)ChangJiang waterway survey center 2013Brief pre-History2006 Yichang-Dapujie Incompleteness of axiomatic mathHilbert, Goedel, etc. (1930) Formalization of “What is Computation?”;“What problems can computers never solve?” Turing, Church, Post etc. (1936) “Co
2、mputation is everywhere” (1940s and onwards) IBM mainframes, DNA, Game of Life, Billiards Balls,.Is it a game, Is it an ecosystem, Is it a computer? (Game of life, 1968)nRules: At each step, in each cellSurvival: Critter survives if it has exactly 2 or 3 neighborsDeath: Critter dies if it has 1 or f
3、ewer neighbors, or more than 3.Birth: If cell was empty and has 3 critters as neighbors, new critter is born.(J. Conway)Moral: Computation lurks everywhere. A central theme in modern TCS: Computational ComplexityHow much time (i.e., # of basic operations) are needed to solve an instance of the probl
4、em? Example: Traveling Salesperson Problem on n citiesNumber of all possible salesman tours = n!( # of atoms in the universe for n =49)One key distinction: Polynomial time (n3, n7 etc.) versus Exponential time (2n, n!, etc.)n =49Some other important themes in TCSnEfficiency common measures: computat
5、ion time, memory, parallelism, randomness,.nImpossibility results intellectual ancestors: impossibility of perpetual motion, impossibility of trisecting an angle, incompleteness theorem, undecidability, etc.n Approximationapproximately optimal answers, algorithms that work “most of the time”,mathema
6、tical characterizations that are approximate (e.g., approximatemax-flow min-cut theorem)n Central role of randomnessrandomized algorithms and protocols, probabilistic encryption,random graph models, probabilistic models of the WWW, etc. n ReductionsNP-completeness and other intractability results (i
7、ncluding complexity-based cryptography) Coming up: Vignettes What is the computational cost of automating brilliance? What does it mean to learn? What does it mean to learn nothing? What is the computational power of physical systems? Will algorithmic thinking become crucial for the social and natur
8、al sciences? How many bits of a math proof do you need to read to check it?What is the computational cost of automating brilliance or serendipity?Vignette 1(P versus NP and related musings)Is there an inherent difference between being creative / brilliant and being able to appreciate creativity / br
9、illiance? Writing the Moonlight Sonata Proving Fermats Last Theorem Coming up with a low-cost salesman tour Appreciating/verifying any of the aboveWhen formulated as “computational effort”, just the P vs NP Question.“General Satisfiability”Given: Set of “constraints”Desired: An n-bit “solution” that
10、 satisfies them all(Important: Given candidate solution, it should be easy to verify whether or not it satisfies the constraints.)“Finding a needle in a haystack”“P = NP” is equivalent to “We can always find the solution to general satisfiability(if one exists) in polynomial time.” is NP-completeExa
11、mple: Boolean satisfiabilitynDoes this formula have a satisfying assignment?nWhat if instead we had 100 variables?n1000 variables?nHow long will it take to determine the assignment?(A + B + C) (D + F + G) (A + G + K) (B + P + Z) (C + U + X)“Reduction”“If you give me a place to stand, I will move the
12、 earth.” Archimedes ( 250BC)“If you give me a polynomial-time algorithm for Boolean Satisfiability, I will give you a polynomial-time algorithm for every NP problem.” - Cook, Levin (1971)“Every NP problem can be disguised as Boolean Satisfiability.”If P = NP, then brilliancewill become routinenProof
13、s of Math Theorems can be found in time polynomial in the proof lengthnPatterns in experimental data can be found in time polynomial in the length of the pattern.nAll current cryptosystems compromised.n Many AI problems have efficient algorithms.“Would do for creativity what controlled nuclear fusio
14、n would do for our energy needs.”What does it mean to learn?(Theory of machine learning)Vignette 2Can we turn into Learning: To gain knowledge or understanding of or skill in by study, instruction, or experiencePAC Learning (Probabilistic Approximately Correct)L. ValiantDatapoints: Labeled n-bit vec
15、tors(white, tall, vegetarian, smoker,) “Has disease”(nonwhite, short, vegetarian, nonsmoker,.) “No disease”Desired: Short OR-of-AND (i.e., DNF) formula that describes fraction of data (if one exists)(white vegetarian) (nonwhite nonsmoker)VVVSample from a Distribution on VVDistributionQuestion: What
16、concepts can be learnt in polynomial time?Benefits of PAC definition Impossibility results: learning many concepts is as hard assolving well-known hard problems (TSP, integer factoring.) implications for goals/methodology of AI New learning algorithms: Fourier methods, noise-tolerantlearning, advances in sampling, VC dimension theory, etc. Radically new concepts: Example: Boosting (Freund-Schapire) Weak learning ( = 0.51) Strong learning ( = 0.99)What does it mean to learn nothing?Vignette 3Encr
