Universitat de Girona

Programa de l'assignatura

Curs 2003-04

3105200754 MATEMÀTICA DISCRETA


Objectius  
La matemàtica discreta integra un conjunt de branques diverses de la matemàtica que tenen totes elles relació amb la modelització de fenòmens discrets i l'estudi de les estructures finites i discretes, i que estan jugant un paper d'importància creixent a la informàtica i a ciències de la computació en general.
Aquest curs vol ésser una introducció a una part dels coneixements matemàtics bàsics i importants
per a l'estudi de la informàtica. Essencialment la Matemàtica Discreta s'estructura a l'entorn de dos grans temes, que entenem que han de constituir el nucli de l'assignatura. I - Teoria de Grafs.
II - Criptografia
 
Prerrequisits  
Obligatoris: cap
Recomanats: Àlgebra. Iniciació a la programació
 
Contingut (Programa)  

1.- Conceptes Fonamentals de grafs. (Temporalització: 8 h.)

1.1 Definicions bàsiques.
1.2 Com es guarda un graf en memòria.
1.3 Recorregut d'un graf.

1.4 Connexió i componenets.

1.5 Planaritat

2.- Camins mínims. (Temporalització: 4 h.)

2.1 Camins mínims entre dos vèrtexs d’un graf
2.2 Camí mínim entre qualsevol parella de vèrtexs.

3.- Arbres. (Temporalització: 4 h.)

3.1 Conceptes generals
3.2 Arbre generat. Generació de tots els arbres d’un graf.

3.3 Arbres generats de cost mínim d’un graf.

4.- Xarxes de transport. (Temporalització: 6 h.)

4.1 Definicions bàsiques i propietats.
4.2 Mètode del Flux-màxim Tall-mínim.
4.3 Variacions del problema del flux màxim.
4.4 Minimització del cost per a un flux fixat.

5.- Camins i Circuits Eulerians i Hamiltonians. (Temporalització: 7 h.)

5.1 Caracterització dels camins i dels circuits eulerians.
5.2 Obtenció d'un circuit eulerià.
5.3 El problema del carter xinès.
5.4 Caracterització dels camins i dels circuits hamiltonians.
5.5 Obtenció de camins hamiltonians.

6.- Conceptes bàsics d'aritmètica. (Temporalització: 7 h.)

6.1 Divisió entera i classes d'enters. L'algorisme d'Euclides.
6.2 La identitat de Bézout.
6.3 Càlcul d'inversos a Z/n.

7.- Nocions bàsiques de Criptografia. (Temporalització: 5 h.)

7.1 Alfabet, textos inicials i xifrat, unitat de missatge.
7.2 Transformacions encriptadora i desencriptadora. Criptoanàlisi.
7.3 Exemples senzills de criptosistemes. Juli Cèsar (segle I a.C.).

8.- Criptografia clàssica. (Temporalització: 6 h.)

8.1 Criptosistemes afins. Atacs al sistema.
8.2 Matrius xifradores.
8.3 Altres: Vigenère (1586 d.C.), transposició. La màquina Enigma (II Guerra Mundial).
8.4 Criptosistemes clàssics moderns: el sistema DES.

9.-Criptografia de clau pública. (Temporalització: 8 h..)

9.1 Preliminars aritmètics:

9.1.1 La funció phi d'Euler. Propietats.
9.1.2 Mètode del quadrat per al càlcul de potències modulars.

9.2 Definició de criptosistema de clau pública. Utilitats.
9.3 El Criptosistema RSA.
9.4 Tests per a l'obtenció aleatòria de nombres primers: Fermat, Miller-Rabin.
9.5 Possibles atacs al sistema RSA: el premi de 100 dòlars de Rivest.

 

 
 
Bibliografia  

Bibliografia bàsica a utilitzar durant el curs.

GRAFS:
- BASART, J.M.: "Grafs. Fonaments i algorismes" Manuals U.A.B. núm.13
- GONDRAN, M.: "Graphs and Algorithms" John Wiley & Sons. 1994
- HARARY, F.: "Graph Theory" Ed. Addison-Wesley.
- WILSON, J.R.: "Introducción a la teoría de grafos" Ed. Alianza.
- WAYNE, L. WINSTON: "Mathematical Programming. Applications and Algorithms" Ed. Duxbury Press.
- GARCÍA MERAYO, F.: "Problemas resueltos de Matemática discreta" Ed. Thomson, 2003.

CRIPTOGRAFIA:

-S. CASTANO et al.: “Database security”, ACM Press, Addison-Wesley, 1995. Seguretat aplicada a les bases de dades.

-A. FUSTER et al.: “Técnicas criptográficas de protección de datos”, Ra-Ma, Madrid, 1997. Descriu de manera resumida (però força entenedora) els temes essencials de la criptografia moderna, amb una petita menció als sistemes clàssics.

-Ll. HUGUET, J. RIFÀ: “Comunicación digital: teoría matemática de la información, codificación algebraica y criptología”, Masson, Barcelona, 1991.

- D. JUHER: “Introducció a la criptografia”, Servei de Publicacions de la Universitat de Girona, Publicacions Docents, 15, Girona, 2001.

-N. KOBLITZ: “A course in Number Theory and Cryptography”,

 Springer-Verlag, Nova York, 1987. És un llibre de matemàtiques

 avançades. Posa èmfasi en la fonamentació rigorosa dels sistemes

 criptogràfics, més que no pas en la seva implementació pràctica.

-M. LI, P. VITÁNYI: “An introduction to Kolmogorov complexity and its applications”, Springer Verlag, Nova York, 1997. És el tractat més complet i ben fonamentat que existeix sobre qüestions relacionades amb la complexitat algorísmica: màquines de Turing, aleatorietat, codis òptims, entropia, llenguatges formals.

-J. L. MORANT et al.: “Seguridad y protección de la información”, Centro Ramón Areces, Madrid, 1994.

-J. PASTOR, M. A. SARASA: “Criptografía digital: fundamentos y aplicaciones”, Publicaciones de la Universidad de Zaragoza, 1998. Constitueix un tractat seriós i exhaustiu, tant dels fonaments teòrics de la criptografia com de les seves aplicacions a xarxes d'ordinadors, comunicacions telefòniques i transaccions electròniques.

-E. A. POE: “L'escarabat d'or” (traducció de Carles Capdevila), La Magrana, Barcelona, 1998 (L'esparver, 21). Un petit clàssic de la literatura universal, l'eix argumental del qual gira al voltant del desxiframent d'un misteriós criptograma.

-J. RIFÀ: “Seguretat computacional”, Universitat Autònoma de Barcelona, Bellaterra, 1995. És un manual de consulta ràpida, concebut com a suport a la docència.

-B. SCHNEIER: “Applied Cryptography: protocols, algorithms and source code in C”, John Wiley & Sons, Nova York, 1996. Un llibre monumental que explica en profunditat tots els protocols criptogràfics moderns. Inclou els codis font (en llenguatge C) de les implementacions software del DES, l'IDEA i altres algorismes.

-S. SINGH: “The code book”, The Fourth Estate, Londres, 1999. Un complet i molt rigorós discurs històric, que abasta des dels extravagants sistemes esteganogràfics dels antics grecs fins a les darreres fronteres de la criptografia quàntica.

-S. SINGH: “Los códigos secretos”, Debate, Madrid, 2000. És la molt acceptable traducció castellana de “The code book”.

-W. STALLINGS: “Network and Internetworking Security: principles and practice”, Prentice Hall, Nova York, 1995.

-P. SWEENEY: “Error control coding: an introduction”, Prentice Hall, Nova York, 1991. Una bona introducció a la teoria dels codis correctors d'errors.

-J. C. A. VAN DER LUBBE: “Information theory”, Cambridge University Press, 1997. Un excel·lent text introductori, entenedor i rigorós alhora. Inclou una extensa col·lecció d'exercicis resolts.

-Agencia de Protección de Datos: “Conferencia sobre seguridad, privacidad y protección de datos”, Madrid, 1996.

- www.kriptopolis.com: “Kriptópolis: seguridad en Internet”.

- www.pgpi.com: “The international PGP Home Page”.

- www.rsa.com/rsalabs/faq: “RSA Laboratories' frequently asked questions about today's Cryptography”.

- www.ssh.fi/tech/crypto: “SSH Communications Security: Cryptography A-Z”.

- iya.com/stoa-atpc.htm: Projecte Echelon (EUA, Canadà, Anglaterra i Austràlia) de vigilància de les comunicacions per satèl·lit.

- www.criptored.upm.es: “Red Temática Iberoamericana de Criptografía”.

- www.arnal.es/free/cripto/cripto.htm: Campanya en contra de l'article 52 de la Llei de Telecomunicacions.

- www.iec.csic.es/criptonomicon/: Butlletí del Consejo Superior de Investigaciones Científicas.

- www.qubit.org: Computació i criptografia quàntiques.

- www.iwm.org.uk/online/enigma/: Història de la màquina Enigma, utilitzada pels alemanys durant la II Guerra Mundial per xifrar les seves comunicacions.

- www.codesandciphers.org.uk

- uk.cambridge.org/mathematics/catalogue/052181054X/default.htm

 
 
Mètodes docents  
Classes de teoria i problemes: 2 hores setmanals de grafs i 2 de criptografia. La part de criptografia es fa semipresencial.
 
Tipus d'exàmens i avaluacions  
Examen de teoria i problemes
 
Informació addicional  
No n'hi ha
 
Llengua de les classes  
Català