Curs 2015-16

Lògica Computacional

Titulació: Codi: Tipus:
Grau en Enginyeria Informàtica 21422 Obligatòria 2n curs
Grau en Enginyeria Telemàtica 22606 Optativa
Grau en Enginyeria en Sistemes Audiovisuals 22672 Optativa

 

Crèdits ECTS: 4 Dedicació: 100 hores Trimestre: 3r

 

Departament: Dept. de Tecnologies de la Informació i les Comunicacions
Coordinador: Héctor Geffner
Professorat:

Teoria: Héctor Geffner

Pràctiques: Oussam Larkem

Seminaris: Oussam Larkem, Filippos Kominis

Idioma:

Material: Anglés, Castellá

Teoria: Héctor Geffner (castellá)

Pràctiques: Oussam Larkem (anglés/castellá)

Seminaris:  (anglés/castellá), Filippos Kominis (anglés/castellá)

Horari:
Campus: Campus de la Comunicació - Poblenou

 

Presentació de l'assignatura

L'assignatura Lògica Computacional és una assignatura obligatòria que
s'ofereix durant el grau en enginyeria en informàtica, formant part del
segon curs de aquest grau. En l'assignatura s'estudien els aspectes
deductius i algorísmics tant de la lògica proposicional com de la lògica de
predicats, i així com els seus problemes computacionals computacionals. L'assignatura té un component teòric i un altre pràctic. Dintre del component teòric l'èmfasi
està en la comprensió dels conceptes a nivell intuïtiu i de la utilització de
llenguatge matemàtic.

L'assignatura està composta de tres activitats principals: classes de teoria,
seminaris i laboratoris. En les classes de teoria s'introdueixen els conceptes
formals i es mostren exemples de la seva aplicació. En els seminaris els
alumnes resolen petits problemes. Cada problema correspon a un dels
conceptes introduïts en classe de teoria. En els laboratoris es presenten
problemes de més complexitat i de caràcter més computacional perquè
els alumnes tinguin l'oportunitat de posar en pràctica els conceptes
apresos.

Objectius d'aprenentatge

L'objectiu de l'assignatura és estendre aspectes deductius i algorísmics de la
lògica proposicional i de predicats, i així com els seus problemes computacionals computacionals. Així mateix, els estudiants haurien de desenvolupar
competències per a entendre les diferències entre els diversos tipus de
lògica i identificar el millor formalisme per especificar diferents problemes i poder solucionar-los de forma computacional.

 

Prerequisits

Els coneixements previs per al seguiment de l'assignatura són certes nocions
de matemàtiques bàsiques adquirides en l’ensenyament secundari
obligatori i durant els primers tres cursos dels estudis. En particular, els
coneixements previs requerits per a l'assignatura són:

• Nocions algebraiques bàsiques: funcions, conjunts i operacions
elementals sobre conjunts, relacions d'equivalència.
• Nocions bàsiques de lògica matemàtica: relacions, conectors lògics.
• Aritmètica bàsica.
• Capacitat bàsica per a comprendre i escriure expressions
matemàtiques a nivell elemental.

 

Competències

L’objectiu fonamental de l'assignatura és que els alumnes adquireixin els
idees fonamentals relacionats amb els aspectes deductius i algorísmics
de la lògica proposicional i de predicats.

Competències transversalsCompetències específiques

Instrumentals

1. Capacitat de raonar a nivell abstracte

2. Habilitats cognitives

3. Sentit comú

Interpersonals

4. Competència de comunicació

Sistèmiques

5. Capacitat d’identificar la millor
metodologia per resoldre un
problema.

6. Capacitat de solucionar
problemes combinant de manera
nova i no trivial elements ja coneguts

7. Capacitat de generar altres idees.

 

 

1. Capacitat d’entendre a nivell intuïtiu i
formal els diferents aspectes de la lògica
proposicional i de predicats: sintaxi,
semàntica i la seva aplicació a diferents
problemes en informàtica.

2. Capacitat d’aplicar els coneixements
adquirits en contextos pràctics.

 

Avaluació

En l’avaluació continuada es té en compte cada una de les tres activitats
que constitueixen l’assignatura: classes de teoria, laboratoris i seminaris:

T: l’avaluació de la teoria mitjançant un examen final
L: l’avaluació dels laboratoris amb les pràctiques de programació.
S: l’avaluació dels seminaris

En l'avaluació continuada, cal aprovar el laboratori i també aprovar-se la suma de l'avaluació dels seminaris mes l'examen final. És a dir,

 

Nota Final = 0,6 * T + 0,2 * L + 0,2 * S

