Lògica a la Informàtica

Esteu aquí

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació)
Requisits
  • Prerequisit: EDA
  • Corequisit: PROP
Departament
CS
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 suguretat, privacitat o eficiència). Aquesta assignatura proporciona una base sòlida de lògica per informàtics. S'estudien en profunditat les dues lògiques més importants, la proposicional i la de primer ordre. Al laboratori es resolen eficaçment diversos tipus de problemes pràctics mitjançant tècniques lògiques, com ara SAT i la programació lògica amb i sense restriccions.

Professors

Responsable

  • Robert Lukas Mario Nieuwenhuis ( )

Altres

  • Albert Oliveras Llunell ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Tècniques

Competències tècniques comunes

  • CT1 - Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
    • CT1.1A - Demostrar coneixement i comprensió dels conceptes fonamentals de la programació i de l'estructura bàsica d'un computador. CEFB4. Coneixement dels fonaments de l'ús i de la programació dels computadors, dels sistemes operatius, de les bases de dades i, en general, dels programes informàtics amb aplicació a l'enginyeria.
    • CT1.2C - Interpretar, seleccionar i valorar conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica i la seva aplicació a partir dels fonaments matemàtics, estadístics i físics necessaris. CEFB3. Capacitat per a comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per al tractament automàtic de la informació mitjançant sistemes computacionals i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
  • CT2 - Utilitzar d'una manera apropiada teories, procediments i eines en el desenvolupament professional de l'enginyeria informàtica en tots els seus àmbits (especificació, disseny, implementació, desplegament -implantació- i avaluació de productes) de manera que es demostri la comprensió dels compromisos adoptats a les decisions de disseny.
    • CT2.3 - Dissenyar, desenvolupar, seleccionar i avaluar aplicacions, sistemes i serveis informàtics i, al mateix temps, assegurar-ne la fiabilitat, la seguretat i la qualitat en funció de principis ètics i de la legislació i la normativa vigents.
  • CT4 - Demostrar coneixement i capacitat d'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i la complexitat dels algorismes
    • CT4.1 - Identificar les solucions algorísmiques més adequades per a resoldre problemes de dificultat mitjana.
    • CT4.2 - Raonar sobre la correcció i l'eficiència d'una solució algorísmica.
    • CT4.3 - Demostrar coneixement i capacitat d'aplicació dels principis fonamentals i de les tècniques bàsiques dels sistemes intel·ligents i de la seva aplicació pràctica.
  • CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
    • CT5.1 - Triar, combinar i explotar diferents paradigmes de programació, en el moment de construir software, tenint en compte criteris com la facilitat de desenvolupament, l'eficiència, la portabilitat i la mantenibilitat.
    • CT5.2 - Conèixer, dissenyar i utilitzar de forma eficient els tipus i les estructures de dades més adients per a la resolució d'un problema.
    • CT5.3 - Dissenyar, escriure, provar, depurar, documentar i mantenir codi en un llenguatge d'alt nivell per a resoldre problemes de programació aplicant esquemes algorísmics i utilitzant estructures de dades.
    • CT5.4 - Dissenyar l'arquitectura dels programes utilitzant tècniques d'orientació a objectes, de modularització i d'especificació i implementació de tipus abstractes de dades.

Competències Transversals

Raonament

  • G9 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.
    • G9.3 - Capacitat crítica, capacitat d'avaluació.

Tercera llengua

  • G3 - Conèixer l'idioma anglès amb un nivell adequat de forma oral i escrita, i en consonància amb les necessitats que tindran els graduats i les graduades en Enginyeria Informàtica. Capacitat de treballar en un grup multidisciplinar i en un entorn multilingüe i de comunicar, tant per escrit com de forma oral, coneixements, procediments, resultats i idees relacionats amb la professió d'enginyer tècnic en informàtica.
    • G3.2 - Estudiar amb materials escrits en anglès. Redactar un informe o un treball de tipus tècnic en anglès. Participar en una reunió tècnica en anglès.

Competències Tècniques de cada especialitat

