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.
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.
Els alumnes que no assoleixin la nota mínima d'aprovat en el càlcul ponderat final de l'assignatura podran presentar-se a l'examen de recuperació per intentar millorar la nota de:
- Examen Lògica
- Examen Combinatòria i Grafs
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: A l’aula on es faci l’activitat d’avaluació s’accedirà amb tots els aparells de comunicació (mòbils, ordinadors, tauletes, rellotges intel·ligents, etc.) APAGATS i dins les motxilles/bosses. L’incompliment d’aquesta norma suposarà una qualificació de 0 a l‘activitat així com l’execució de les accions que descriu l’article 21 de la normativa reguladora dels processos d’avaluació i qualificació dels estudiants de la UdG. Si durant el procés de correcció de l’activitat d’avaluació el professor determina l’existència d’un possible frau, aquest es reserva el dret de validar la qualificació obtinguda segons la metodologia d’avaluació que consideri oportuna.
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.