L’examen de teoria es realitzarà sobre els continguts desenvolupats a classe
de teoria i als seminaris. És un examen escrit i individual que avalua totes les
competències desenvolupades al llarg de l’assignatura.

En els laboratoris es realitzen un sèrie de pràctiques que posen a prova la
capacitat dels alumnes de aplicar la teoria en forma de programes en un
ordinador. Les pràctiques es realitzen en parella, de manera que els
alumnes hagin de cooperar i saber comunicar-se per resoldre els
problemes.

Abans de cada seminari es presentaran problemes als alumnes per tal que ells els resolguin abans de la sessió, com una preparació prèvia al seminari. Aquests problemes corresponen a conceptes o coneixements tractats a classe de teoria. Es demanarà als alumnes que presentin les seves solucions a la pissarra o per escrit. Com a part de l'avaluació, es realitzaran dues proves curtes, i dues tasques per lliurar per escrit.

En cas de no aprovar l’assignatura, l’alumne té dret a una convocatòria en
el mes de juliol, però nomès si havia aprovat el laboratori (L). La nota
d’aquesta convocatòria s’obtindrà en un examen.

Nota Juliol = 1,0*T+0*L +0*S (si havia aprovat L)

 

Continguts

1. Lògica: Què és, història, usos en la informàtica. Concepte de derivació formal. Exemples de les matemàtiques.

2. Lògica proposicional.

1. Llenguatge formal, formules.
2. Modelació.
3. Teoria de proves: sistema de deducció natural per a la lògica proposicional. Proves, derivabilitat.
4. Semàntica: taules de verita. Satisfactibilidad i Conseqüència Lògica. Tautologies.
5. Formes Normals. Resolució. Clausulas de Horn. SAT i SAT solvers.

3. Lògica de predicats.

1. Motivació. Llenguatge formal, formules.
2. Modelació.
3. Teoria de proves per a lògica de predicats: sistema de deducció natural. Proves, derivabilitat.
4. Semàntica: interpretacions de formules de la lògica de predicats.
5. Satisfactibilidad i Conseqüència Lògica. Resolució en lògica de predicats.

 

Metodologia

El procés habitual d’aprenentatge comença amb una sessió de teoria en la
que es presenten certs fonaments teòrico-pràctics. Aquesta activitat es realitza
amb tot el grup d’estudiants. L’estudiant haurà de complementar aquesta
activitat amb una lectura detinguda dels seus propis apunts i el material
addicional que el professor hagi proporcionat. Per exemple, una sessió de
teoria de 2 hores, convenientment aprofitades, requerirà un treball addicional
fora de l’aula d’1 hora per part de l’estudiant.

Posteriorment es realitzaran algunes sessions d’exercicis, en les quals l’estudiant
posa en pràctica els conceptes i tècniques presentades a la sessió de teoria,
mitjançant la resolució de petits problemes. Per als primers exercicis de la sessió
es pot proporcionaran les solucions, però per la resta no. L’objectiu és que consolidi
els fonaments per tal que posteriorment pugui resoldre problemes de major
complexitat. Per aquesta activitat el grup es divideix en quatre i es realitza en
quatre grups petits d’estudiants.

El següent pas en el procés d’aprenentatge és la sessió de pràctiques. En ella
es proposen uns problemes de mida més gran que requereixen integrar
diferents conceptes i tècniques. Aquesta activitat es realitza per parelles, en grups d’uns 20 estudiants, i es pressuposa que continua fora de l’aula.

Estan previstes 18h de teoria, 12h de seminari, i 6h en aula de pràctica,  encara que aquesta continua fora de l'aula.

 

Recursos

Fonts d’informació per a l’aprenentatge. Bibliografia bàsica (suport paper i electrònic)

Logic in Computer Science
Michael R.A. Huth, Mark D Ryan

Cambridge University Press. 2nd edition, 2004.
Cobrim la primera part, pàgines 1-131. Excepte les secció 1.6 que farem
de manera diferent (usant el mètode DPLL).

Fonts d’informació per a l’aprenentatge. Bibliografia complementària (suport paper i electrònic)

Mathematical Logic for Computer Science
Mordechai Ben-Ari
Springer (2003).

Logic and its Applications
Edmund Burke, Eric Foxley
Prentice Hall (1996)

Fonts d’informació per a l’aprenentatge. Bibliografia de reforç (suport paper i electrònic)

Recursos didàctics. Material docent de l’assignatura

Web de l’assignatura

Apunts
Col·lecció d’exercicis (amb solució)

Enunciats de les pràctiques

Recursos didàctics. Materials i eines de suport

http://www.diveintopython.org
http://www.swi-prolog.org/