Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
lopro [2011/09/25 14:13]
val.tannen
lopro [2011/11/16 10:24] (current)
val.tannen
Line 3: Line 3:
 **Doctoral course by Val Tannen** **Doctoral course by Val Tannen**
  
-Syllabus+Lecture notes 1 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln1.pdf|(pdf)]]
  
-   ​Introduction+Homework 1 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​hw1.pdf|(pdf)]]
  
-Truth, proof, and computationsome basic results about first-order logic +Lecture notes 2 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln2.pdf|(pdf)]]
-A bit of the story of how Mathematical Logic (and Electronic Technologygave birth to Computer Science. ​+
  
-Part IProbability of Logic+Lecture notes 3 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln3.pdf|(pdf)]]
  
-Random graphs and random structures +Lecture notes 4 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln4.pdf|(pdf)]]
-0-1 laws +
-Queries on probabilistic databases+
  
-Part IILogic of Probability+Homework 2 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​hw2.pdf|(pdf)]]
  
-Pearl-Paz logics for reasoning about probabilistic (in)dependence +Lecture notes 5 (revised) [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln5rev.pdf|(pdf)]] 
-Reasoning about independence in Bayesian and Markov networks; the Hammersley-Clifford theorem  + 
-Reasoning about independence in relational graphical models (PRMs and RMNs)+Lecture notes 6 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln6.pdf|(pdf)]] 
 + 
 +Lecture notes 7 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln7.pdf|(pdf)]] 
 + 
 +//Course Materials//​ 
 + 
 +"​Models for Incomplete and Probabilistic Information"​ Green and Tannen [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​GreenTannen06.pdf|(pdf)]] 
 + 
 +Old lecture notes on computability [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​compNotes.pdf|(pdf)]] 
 + 
 +"On the Unusual Effectiveness of Logic in Computer Science"​ Halpern, Harper, Immerman, Kolaitis, Vardi, and Vianu" [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​UnusualEffectiveness.pdf|(pdf)]] 
 + 
 +//​Syllabus//​ 
 + 
 +  *Introduction 
 +    *Truth, proof, and computation:​ some basic results about first-order logic 
 +    *A bit of the story of how Mathematical Logic (and Electronic Technology) gave birth to Computer Science.  
 + 
 +  *Part I: Probability of Logic 
 +    *Random graphs and random structures 
 +    *0-1 laws 
 +    *Queries on probabilistic databases 
 + 
 +  *Part II: Logic of Probability 
 +    *Pearl-Paz logics for reasoning about probabilistic (in)dependence 
 +    *Reasoning about independence in Bayesian and Markov networks; the Hammersley-Clifford theorem  
 +    *Reasoning about independence in relational graphical models (PRMs and RMNs) 
 + 
 +//Some useful books// 
 + 
 +I will rely on basic results about computability and complexity that 
 +are (usually) covered in a Computer Science undergraduate curriculum. 
 +If you need to freshen up on these topics, I can recommend:​ 
 +  *"​Introduction to the Theory of Computation",​ Sipser, PWS 1997. 
 +  *"​Introduction to Automata Theory, Languages, and Computability",​ Hopcroft, Motwani, and Ullman, 2nd edition, Addison-Wesley 2001. 
 +  *"​Computational Complexity",​ Papadimitriou,​ Addison-Wesley 1994. 
 +  *"​Computational Complexity: A Modern Approach",​ Arora and Barak, Cambridge University Press 2009. 
 +  *I have also made available my own notes on computability (see above). 
 + 
 +There many textbooks on logic but let me recommend my favorites:​ 
 +  *"​Logic for Computer Science",​ J. Gallier, (Wiley 1986), out of print but available [[http://​www.cis.upenn.edu/​~jean/​gbooks/​logic.html|here]] with the latest revisions. 
 +  *"A mathematical introduction to logic",​ H. B. Enderton, Harcourt/​Academic Press, 1972 and 2000. 
 +  *"​Introduction to mathematical logic",​ E. Mendelson, various publishers, 1964, 1979, 1987, and 1997. 
 +  *"​Computability and logic",​ G. Boolos and R. Jeffrey, Cambridge Univ.~Press,​ 1974 and 1980. 
 + 
 +The complete classification of the prefix fragments of FOL from the point of view of the decidability of satisfiability is in: 
 +  *"The Classical Decision Problem",​ Boerger, Graedel, and Gurevich, Springer 1997. 
 + 
 +The story of how mathematical logic gave birth to computer science is told best in: 
 +  *"​Engines of Logic: Mathematicians and the Origins of the Computer",​ Davis, 2nd edition, Norton 2001. 
 + 
 +There are many, many textbooks that offer an introduction to probabilities I prefer those that do a good job on discrete probability spaces. Some examples: 
 +  *"​Probability and Random Processes",​ Grimmett, Stirzaker, Oxford U. Press 2001. 
 +  *"​Probability:​ Theory and Examples",​ Durrett, Thomson (Brooks/​Cole) 2005. 
 +  *There is also a brief introduction to probability in chapter 2 of Koller-Friedman (mentioned below). 
 + 
 +For 0-1 laws, I will consult 
 +  *"​Elements of Finite Model Theory",​ Libkin, Springer 2004. 
 +  *"The Strange Logic of Random Graphs",​ Spencer, Springer 2001. 
 + 
 +For the logic of independence in Bayesian and Markov networks I will follow selected sections from: 
 +  *"​Probabilistic Graphical Models",​ Koller, Friedman, MIT Press 2009.
  
  
  
  
-My lecture notes on Computability ​