INFORMAZIONI SU

ASD Matematica Discreta

Programma dell'insegnamento di ASD Matematica Discreta - Corso di laurea in Biotecnologie (2012/13)

Docente

Giuseppe Lancia giuseppe.lancia@uniud.it

Crediti

6 CFU

Finalità

In questo corso verranno illustrate alcune fondamentali strutture dati e il loro utilizzo nell'implementazione efficiente di algoritmi per dei problemi, molto generali e particolarmente importanti, di ottimizzazione discreta. Tra questi problemi ricordiamo la ricerca di cammini minimi su grafi, di minimi alberi di supporto, di accoppiamenti ottimi in grafi bipartiti ed altri ancora. Molti di questi problemi sono definiti relativamente a grafi, pesati e non. Il corso introdurrà perciò le nozioni fondamentali della teoria dei grafi, a partire dalle principali definizioni (cammini, cicli, tagli, alberi, colorazioni, ecc.) e i principali teoremi (relativi alla somma dei gradi dei nodi, alla bi-colorabilità di un grafo, a relazioni di dualità tra coperture e accoppiamenti, ecc.).

Verrà altresì introdotta la matematica fondamentale necessaria alla comprensione di tali argomenti, tra cui nozioni combinatoriche di base (permutazioni e coefficienti binomiali) e teoremi fondamentali relativi all'esistenza (principio della piccionaia) o al conteggio (principio di inclusione/esclusione, principi della somma e del prodotto) di elementi di un insieme. Al termine del corso lo studente dovrebbe aver acquisito la capacità di modellare un nuovo problema tramite opportuni oggetti matematici (ad esempio un grafo opportunamente definito) di tradurre tali oggetti in corrispondenti strutture dati e infine disegnare un algoritmo efficiente per la sua risoluzione.
 

Programma

  • Algebra booleana, insiemi e funzioni. Relazioni e equivalenze.
  • Sommatorie. Il principio di induzione. Cenni di calcolo delle probabilità.
  • Elementi di Combinatorica. Il principio della piccionaia. Numeri di Fibonacci. Il principio di inclusione-esclusione.
  • Procedure combinatoriche. Problema dei matrimoni stabili.
    Generazione di tutti i sottoinsiemi/permutazioni e di sottoinsiemi/permutazioni casuali.
  • Teoria dei grafi. Grafi euleriani e hamiltoniani. Grafi bipartiti.
    Connessione. Alberi. Grafi orientati e pesati. Algoritmi su grafi. Il minimo albero di supporto. Accoppiamenti e coperture di vertici.
    Cliques e insiemi indipendenti. Colorazione di grafi.
  • Aritmetica intera, quoziente e resto, scomposizione in fattori primi. MCD e mcm. Algoritmo di Euclide. Cenni di teoria dei numeri.
    Numeri primi e fattorizzazione.
     

 

Bibliografia

Dispense preparate dal docente.
Introductory Combinatorics di Richard Brualdi North-Holland publishing (2nd edition 1992, e successive)


Modalità d'esame

Prova scritta.