Lògica en la Informàtica (Tardor 2022)

Resumen

La lògica juga un paper bàsic en la informàtica (bases de dades, complexitat computacional, llenguatges de programació, intel·ligència artificial, disseny i verificació de sistemes hard i soft, etc.), i és sens dubte un dels fonaments que proporcionen la maduresa i agilitat necessàries per assimilar els conceptes, llenguatges, tècniques i eines informàtiques que sorgeixin en el futur. Igual que els arquitectes i enginyers, que analitzen matemàticament les seves construccions, els informàtics necessiten analitzar les propietats lògiques dels seus sistemes mentre els dissenyen, desenvolupen, verifiquen i mantenen, especialment quan es tracta de sistemes crítics (econòmicament, o en seguretat, privacitat o eficiència).

Programa

  • Introducció i motivació

  • Definició de la Lògica Proposiciónal

  • Deducció en Lògica Proposicional

  • Definició de la Lògica de Primer Ordre

  • Deducció en Lògica de Primer Ordre

  • Programació Lògica

Pàgina de la Guia Docent de la FIB.

Professorat


Apunts

  • Sobre la lògica en general, en el Racó hi ha unes notes de classe en 6 temes, amb exercicis resolts, problemes Prolog resolts, etc. Per al correcte seguiment de l’assignatura és fonamental entendre i dominar bé aquestes apunts i exercicis bàsics.

  • Aquí teniu uns apunts amb -entre altres coses- la transformació de Tseitin a CNF equisatisfactible.

  • Breu resum sobre NP i NP-completitud (per a detalls veure els apunts de complexitat de l’assignatura EDA).

  • Vídeo (12 minuts) sobre el problema de la Transportation Company (ignora el que diu al principi sobre el confinament; això va ser a la primavera de 2020).

  • Vídeo (27 minuts) sobre Codificació de Constraints Numèrics en SAT. I aquí hi ha un breu resum escrit d’això.

  • Resum CLP en Prolog. Veure també la pàgina de swi-prolog clpfd.

Exàmens

Els enunciats dels exàmens de teoria i de laboratori són en anglès. No influeix en la nota de LI si contestes en català, castellà o english (o un mix dels tres). Però si contestes en anglès et pot pujar la nota de la competència transversal d’anglès.

Pràctiques de laboratori

Hi haurà dos exàmens presencials de laboratori davant de l’ordinador. Atenció: aquest quadrimestre hi ha setmana d’exàmens parcials, amb examen parcial de teoria de LI i el primer examen de labo de LI.

Les primeres tres pràctiques es lliuraran (via Racó) fins a les 23:59 hores del dia anterior al primer examen de laboratori, i les altres el dia abans del segon examen de laboratori. Aquestes són les dates límit de lliurament per a tot estudiant.

Important

Lliura les pràctiques a temps, fes-les personalment, i de la forma més clara i senzilla, perquè l’examen de laboratori pot consistir en implementar una modificació o ampliació de la pràctica que vas lliurar. Per això és important també conservar la pràctica que vas lliurar en la teva zona de disc en la FIB, perquè durant l’examen només tindràs accés allí a la teva pràctica.

La nota de laboratori (el 40% de la nota total) serà la mitjana dels dos exàmens de laboratori. Cada examen de laboratori tindrà diversos exercicis, en els quals serà requisit indispensable el seu correcte funcionament, i addicionalment es valorarà la simplicitat i claredat. Recomanem una forta dedicació a la teoria perquè serà difícil compensar una nota baixa de teoria mitjançant el laboratori.

Enunciats de les pràctiques