Dades generals

Curs acadèmic:
2017
Descripció:
Lògica de proposicions i de predicats. Teoria de conjunts i combinatòria. Grafs.
Crèdits ECTS:
9

Grups

Grup A

Durada:
Semestral, 2n semestre
Professorat:
REMEI CALM PUIG  / NARCIS COLL ARNAU  / JOSEP MARIA HUMET CODERCH  / JAIME PEDRO ROMERO RUIZ
Idioma de les classes:
Català (85%), Castellà (5%), Anglès (10%)

Grup B

Durada:
Semestral, 2n semestre
Professorat:
NARCIS COLL ARNAU  / JOSEP MARIA HUMET CODERCH  / JAIME PEDRO ROMERO RUIZ
Idioma de les classes:
Català (85%), Castellà (5%), Anglès (10%)

Competències

  • CFB3 Capacitat per comprendre i dominar els concepte bàsics de matemàtica discreta, lògica, algorítmica i complexitat computacional, i la seva aplicació per al tractaments automàtic de la informació a través de sistemes computacionals i la seva aplicació per a la resolució de problemes propis de la enginyeria

Continguts

1. Lògica de proposicions.

          1.1. Proposicions. Connectors lògics. Taules de veritat associades.

          1.2. Fórmules del càlcul proposicional.

          1.3. Formalització de proposicions.

          1.4. Tautologies i contradiccions. Implicacions i equivalències en el càlcul de proposicions.

2. Lògica de predicats.

          2.1. Definicions bàsiques: conjunt, element, pertinença, inclusió, funció, operacions amb conjunts, producte cartesià entre conjunts.

          2.2. Predicats. Quantificadors: universal i existencial.

          2.3. Fórmules del càlcul de predicats.

          2.4. Formalització de proposicions en el càlcul de predicats.

          2.5. El predicat igualtat. Formalització de proposicions utilitzant el predicat igualtat.

          2.6. Fórmules vàlides, invàlides, satisfactibles i insatisfactibles. Implicacions i equivalències en el càlcul de predicats.

3. Inferència lògica.

          3.1. Inferència lògica. La demostració directa. La demostració per reducció a l’absurd. Regles d’inferència.

          3.2. Formes conjuntives i disjuntives d’una fórmula.

          3.3. Forma normal de Skolem.

          3.4. La demostració automàtica: el mètode de resolució lineal.

          3.5. Contraexemples. Cerca de contraexemples.

          3.6. El mètode de demostració per inducció.

4. Conjunts i combinatòria.

          4.1. Producte cartesià entre conjunts.

          4.2. Relacions binàries. Relacions d'equivalència i relacions d'ordre.

          4.3. El cardinal d’un conjunt.

          4.4. Variacions i permutacions amb i sense repetició.

          4.5. Combinacions amb i sense repetició.

          4.6. Els coeficients binomials: significat i algunes propietats.

          4.7. Principi d'inclusió-exclusió. Desarranjaments.

5. Introducció als grafs.

          5.1. Conceptes bàsics sobre grafs i propietats.

          5.2. Tipus especials de grafs.

          5.3. Isomorfisme de grafs.

          5.4. Subestructures de grafs.

          5.5. Seqüència de graus d'un graf.

          5.6. Connexió i components.

          5.7. Grafs plans.

          5.8. Coloració d'un graf.

          5.9. Emmagatzematge d'un graf en memòria. Matriu d’adjacència, llista d’adjacències.

6. Recorreguts i camins mínims.

          6.1. Recorregut d'un graf. Recorregut en profunditat. Recorregut en amplada.

          6.2. Camins mínims. Algorisme de Dijkstra. Algorisme de Bellman-Ford.

7. Arbres generadors.

          7.1. Conceptes generals.

          7.2. Arbres dirigits amb arrel.

          7.3. Arbres generadors minimals. Algorisme de Kruskal. Algorisme de Prim.

8. Grafs eulerians i hamiltonians.

          8.1. Caracterització dels camins i dels circuits eulerians. Algorisme de Hierholzer.

          8.2. Problema del carter xinès. Algorisme d'Edmonds.

          8.3. Caracterització dels camins i dels circuits hamiltonians. Algorisme de Roberts i Flores.

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Total
Classes expositives 42 42 84
Classes participatives 28 35 63
Classes pràctiques 14 7 21
Prova d'avaluació 4 41 45
Resolució d'exercicis 0 12 12
Total 88 137 225

