MATEMÀTIQUES APLICADES

 

 

Professor coordinador: Enric Sesa i Nogueras (sesa@eupmt.cat)

 

Tipus d’assignatura: Troncal

 

Nivell: 3A

 

Càrrega lectiva: 4.5 crèdits (teoria/aplicació) / 3.5 crèdits ECTS

 

Recomanacions: Estar cursant o haver cursat l’assignatura “Algorísmica i Programació Avançada”.

 

Organització de la docència:

Teoria/aplicació: 3 hores/setmana x 12 setmanes

 

Descripció

En el primer tema, l'estudiant analitzarà amb un cert rigor matemàtic la complexitat dels algorismes que dissenya. La  resta de temes es dediquen a la lògica matemàtica d'enunciats i la de predicats, posant especial atenció als diversos mecanismes de deducció lògica. Finalment, com a exemple d’aplicació de la lògica en el camp de la informàtica, s’introduirà la programació amb el llenguatge lògic Prolog.

 

Objectius

En finalitzar el curs, l’estudiant serà capaç de:

·          Enumerar  les diferents funcions usades per categoritzar la complexitat temporal dels algorismes.

·          Analitzar la complexitat dels algorismes (sobretot els iteratius).

·          Donar la complexitat d’alguns dels algorismes que coneix (ordenacions, cerques, algorismes sobre grafs, ...).

·          Interpretar i manipular la sintaxi i semàntica de la lògica d'enunciats (formalitzar enunciats i raonaments de poques premisses en el llenguatge de la lògica d’enunciats).

·          Aplicar els conceptes d’interpretació, model i contraexemple de la lògica d’enunciats a la validació/refutació de raonaments i a la categorització d’enunciats (contradiccions, tautologies, contingències).

·          Aplicar la deducció natural per validar raonaments (construir demostracions per a raonaments de poques premisses).

·          Aplicar la resolució lineal com a mètode de deducció/refutació.

·          Interpretar i manipular la sintaxi (i la semàntica, però en menor grau) de la lògica de predicats (formalitzar enunciats i raonaments de poques premisses en el llenguatge de la lògica de predicats).

·          Aplicar la deducció natural en la lògica de predicats (construir demostracions per a raonaments simples i amb poques premisses).

·          Aplicar la resolució lineal en la lògica de predicats, com a mètode de validació/refutació.

·          Escriure petits programes en Prolog.

 

Bibliografia bàsica

·          Matemàtiques Aplicades. Notes de Teoria. Enric Sesa. Publicacions de l’EUPMt 2008

·          Matemàtiques Aplicades. Exercicis de Lògica. Enric Sesa. Publicacions de l’EUPMt 2008

 

Bibliografia complementària

·          Introducción a la Lógica formal. Alfredo Deaño. Alianza Editorial, 1993

·          Lógica Simbólica. Manuel Garrido. Ed. Tecnos, 3a edició 1995

·          Prolog Programming for Artificial Intelligence. Ivan Bratko. Ed. Pearson Addison Wesley. 3a edició 2000, ISBN 0201403757

 

Criteris d’avaluació i mètode de qualificació

·          Prova parcial de complexitat algorísmica i de lògica d’enunciats (entre un 45% i un 50%).

·          Prova parcial de lògica de predicats i de Prolog (entre un 45% i un 50%).

·          Treball personal dirigit pel professor  (10% aprox., si es realitza).

·          Les proves parcials es realitzen sense apunts.

·          No hi ha examen final però es podran recuperar els parcials.

Programa de teoria

Tema 1. Complexitat algorísmica

1.1  Espai de memòria vs. temps de computació

1.2  Ordres de complexitat

1.3  Complexitat dels algorismes recursius

1.4  Classificació dels problemes segons la complexitat

 

Tema 2. Lògica d'enunciats: introducció

2.1 La lògica d'enunciats i el seu llenguatge

2.2 Àtoms i connectives

2.3 Formalització

 

Tema 3. Lògica d'enunciats: semàntica

3.1 Interpretació dels enunciats

3.2 Enunciats vàlids, invàlids, satisfactibles i insatisfactibles

3.3 Enunciats equivalents

3.4 Àlgebra d'enunciats

 

Tema 4. Lògica d'enunciats: regles d'inferència i resolució

4.1 Les regles d'inferència

4.2 La deducció natural

4.3 Formes normals

4.4 Introducció al mètode de resolució

4.5 Resolució lineal

 

Tema 5. Lògica de predicats: introducció

5.1 Lògica de predicats i el seu llenguatge

5.2 Variables i constants

5.3 Predicats, quantificadors i fórmules

5.4 Formalització

 

Tema 6. Lògica de predicats: regles d'inferència i resolució

6.1 Predicats equivalents

6.2 Les regles d'inferència i la deducció natural

6.3 Formes normals i skolemització

6.4 Unificació de fórmules

6.5 Resolució lineal

 

Tema 7. Introducció a la programació lògica. El llenguatge Prolog

7.1  Fets i regles. Les clàusules de Horn

7.2  Consultes i validació de raonaments

7.3  El mètode de resolució en Prolog

 

 

Metodologia docent

El treball a l’aula es basarà en l’exposició, per part del professor, dels continguts teòrics de l’assignatura. D’aquests continguts teòrics se’n treballarà la vessant pràctica (aplicació a la resolució de problemes concrets) a través de la proposta de (petits) problemes  per part del professor i que els estudiants hauran de resoldre de manera individual o en petits grups de caire informal. El professor resoldrà part dels problemes proposats (els estudiants podran participar activament en aquesta resolució, si ho desitgen) com a il·lustració pràctica dels conceptes teòrics i per proporcionar als estudiants elements que els permetin d’avaluar el seu seguiment de la matèria.

L’assignatura disposa d’una àmplia col·lecció d’exercicis i problemes, tots ells amb la seva corresponent solució, complementada amb els enunciats dels exàmens del(s) darrer(s) semestre(s). La major part de l’activitat fora de l’aula que l’estudiant haurà de desenvolupar consistirà en la resolució de problemes d’aquesta col·lecció, previ repàs dels conceptes teòrics explicats a l’aula. En disposar de la solució de tots els problemes i exercicis, l’estudiant podrà autoavaluar el seu seguiment i destresa per a enfrontar-se a diferents problemes i podrà contactar amb el professor sempre que ho consideri escaient, en l’horari habilitat a aquest efecte.

El professor pot proposar la realització d’un treball no presencial dirigit (en funció del temps disponible, etc.) que en cas de ser proposat tindria un petit impacte en l’avaluació final. Cas de proposar-se, aquest treball versaria preferentment sobre programació en prolog.

by Bitlonia