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
Last revision Both sides next revision
lopro [2011/09/25 14:32]
val.tannen 		lopro [2011/11/16 07:34]
val.tannen
Line 4: Line 4:
  
 Lecture notes 1 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln1.pdf|(pdf)]] Lecture notes 1 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln1.pdf|(pdf)]]
 +
 +Homework 1 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​hw1.pdf|(pdf)]]
 +
 +Lecture notes 2 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln2.pdf|(pdf)]]
 +
 +Lecture notes 3 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln3.pdf|(pdf)]]
 +
 +Lecture notes 4 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln4.pdf|(pdf)]]
 +
 +Homework 2 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​hw2.pdf|(pdf)]]
 +
 +Lecture notes 5 (revised) [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln5rev.pdf|(pdf)]]
 +
 +Lecture notes 6 [[http://​www.cis.upenn.edu/​~val/​LogicProbEPFL2011files/​ln6.pdf|(pdf)]]
  
 //Course Materials// //Course Materials//
Line 32: Line 46:
 are (usually) covered in a Computer Science undergraduate curriculum. are (usually) covered in a Computer Science undergraduate curriculum.
 If you need to freshen up on these topics, I can recommend: If you need to freshen up on these topics, I can recommend:
- +  *"Introduction to the Theory of Computation", Sipser, PWS 1997. 
-``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. 
-``Introduction to Automata Theory, Languages, and Computability''​, +  ​*"​Computational Complexity: A Modern Approach", ​Arora and Barak, Cambridge University Press 2009. 
-Hopcroft, Motwani, and Ullman, 2nd edition, Addison-Wesley 2001. +  *I have also made available my own notes on computability ​(see above).
- +
-``Computational Complexity''​, Papadimitriou,​ Addison-Wesley 1994. +
- +
-``Computational Complexity: A Modern Approach'' ​Arora and Barak, +
-Cambridge University Press 2009. +
- +
-I will also make available my own notes on computability ​on the website. +
  
 There many textbooks on logic but let me recommend my favorites: 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.
  
-``Logic for Computer Science'',​ J. Gallier,  +The complete classification ​of the prefix fragments of FOL from the point of view of the decidability of satisfiability is in: 
-(Wiley 1986), out of print but available online +  *"The Classical Decision Problem",​ Boerger, Graedel, and Gurevich, Springer 1997.
-with the latest revisions at  +
-\verb|http://​www.cis.upenn.edu/​~jean/​gbooks/​logic.html|+
  
-``A mathematical ​introduction to logic''​, H. B. Enderton, +The story of how mathematical logic gave birth to computer science is told best in: 
-Harcourt/​Academic Press, 1972 and 2000.+  *"​Engines of Logic: Mathematicians and the Origins of the Computer"​, Davis, 2nd edition, Norton 2001.
  
-``Introduction to mathematical logic'',​ E. Mendelson,​ +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: 
-various publishers, 1964, 1979, 1987, and 1997. +  ​*"​Probability and Random Processes", Grimmett, Stirzaker, Oxford U. Press 2001. 
- +  ​*"​Probability:​ Theory and Examples", Durrett, Thomson (Brooks/​Cole) 2005. 
-``Computability and logic'',​ G. Boolos and R. Jeffrey, +  *There is also a brief introduction to probability in chapter 2 of Koller-Friedman (mentioned below).
-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, 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 For 0-1 laws, I will consult
 +  *"​Elements of Finite Model Theory",​ Libkin, Springer 2004.
 +  *"The Strange Logic of Random Graphs",​ Spencer, Springer 2001.
  
-``Elements of Finite Model Theory'',​ Libkin, Springer 2004, +For the logic of independence in Bayesian and Markov networks I will follow selected sections from: 
- +  ​*"​Probabilistic Graphical Models", Koller, Friedman, MIT Press 2009.
-and +
- +
-``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.+