Bibliografia

  • Aranda Almansa, Joaquín (1993 ). Lógica matemática . Madrid: Sanz y Torres. Catàleg
  • Arenas Alegría, Lourdes (1996 ). Lógica formal para informáticos . Madrid: Díaz de Santos. Catàleg
  • Badesa Cortés, Calixto (1998 ). Elementos de lógica formal . Barcelona: Ariel. Catàleg
  • Barrière, Lali (2006 ). Introducció a la lògica. Barcelona: Edicions UPC. Recuperat 09-07-2012, a http://biblioteca.udg.edu/biblioteca_digital/le/edicions_upc/llibre.asp?codi=ME055XXX Catàleg
  • Cuena, José (1985 ). Lógica informática . Madrid: Alianza. Catàleg
  • Manzano Arjona, María Gracia (cop. 2004 ). Lógica para principantes . Madrid: Alianza. Catàleg
  • Sáinz Sánchez, Miquel Ángel (1994 ). Algebra . Girona: Palahí els autors. Catàleg
  • Sesa Nogueras, Enric (2004 ). Lògica (2a ed.). Barcelona: UOC. Catàleg
  • Basart i Muñoz, Josep M (1994 ). Grafs : fonaments i algorismes . Bellaterra: Publicacions de la Universitat Autònoma de Barcelona. Catàleg
  • Basart i Muñoz, Josep M (1997 ). Fonaments de matemàtica discreta : elements de combinatòria i d'aritmètica . Bellaterra: Universitat Autònoma de Barcelona Servei dePublicacions. Catàleg
  • García Merayo, Félix (2003 ). Problemas resueltos de matemática discreta . Madrid: International Thomson. Catàleg
  • García Merayo, Félix (2001 ). Matemática discreta . Madrid: Paraninfo. Catàleg
  • Grimaldi, Ralph P (1989 ). Matemáticas : discreta y combinatoria : introducción y aplicaciones . Argentina [etc.]: Addison-Wesley Iberoamericana. Catàleg
  • Manual MuPAD. Recuperat , a http://www.calvin.edu/~tmk5/research/mupad_tutorial.pdf
  • Masià, Ramon (2007 ). Matemàtica discreta (2a ed.). Barcelona: UOC. Catàleg
  • Trias Pairó, Joan (2001 ). Matemàtica discreta : problemes resolts . Barcelona: Edicions UPC. Catàleg
  • Trias Pairó, Joan (2001 ). Matemàtica discreta. Barcelona: Edicions UPC. Recuperat 04-07-2013, a http://biblioteca.udg.edu/biblioteca_digital/le/edicions_upc/llibre.asp?codi=ME026XXX Catàleg

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Exercicis Lògica Resolució individual d'exercicis de lògica amb la plataforma ACME. No recuperable. 5
Examen Lògica Es realitzarà durant el curs després de les 6 primeres setmanes. Es valorarà el procés de resolució i el resultat. Recuperable. 35
Exercicis Grafs Lliurament d'exercicis proposats a les classes de problemes. Es podran fer de manera individual o per parelles. Es valorarà la presentació, el procés de resolució i el resultat. No recuperable. 5
Examen Combinatòria i Grafs Es realitzarà a la convocatòria ordinària de l'assignatura. Es valorarà el procés de resolució i el resultat. Recuperable. 40
Pràctiques S'avaluarà la feina lliurada a cada sessió. No recuperable. 15

Qualificació

Exercicis: Els exercicis només es podran lliurar una vegada i no es podran recuperar.

Pràctiques: La feina realitzada a cada pràctica s'avaluarà sobre 10. La nota de pràctiques serà la mitjana d'aquestes notes. Si no s'assisteix a un mínim de 5 sessions de les 7 sessions totals, la nota de pràctiques serà 0. Les pràctiques no són recuperables.

Es necessita un mínim de 3 en la nota de l'examen de Lògica i un mínim de 3 en la nota de l'examen de Combinatòria i Grafs per a poder aprovar l'assignatura. En cas que alguna d'aquestes dues notes sigui inferior a 3 la nota màxima de l'assignatura serà de 4.5

Per a poder recuperar els exàmens de Lògica o de Combinatòria i Grafs caldrà que la nota global de l'assignatura sigui més gran o igual que 3.
En cas que la nota de recuperació d'una part sigui superior a l'anterior, es prendrà aquesta com a nota definitiva de la part. En cas contrari, es prendrà com a nota definitiva la mitjana de les notes dels dos exàmens de la part.

Criteris específics de la nota «No Presentat»:
L'alumne se'l considerarà No Presentat si no es presenta a cap de les següents activitats: Examen Lògica, Examen Combinatòria i Grafs.

Observacions

Prerequisits:

Es necessita haver adquirit les destreses que són habituals en el raonament i càlcul formal matemàtics. També és recomenable tenir uns coneixements mínims de programació i de Matemàtiques a nivell de batxillerat, en especial l'àlgebra de matrius.