Especialitat computació

  • CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
    • CCO1.1 - Avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin dur a la seva resolució, i recomanar, desenvolupar i implementar la que garanteixi el millor rendiment d'acord amb els requisits establerts.
  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.1 - Demostrar coneixement dels fonaments, dels paradigmes i de les tècniques pròpies dels sistemes intel·ligents, i analitzar, dissenyar i construir sistemes, serveis i aplicacions informàtiques que utilitzin aquestes tècniques en qualsevol àmbit d'aplicació.
    • CCO2.2 - Capacitat per a adquirir, obtenir, formalitzar i representar el coneixement humà d'una forma computable per a la resolució de problemes mitjançant un sistema informàtic en qualsevol àmbit d'aplicació, particularment en els que estan relacionats amb aspectes de computació, percepció i actuació en ambients o entorns intel·ligents.
  • CCO3 - Desenvolupar les solucions informàtiques que, considerant l'entorn d'execució i l'arquitectura del computador sobre el qual s'executen, aconsegueixin el millor rendiment.
    • CCO3.1 - Implementar codi crític seguint criteris de temps d'execució, eficiència i seguretat.
    • CCO3.2 - Programar considerant l'arquitectura hardware, tant en asemblador com en alt nivell.

Objectius

  1. Conéixer el concepte de què és una lògica, en termes de sintaxi (què és una fórmula F), i semàntica (què és una interpretació I, i quan una I satisfà una F).
    Related competences: G9.3, CCO2.1, CCO2.2,
  2. Conéixer la definició (sintaxi i semàntica) de dues lògiques: la proposicional i la de primer ordre. Entendre, escriure i manipular ágilment fórmules en les dues lògiques, amb especial émfasi a les aplicacions a l'informàtica.

    Related competences: G9.3, CCO2.1, CT4.1, CT4.2, CCO2.2, CT4.3,
  3. Conéixer els conceptes de tautologia/validesa, contradicció, conseqüència i
    equivalència lògiques (de forma independent de la lògica concreta), com s'utilitzen per a formalitzar problemes pràctics a l'informàtica, i com es redueixen al problema de satisfactibilitat.
    Related competences: G9.3, G3.2, CCO1.1, CCO2.1, CT4.1, CT4.2, CCO2.2, CT2.3,
  4. Conéixer els mètodes de deducció per a determinar les propietats de l'objectiu previ de major relevància a la informàtica: Davis-Putnam, i resolució; la seva correcció i completesa respecte la definició de la lògica. Ser capaç d'aplicar a mà resolució i Davis-Putnam sobre exemples pràctics abordables, i saber utilitzar la resolució com a mecanisme de còmput (càlcul de respostes).
    Related competences: G9.3, G3.2, CCO1.1, CCO2.1, CT4.1, CT4.2, CCO2.2, CT2.3,
  5. Saber aplicar els fonaments lògics a algunes de les aplicacions, cada cop més abundants, a la informàtica dels mètodes deductius: fonaments de la programació lògica (Prolog), bases de dades deductives, circuits, problemes de planificació, etc. Saber expressar alguns problemes pràctics NP-complets (sudokus, horaris, problemes de grafs, circuits) com a problemes de satisfacció de lògica proposicional, i resoldre-ls amb un SAT solver.
    Related competences: G9.3, CT1.2C, G3.2, CCO1.1, CCO2.1, CT4.1, CT4.2, CT5.2, CT5.4, CCO2.2, CCO3.1, CCO3.2, CT4.3, CT5.1, CT5.3, CT1.1A, CT2.3,
  6. Saber expressar problemes diversos utilitzant el llenguatge
    Prolog, i entendre les extensions "extra-lògiques" del Prolog
    incloses les dels diferents sistemes de restriccions.
    Related competences: G9.3, G3.2, CCO2.1, CT4.1, CT4.2, CT5.2, CCO2.2, CCO3.1, CT4.3, CT5.1,

