Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Lògica a la informàtica (LI)

Crèdits Dept.
7.5 (6.0 ECTS) CS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

Aquesta assignatura aprofundirà als coneixements generals de la lògica com a eina fonamental a la informàtica.

A més es desenvoluparan habilitats a algunes àrees d'aplicació que permetran a l'estudiant crear en poc temps sistemes per a la resolució de molt diversos problemes pràctics.

Es dedicarà especial atenció a la programació lògica i a la programació lògica amb restriccions.

Objectius Específics

Coneixements

  1. Conèixer els fonaments lògics de la programació lògica, de les bases de dades deductives, i d"altres aplicacions de la lògica a la informàtica, com la web semàntica o la verificació.
  2. Conèixer les tècniques i eines de programació lògica orientades al desenvolupament ràpid i flexible de sistemes per a un problema donat.
  3. Conèixer algunes de les extensions de la programació lògica orientades a l"eficiència: avaluació parcial, paral·lelització, programació lògica amb restriccions (dominis finits, booleans, reals).
  4. Conèixer algunes aplicacions crítiques en seguretat, fiabilitat o privadesa i tècniques associades: eines basades en comprovació de models, interpretació abstracta i deducció automàtica.

Habilitats

  1. Davant d"un problema pràctic concreto, ser capaç d"escollit les tècniques i eines de programació més adients.
  2. Desenvolupar algunes aplicacions pràctiques fent servir les tècniques i eines estudiades.

Competències

  1. Ser millors programadores i més eficients, a través d"un millor coneixement de les tècniques i eines avançades.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Introducció i motivació:
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 0 0 0 0 0 0 2,0
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. Tècniques basades en lògica proposicional
T      P      L      Alt    L Ext. Est    A Ext. Total 
9,0 0 6,0 0 6,0 8,0 0 29,0
Repàs de lògica proposicional.
Algoritmes: Resolució, Davis-Putnam-Logemann-Loveland, BDD's.
Eines: Prolog, Chaff, paquets de BDD's.
Programació per traducció a SAT i ús de les eines associades.
Exemples d'aplicacions: problemes d'horaris, etc.
  • Laboratori:
    Implementació a un llenguatge imperatiu (possiblement C) d'algun algoritme senzill per a SAT.
    Aprenentatge del llenguatge Prolog a nivell d'usuari.
    Implementació en Prolog d'algun problema.

3. Tècniques basades en lògica de Primer Ordre
T      P      L      Alt    L Ext. Est    A Ext. Total 
12,0 0 8,0 0 4,0 6,0 0 30,0
Repàs de lògica de primer ordre.
Algoritmes: Resolució i les seves restriccions, deducció automàtica.
Mètodes basats en resolució: programació lògica, bases de dades deductives.
  • Laboratori:
    Implementació en Prolog de problemes de deducció automàtica i de bases de dades deductives i d'altres tipus.

4. Programació Lògica
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 0 4,0 0 8,0 10,0 0 28,0
Fonaments: resolució SLD.
Optimitzacions: tipus de dades predefinits, entrada-sortida.
Disseny de programes declaratius.
Estructures de dades avançades en programació lògica.
  • Laboratori:
    Exemples avançats de programació lògica.

5. Programació lògica amb restriccions (Constraint Logic Programming)
T      P      L      Alt    L Ext. Est    A Ext. Total 
9,0 0 6,0 0 6,0 9,0 0 30,0
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.
CLP(X) i dominis,
Maneres de reduir l"espai de cerca.
Problemes lògics amb restriccions d"altres dominis.
Exemple: horaris (revisited).
Cerca de solucions òptimes amb CLP.
  • Laboratori:
    Problemes de planificació, assignació de recursos, horaris, etc., amb el GNU prolog amb restriccions.

6. Aplicacions de verificació
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 0 4,0 0 4,0 4,0 0 16,0
Alguns problemes representables en lògica proposicional i en lògica de primer ordre.
Verificació de circuits.
Verificació de protocols criptogràfics.
Representació de sistemes d'estats finits.



  • Laboratori:
    Ús de CLP i altres eines per a problemes de verificació.


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
42,0 0 28,0 0 28,0 37,0 0 135,0
Hores addicionals dedicades a l'avaluació 4,0
Total hores de treball per l'estudiant 139,0

Metodologia docent

Hi haurà 3 hores setmanals de teoria i/o problemes (per a evitar una excessiva rigidesa a la planificació, no hi ha un número fix d'hores per setmana per a problemes, ni classes específiques de només problemes).

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, obtinguda de l'examen escrit, amb un pes del 60%.

La nota de laboratori (40%) s'obtindrà a partir de l'avaluació de les successives entregues dels exercicis a les classes de laboratori (es preveu que siguin unes quatre entregues), tot i que hi haurà una possibilitat opcional de millora d'aquesta nota, o de recuperació de qualsevol suspens, mitjançant un examen al final del quadrimestre.

Bibliografía bàsica

  • W. F. Clocksin y C. S. Mellish Programación en Prolog, Gustavo Gili, 1993.
  • Robert Nieuwenhuis Apuntes de Lógica, Dept. LSI, 2004.
  • Pascal Van Hentenryck Constraint satisfaction in logic programming, The MIT Press, 1989.

Bibliografía complementària

  • Richard A. O'Keefe The Craft of PROLOG, the MIT Press, 1990.
  • Pascal Van Hentenryck The OPL optimization programming language, Pascal Van Hentenryck, 1999.
  • Moskewicz et al. Chaff: engineering an efficient SAT solver, Procs. Design Automation Conference, 2001.

Enllaços web

  1. http://www.lsi.upc.es/~roberto
    Pagina web de la aignatura.


Capacitats prèvies

Es tracta d'una assignatura prou autocontinguda, que no necessita molts coneixements previs.

Es requereixen coneixements bàsics de lògica, a nivell de l'assignatura d'IL, tot i que a LI es realitzarà un ampli repàs d'aquests continguts, amb una visió més orientada a les aplicacions a la informàtica.

Es desitjable, però no imprescindible, tenir coneixements de les estructures de dades i algoritmes bàsics (Pred).


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil