Differences

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

--- lopro [2011/09/21 18:39]
vkuncak created
+++ lopro [2011/09/25 14:32]
val.tannen
@@ Line 1: / Line 1: @@
-====== Logic and Probability ======
+====== EPFL Fall 2011: Logic and Probability ======
 **Doctoral course by Val Tannen**
+Lecture notes 1 [[http://www.cis.upenn.edu/~val/LogicProbEPFL2011files/ln1.pdf|(pdf)]]
+//Course Materials//
+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 will also make available my own notes on computability on the website.
+There many textbooks on logic but let me recommend my favorites:
+``Logic for Computer Science'', J. Gallier,
+(Wiley 1986), out of print but available online
+with the latest revisions at
+\verb|http://www.cis.upenn.edu/~jean/gbooks/logic.html|
+``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, 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,
+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.