Continguts

  1. Introducció i motivació:
    -Importància de la lògica a la informàtica. Exemples. Lògica informàtica vs lògica matemàtica. Què és una lògica? Objectius de l'assignatura. Alguns exemples de problemes. Com els resoldríem amb les tècniques vistes a assignatures prèvies? Quant de temps ens costaria? Què en sabríem de les garanties de fiabilitat?
  2. Definició de la Lògica Proposiciónal
    Sintaxi i semàntica de la LP. Satisfacció, tautologia, conseqüència i equivalència. Tots aquests problemes es poden expressar com a SAT. Poder expressiu: quines coses es poden modelar? Exercicis sobre: inducció, llegibilitat única de fórmules, formalització de problemes, comptatge (de fórmules, interpretacions, etc.). Problemes de conseqüència i equivalència lògiques, intuició sobre cost computacional polinòmic i exponencial (taules de veritat), cost lineal d'avaluar una fórmula, entre altres.
  3. Deducció en Lògica Proposicional
    Formes normals, literals i clàusules. Algorisme de Davis-Putnam-Logemann-Loveland (DPLL) a partir de taules de veritat i arbres de decisió. La pila explícita de Backtracking. Com expressar problemes com a SAT i com utilitzar SAT solvers. Intuició sobre problemes NP i NP complets. Sistemes deductius: propietats de correctesa, completesa, i completesa refutacional. Resolució: clausura sota resolució. Exercicis sobre formes normals, cost de les transformacions, relació amb circuits digitals, deducció per resolució i DPLL, i formulació de problemes com a SAT: sudokus, vertex cover, confecció d'horaris, hitting set...
  4. Definició de la Lògica de Primer Ordre
    Sintaxi i semàntica de la LPO. Fórmules tancades. Poder expressiu i decidibilitat. La LP com a cas particular de la LPO. Lògica de primer ordre amb igualtat i teories. Exercicis sobre llegibilitat única de fórmules, formalització de problemes, comptatge (de fórmules, interpretacions, etc.), problemes de conseqüència i equivalència lògiques, models finits i infinits, etc.
  5. Deducció en Lògica de Primer Ordre
    Formes normals, literals i clàusules. Pas a forma clausal, Skolemització. Unificació, unificador simultani, les regles d'unificació: acabament i correcció. Resolució i factorització: correctesa i completesa refutacional. No-terminació: procediments de decisió i de (co-)semi-decisió. Exercicis de formalització, pas a forma clausal, unificació, resolució, i problemes sobre (semi-)decisió aplicats als programes i la compilació.
  6. Programació Lògica
    Càlcul de respostes: com trobar els valors de les variables X que fan que F satisfaci una expressió de la forma "Existeix X tal que G"? L'estratègia SLD de resolució per clàusules de Horn. Completesa pel càlcul de respostes. La pila de backtracking: què fa l'operador de tall? Altres aspectes extra-lògics: la negació, l'aritmètica predefinida, l'entrada-sortida. Exercicis de resolució amb càlcul de respostes, sobre la teoria i el comportament de programes Prolog, i de confecció de programes Prolog.
  7. Programació amb restriccions
    Com obtenir la flexibilitat i rapidesa en l'expressió del problema característica de la programació lògica, i a la vegada tenir l'eficiència de l'ús de resoledors especialitzats per als enters, els reals, dominis finits, etc.? CLP(X) i dominis. Maneres de reduir l'espai de cerca. Problemes lògics amb restriccions d"altres dominis. Exemple: assignació de recursos, horaris. Cerca de solucions òptimes amb CLP.

Activitats

Activitat Acte avaluatiu


Aprenentatge del tema Introducció i motivació

Els estudiants segueixen l'explicació del pofessor, responen les seves preguntes, fan preguntes, i intervenen a la discusió proposada.
Objectius: 1
Continguts:
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Aprenentatge del tema Definició de la Lògica Proposiciónal

Els estudiants fan els exercicis proposats, segueixen l'explicació del pofessor, fan preguntes, responen les seves preguntes i intervenena la discusió proposada.
Objectius: 1 2
Continguts:
Teoria
4h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Aprenentatge del tema Deducció en Lògica Proposicional

Els estudiants fan els exercicis proposats, que inclouen tant exercicis de problemes a classe com els de laboratori per modelar i resoldre problemes amb aquesta lógica i, en particular, amb SATsolvers. Addicionalment segueixen l'explicació del pofessor, fan preguntes, responen les seves preguntes i intervenen a la discussió proposada.
Objectius: 1 2 3 4 5
Continguts:
Teoria
6h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
1h
Aprenentatge autònom
12h

Aprenentatge del tema Definició de la Lògica de Primer Ordre

Els estudiants fan els exercicis proposats, segueixen l'explicació del pofessor, responen les seves preguntes i intervenen a la discusió proposada.
Objectius: 1 2 3 4 5
Continguts:
Teoria
6h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Examen parcial

Examen parcial escrit sobre la primera meitat de la materia de teoria. Es fa en hores de classe.
Objectius: 1 2 3 4 5
Setmana: 9
Tipus: examen final
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Aprenentatge del tema Deducció en Lògica de Primer Ordre

