Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
lopro [2011/09/25 14:14] val.tannen |
lopro [2011/09/25 14:32] 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 | + | //Course Materials// |
- | Truth, proof, and computation: some basic results about first-order logic | + | Old lecture notes on computability [[http://www.cis.upenn.edu/~val/LogicProbEPFL2011files/compNotes.pdf|(pdf)]] |
- | A bit of the story of how Mathematical Logic (and Electronic Technology) gave birth to Computer Science. | + | |
- | Part I: Probability of Logic | + | "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)]] |
- | Random graphs and random structures | + | //Syllabus// |
- | 0-1 laws | + | |
- | Queries on probabilistic databases | + | |
- | Part II: Logic of Probability | + | *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. | ||
- | Pearl-Paz logics for reasoning about probabilistic (in)dependence | + | *Part I: Probability of Logic |
- | Reasoning about independence in Bayesian and Markov networks; the Hammersley-Clifford theorem | + | *Random graphs and random structures |
- | Reasoning about independence in relational graphical models (PRMs and RMNs) | + | *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. | ||
- | My lecture notes on Computability |