Estudia > Oferta formativa > Oferta d'assignatures > Detall de l'assignatura
Anar al contingut (clic a Intro)
UdG Home UdG Home
Tancar
Menú
Identificació

Estudia a la UdG

Dades generals

Curs acadèmic:
2020
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  / JORDI RIPOLL MISSE  / 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  / JORDI RIPOLL MISSE  / 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 Hores virtuals amb professor Total
Prova d'avaluació 4,00 41,00 0 45,00
Resolució d'exercicis 0 15,00 0 15,00
Sessió expositiva 0 42,00 42,00 84,00
Sessió participativa 28,00 35,00 0 63,00
Sessió pràctica 0 6,00 12,00 18,00
Total 32,00 139,00 54,00 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 22-06-2018, a http://hdl.handle.net/2099.3/36696 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 % Recuperable
Exercicis Lògica Resolució individual d'exercicis de lògica amb la plataforma ACME. No recuperable. 5 No
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 No
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à l'assistència a cada sessió i el lliurament de la darrera sessió de pràctiques. No recuperable. 15 No

Qualificació

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

Pràctiques: Assistència (5%), pràctica final (10%)

Per a les activitats recuperables s'ha de tenir en compte que quan 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.

Avaluació única:
L'avaluació única consistirà en:
• Examen final, 85% de la nota (40% Lògica, 45% Grafs i Combinatòria)
• Examen de pràctiques, 15% de la nota.
L'examen final serà recuperable en la data fixada en el calendari d’exàmens.

Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació global mínima de 5.0. Ara bé, es necessitarà 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 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

Tutoria

Les tutories personalitzades amb els estudiants es duran a terme de forma presencial o virtual mitjançant Google Meet. Prèviament caldrà concertar la tutoria per alguna de les vies de comunicació.

Comunicacio i interacció amb l'estudiantat

A part de la comunicació i interacció que es produeixi a l’aula a les hores d’activitat presencial, la comunicació amb els estudiants és portarà a terme via un dels tres mitjans següents:
• Correu electrònic
• El sistema de missatgeria del Moodle de l’assignatura
• Algun dels fòrums de l’assignatura, a través del Moodle

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.

Modificació del disseny

Modificació de les activitats:
En el cas que s’hagi de passar a un escenari presencial es mantindran les activitats ja programades de forma presencial i les activitats no presencials es passaran a presencials reorganitzant els grups si és necessari.

Modificació de l'avaluació:
No hi haurà modificacions.

Tutoria i comunicació:
Les tutories es podran fer en format presencial o via Google Meet concertant-les prèviament. La comunicació es mantindrà igual per una de les tres vies indicades.