Els estudiants fan els exercicis proposats, que inclouen tant exercicis de problemes a classe com els de laboratori per modelar iresoldre problemes amb aquesta lògica, Segueixen l'explicació del pofessor, responen les seves preguntes i intervenen a la discusió proposada.
Objectius: 1 2 3 4 5
Continguts:
Teoria
4h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
1h
Aprenentatge autònom
10h

Aprenentatge del tema Programació Lògica

Els estudiants fan els exercicis proposats, que inclouen tant exercicis de problemes a classe com els de laboratori per resoldre problemes. Segueixen l'explicació del pofessor, responen les seves preguntes i intervenen a la discusió proposada.
Objectius: 4 5 6
Continguts:
Teoria
5h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
1h
Aprenentatge autònom
11h

Aprenentatge del tema Programació amb restriccions

Els estudiants fan els exercicis proposats, que inclouen tant exercicis de problemes a classe com els de laboratori per resoldre problemes industrials reals: assignació de recursos, confecció d'horaris. Segueixen l'explicació del pofessor, responen les seves preguntes i intervenen a la discusió proposada.
Objectius: 5 6
Continguts:
Teoria
4h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
1h
Aprenentatge autònom
12h

Examen final

Examen escrit, amb dos parts, sobre les dues meitats de la materia de teoria.
Objectius: 1 2 3 4 5 6
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
14h

Metodologia docent

La principal característica de la metodologia docent és l'utilització de materials docents accessibles a través de la web, específicament dissenyats per a l'auto-aprenentatge de l'assignatura. Aquest material (apunts de teoria, problemes, problemes resolts, exemples de pràctiques de laboratori, software de SAT i de programació lógica sense i amb restriccions) ens permet replantejar el model de les classes, de manera que el tradicional model de classes magistrals
desapareix en gran mesura.

Així:

1. Es planteja la classe com un inici de l'estudi i el treball que l'estudiant ha de continuar i aprofundir pel seu compte.

2. Es proporciona el màxim de materials de qualitat (apunts, exercicis resolts, exercicis per fer, referències bibliogràfiques).

3. S'aprofiten al màxim les classes per a fomentar la motivació de l'estudiant (amb exemples, debats, comentaris, etc.) i es transmet
l'enfocament i les intuïcions darrere les definicions, propietats i
tècniques tractades.


Encara que no hi ha classes específiques de només problemes, a les sessions de classe s'intercalen teoria i problemes de manera flexible segons les necessitats del temari a cada moment. No convé fixar de manera rígida quantes i quines hores setmanals seran de problemes.

Al laboratori es fomentarà el treball autònom per part de l'estudiant, i el paper del professor, que sempre estarà present a les 2 hores setmanals de laboratori, serà en gran mesura de consultor/avaluador dels treballs que l'estudiant realitzarà de forma autònoma a partir d'un enunciat prou específic.

Mètode d'avaluació

Hi haurà un nota de teoria T amb un pes del 60%, obtinguda calculant la mitjana entre la primera meitat de la matèria (T1) i de la resta (T2). Aquestes notes s'obtenen amb dos exàmens escrits: el parcial (P) sobre la materia de T1, i el final, sobre T1 i T2. La nota de l'examen parcial allibera d'examinar-se de T1 a l'examen final, i en tot cas comptarà la millor nota de T1 entre la del parcial i la del final.

La nota de laboratori (40%) s'obtindrà fent la mitjana de les notes de dos petits exàmens davant de l'ordinador. Aquests exàmens avaluaràn la capacitat de l'estudiant de realitzar els exercicis fets a les sessions de laboratori, i normalment consistiràn en fer alguna extensió d'alguna pràctica lliurada previament pel mateix estudiant.

A com a minim dues preguntes de cada exàmen escrit, i a com a minim dos dels exericis de labori a entregar, a banda de la nota normal de la pregunta o exercici, adicionalment es donarà una nota de la competència transversal de Raonament.
La mitjana aritmètica de totes les notes de la competència transversal donarà una nota de
0 a 10 que es traduirà a A/B/C/D segons els intervals [0,5) -> D, [5,6) -> C, [6,8) -> B, [8,10] -> A.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Coneixements bàsics de matemátiques (conjunts, funcions, relacions, conteig, combinatòria molt bàsica i técniques de demostració: inducció, reducció a l'absurd, contrarrecíproc...).
Coneixements d'algorismica, programació (C++) i estructures de dades.
Coneixements de circuits digitals i funcions Booleanes.
Capacitats de treball autònom.