Pontifı́cia Universidade Católica do Rio Grande do Sul
Faculdade de Informática - Teoria da Computação
profa. Beatriz R. Tavares Franciosi - 2015/II
Materiais: Leituras/Vı́deos
Bibliografia básica
1. HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. I NTRODUÇ ÃO À TEORIA
DE AUT ÔMATOS , LINGUAGENS E COMPUTAÇ ÃO . Elsevier, 2003. Sitedolivro:http://
infolab.stanford.edu/˜ullman/ialc.html
2. LEWIS, Harry. R.; PAPADIMITRIOU, Christos. H. E LEMENTOS DE T EORIA DA C OMPUTAÇ ÃO.
2. ed. Porto Alegre: Bookman, 2000.
3. BOOLOS, George S.; JEFFREY, Richard C. C OMPUTABILITY AND LOGIC. 3. ed. Cambridge
University Press, 1990.
Bibliografia complementar
1. CARNIELLI, Walter; EPSTEIN, Richard L. C OMPUTABILIDADE , FUNÇ ÕES COMPUT ÁVEIS ,
L ÓGICA E OS FUNDAMENTOS DA MATEM ÁTICA . São Paulo: UNESP, 2006.
2. DIVERIO, Tiaraju. A.; MENEZES, Paulo. F. B. T EORIA DA COMPUTAÇ ÃO : M ÁQUINAS UNI VERSAIS E COMPUTABILIDADE . 2. ed. Porto Alegre: Sagra-Luzzatto, 2000.
3. BRAINERD, Walter S.; LANDWEBER, Lawrence H. T HEORY OF COMPUTATION. New York:
John Wiley, c1974.
4. CORMEM, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L. I NTRODUCTION TO
ALGORITHMS . Cambridge: The MIT Press, 1990.
5. GAREY, Michael R.; JOHNSON, David S. C OMPUTERS AND INTRACTABILITY: A GUIDE TO
THE THEORY OF NP- COMPLETENESS . New York: W. H. Freeman, 1979.
Livros
1. Aspectos Teóricos da Computação. LUCCHESI, C. Projetos Euclides.
2. Matemática concreta: fundamentos para ciência da computação. GRAHAM, R.L.;
KNUTH, D.E.; PATASHNIK, O. 2a. edição, Rio de Janeiro: LTC Editora, 1995.
3. Matemática discreta para ciência da computação. STEIN, C.; DRUSDALE, R.L.; BOGART, K. São Paulo: Pearson Education Brasil, 2013.
4. Matemática discreta para computação e informática. MENEZES, P.B. Porto Alegre: Editora Bookman, 2013.
1
5. Models of computation: exploring the power of computing. SAVAGE, J.E. , Virginia
Tech. http://www.modelsofcomputation.orghttp://cs.brown.edu/people/jes/
book/
6. Alice no paı́s do quantum. GILMORE, R. , Rio de Janeiro: Jorge Zahar Editor, 1998.
7. An introduction to functional programming through lambda calculus. MICHAELSON,
Greg., Dover Publications, 2011.
8. Discrete mathematics and functional programming. VANDRUNEN, Thomas., Franklin,
BEEDLE & Associates Inc. October, 2012.
9. Elements of ML programming ML 97 edition. ULLMAN, Jeffrey. 2 ed. Prentice-Hall.
10. Espaço-tempo e além. TOBEN, B.; WOLF, F.A., São Paulo: Editora Pensamento-Cultrix,
1982.
11. Functional thinking. FORD, Neal. , 1 ed. O’Reilly Media, 2014.
12. Lambda calculi: A guide for computer scientists. HANKIN, Chris. Oxford University
Press, 1995. 2. PIERCE, Benjamin. Types and programming languages. MIT Press, 2002.
13. ML for the working programmer. PAULSON, L. C., 2 ed. Cambridge University Press.
14. The haskell road to logic, maths and programming. DOETS, Kees; EIJCK, Jan van., 2
ed. College Publications, 2004.
15. An introduction to the analysis of algorithms. SEDGEWICK, R.; FLOAJOLET, P. USA:
Addison-Wesley, 2013 http://aofa.cs.princeton.edu
Textos
1. A crise nos fundamentos da matemática e a Teoria da Computação: Qual é a natureza da
verdade matemática? http://www.cic.unb.br/docentes/pedro/trabs/acrise.
htm
2. Discrete mathematics for computer science. In: Lecture 42, CS 70, Fall 2006. http://
www-inst.eecs.berkeley.edu/˜cs70/fa06/lectures/computability/lec30.pdf
(paradoxos)
3. Qual é a natureza da verdade matemática? http://www.cic.unb.br/docentes/pedro/
trabs/acrise.htm
4. Mathematic problems. David Hilbet. In: Congresso Internacional de Matemáticos em Paris,
1900. http://www.clarku.edu/˜djoyce/hilbert/, http://www-history.mcs.
st-andrews.ac.uk/Extras/Hilbert_Problems.html
5. Theory of Computation: MIT Group http://toc.csail.mit.edu/about
6. Turing Machines First published Thu Sep 14, 1995; substantive revision Tue Jun 26, 2012
http://plato.stanford.edu/entries/turing-machine/
2
7. Will Computers Redefine the Roots of Math? Quanta Magazine https://www.quantamagazine.
org/20150519-will-computers-redefine-the-roots-of-math/
8. Computing machinery and intelligence. (prêmio Turing) http://www.loebner.net/Prizef/
TuringArticle.html
9. Tese de Church-Turing. SOBRINHO, J. Z. In: Revista Matemática Universitária, USP, n 6,
dezembro de 1987, pp 1-23.
10. Tese de Turing (problema da parada) http://www.abelard.org/turpap2/tp2-ie.
asp
11. The Church-Turing Thesis. COPELAND, B. Jack The Stanford Encyclopedia of Philosophy
(Fall 2008 Edition), Edward N. Zalta (ed.), 2008. http://plato.stanford.edu/archives/
fall2008/entries/church-turing/
12. The genius who gave us the future [arquivo pdf], http://plato.stanford.edu/entries/
turing/, http://ww1.inf.pucrs.br/alunos/material_apoio/CC/Palestra-Turing-POA.
pdf, http://www.cs.princeton.edu/˜chazelle/courses/BIB/turing-intelligence.
pdf, http://www.loebner.net/Prizef/TuringArticle.htm, http://www.princeton.
edu/turing/, https://royalsociety.org/exhibitions/century-british-innovation/
universal-machine/, http://www.turing.org.uk/, http://nolabirinto.com/
ciencia/4-trabalhos-turing/, http://www.reading.ac.uk/news-and-events/
release/PR583836.aspx, http://www.ime.usp.br/˜vwsetzer/Turing-teatro.
html, Turing e o computador em 90 minutos. Paul Strathern, São Paulo: Editora Zahar,
2000.
13. On computable numbers, with an application to the entscheidungsproblem. http://www.
abelard.org/turpap2/tp2-ie.asp
14. Recontando a computabilidade. Isabel-Edward-Henrique [arquivo pdf]
15. An overview of computational complexity. Stephen A. Cook In: Communications of the ACM,
vol.26, n.6, 1983. [arquivo pdf]
16. Complexity theory: a modern approach. ARORA, Sanjeev; BARAK, Boaz Cambridge University Press, 2009 [sections 1.4, 1.7]
17. The complexity of loop programs. Albert Meyer e Dennis Ritchie. [arquivo pdf]
18. The status of the P versus NP problem. Lance Forton, publicado em Communications of the
ACM, vol.52, n.9, September 2009. http://www.win.tue.nl/˜gwoegi/P-versus-NP.
htm, http://www.cs.princeton.edu/courses/archive/spr09/cos522/SipserNP.
pdf
Manuais
1. JFLAP http://www.cs.duke.edu/csed/jflap: software para visualização/simulação
de diagramas de estados.
3
Vı́deos
1. Somos maduros o bastante para conviver com as incertezas?
Fonte: Série da BBC Four: Conhecimentos Perigosos (Parte I:http://www.dailymotion.
com/video/xsppob_conhecimento-perigoso-1-2_tech, Parte II:http://www.dailymotion.
com/video/xsp5tq_conhecimento-perigoso-2-2_tech)
2. O jogo da imitação. [filme]
Sites
1. Biografia de Bolzano http://www.ontology.co/bolzanob.htm
2. Biografia de Cantor https://pt.wikipedia.org/wiki/Georg_Cantor
3. Ciência da computação http://walfredo.dsc.ufcg.edu.br/textos-comp/: site mantido pelo prof. Walfredo Cirne, Universidade Federal de Campo Grande
4. Computation theory http://www.cl.cam.ac.uk/teaching/1213/CompTheory/: site
mantido pelo pro. Andrew Pitts, University of Cambridge
5. Computer science theory http://www.cs.berkeley.edu/˜vazirani/f06cs70.html:
site da disciplina CS70, ministrada pelos professores Christos Papadimitriou e Umesh Vazirani, Princenton University
6. Técnicas de prova http://www-inst.eecs.berkeley.edu/%7Ecs70/fa06/lectures/
lecture02-2.pdf : site da disciplina CS70, ministrada pelos professores Christos Papadimitriou e Umesh Vazirani, Princeton University
7. Teoria da computação http://theoryofcomputing.org/index.html: site do Journal
da ACM SIGACT
8. Teoria da computação do MIT/USA http://theory.csail.mit.edu/
9. Theory of computation http://www.cs.ucc.ie/˜dgb/courses/toc/lectures.html:
site de disciplina, mantido pelo prof. Derek Bridge, Department of Computer Science, University College Cork
10. Theory of computation http://theory.csail.mit.edu/: site do grupo de pesquisa
sobre Teoria da Computação, MIT/USA
11. A Turing Machine in the classic style http://aturingmachine.com
12. ACM Turing Award http://amturing.acm.org/
13. Máquina de Turing http://aturingmachine.com: site mantido por Mike Daveya
14. Tese de Church-Turing http://plato.stanford.edu/entries/church-turing/: site
mantido pela Universidade de Stanford
15. Função recursiva http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm:
site mantido por Alan Gauld (exemplos de código em Python)
4
16. Primer on Recursion http://echorand.me/writings/ http://amitksaha.files.
wordpress.com/2009/05/recursion-primer.pdf: site mantido por Amit (cartilha sobre recursão)
17. Wolfram Demonstrations Projectshttp://demonstrations.wolfram.com/TreeFormOfRecursiveFuncti
função recursiva - animação
18. Wolfram Demonstrations Projectshttp://mathworld.wolfram.com/Recursion.html
: recursão
5