ALCC. Segon quadrimestre '05-'06
En aquesta pàgina podreu trobar informació sobre el
quadrimestre actual, tot el material de l'assignatura i alguns
enllaços relacionats. La col·lecció d'exercicis i
els apunts de classe s'aniran actualitzant a mesura que avanci el curs;
per més claredat, les noves versions apareixeran com a avisos en
el racó de la FIB.
- Professors
- Antoni Lozano
Campus Nord, Edif. A0-Omega, despatx 233
- E-mail: antoni a lsi.upc.edu
- Consultes:
- dilluns de 16:00 a 18:00
i dijous de 11:00 a 13:00
- concertades
- per email per a consultes puntuals
- no hi haurà consultes el dia d'examen
ni el dia previ
- Calendari
- Apunts de classe
- Enunciats d'exercicis
- Enunciats d'exàmens
- Treballs voluntaris
- Guia d'estudi
- Preliminars matemàtics: capítols 0 dels llibres
de teoria de
la computació (per exemple, de Sipser)
- Alfabets, mots i llenguatges
- Problemes i algorismes
- Autòmats finits. Llenguatges regulars.
- Gramàtiques incontextuals. Llenguatges incontextuals
- Reduccions i completesa
- Màquines de Turing, tesi de Church-Turing.
- Cap 2,3 de Serna, Alvarez, Cases i Lozano
- Cap 3,4 de Sipser
- Transparències
- Indecidibilitat: El problema de l'aturada. NP-dificultat:
Satisfactibilitat de circuits
- Computability and complexity (veure Material addicional)
- Cap 4,6,8 de Serna, Alvarez, Cases i Lozano
- Alguns problemes indecidibles
- Cap 9 de Serna, Alvarez, Cases i Lozano
- Cap 5,7.4 de Sipser
- Transparències
- Mesures d'eficiència dels algorismes
- Cap 3 i 4 de Brassard i Bratley
- Apunts de S. Roura
- Alguns problemes NP-difícils
- Cap 10 de Serna, Alvarez, Cases i Lozano
- Sec 7.5 de Sipser
- Apèndix de Garey i Johnson
- "A compendium of NP Optimization Problems" (veure Material addicional)
- Algorismes voraços
- Cap 6 de Brassard i Bratley
- Arbre d'expansió mínim, cap 35 de Cormen,
Leisserson i Rivest
- Knapsack, pàg 335 y 336 de Cormen, Leisserson i
Rivest.
- Transparències
- Backtracking
- Sec 9.6 i 9.7 de Brassard i Bratley
- Sec 5.1 i 5.2 de Skiena
- Transparències
- Programació dinàmica
- Cap 8 de Brassard i Bratley
- Cap 16 de Cormen, Leisserson i Rivest
- Transparències
- Material addicional
- Informació addicional
- Existeix un servei d'impressió de pagament del CPET
accessible des de la xarxa de PCs del LCFIB. Per més detalls,
premeu aquí
- Software general:
- Gzip (GNU Zip) és
un
programa de compressió d'arxius. Tant el mateix Gzip com el
programa WinZip per a
Windows '95 poden descomprimir arxius comprimits amb gzip
- Postscript
és un format de descripció de pàgines. Hi ha
visualitzadors de postcript gratuits per a tota
mena de plataformes, i la majoria d'impressores i aplicacions de
processament de textos entenen aquest format. Per a Windows '95, Linus
i Unix es pot fer servir Ghostview
- Els documents PDF (Portable Document Format) d'Adobe es poden
llegir
mitjançant Ghostview o amb el programa Acrobat
Reader