Anar al contingut (clic a Intro)
UdG Home UdG Home
Tancar
Menú

Estudia

Dades generals

Curs acadèmic:
2023
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  / Narcís Coll Arnau  / Jordi Ripoll Misse  / Jaime Pedro Romero Ruiz
Idioma de les classes:
Català (100%)

Grup B

Durada:
Semestral, 2n semestre
Professorat:
Narcís Coll Arnau  / Josep Gispert i Vilaseca  / Jaime Pedro Romero Ruiz
Idioma de les classes:
Català (100%)

Competències

  • CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
  • CT02 Comunicar-se oralment i per escrit
  • CT04 Treballar en equip
  • 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 42,00 42,00 0 84,00
Sessió participativa 28,00 35,00 0 63,00
Sessió pràctica 12,00 6,00 0 18,00
Total 86,00 139,00 0 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: Les pràctiques (15%) són no recuperables i estan distribuïdes en un 5% Lògica i en un 10% Grafs. Les pràctiques de Lògica s'avaluen amb la resolució de cada pràctica, mentre que les pràctiques de Grafs s'avaluen amb la resolució de l'última pràctica.

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.

Important: Si en qualsevol tipus d'activitat acadèmica es detecten actuacions fraudulentes (utilització d'informació sense autorització, utilització d'informació falsa, utilització de dispositius no autoritzats, suplantació de la identitat, plagis totals o parcials, compra i venda de proves, pràctiques i treballs, etc) l'estudiantat implicat suspendrà automàticament l'assignatura. En funció del tipus d'acte fraudulent la Direcció de l'Escola iniciarà els procediments adients d'acord amb la Llei 3/2022 de 24 de febrer de Convivència Universitària (https://www.boe.es/eli/es/l/2022/02/24/3).

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.5 en la nota de l'examen de Lògica i un mínim de 3.5 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.5 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.

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.