Questo sito utilizza cookie tecnici propri e di terze parti, necessari al suo funzionamento, e, con il tuo consenso, cookie di profilazione ed altri strumenti di tracciamento di terze parti, utili per esporre video ed analizzare il traffico al fine di misurare l'efficacia delle attività di comunicazione istituzionale. Puoi rifiutare i cookie non necessari e di profilazione cliccando su "Solo cookie tecnici". Puoi scegliere di acconsentirne l'utilizzo cliccando su "Accetta tutti" oppure puoi personalizzare le tue scelte cliccando su "Personalizza".
Per maggiori informazioni consulta la nostra privacy policy.

Solo cookie tecnici Personalizza Accetta tutti

vai al contenuto vai al menu principale vai alla sezione Accessibilità vai alla mappa del sito
Login  Docente | Studente | Personale | Italiano  English
 
Home page Home page

TEORIA DEI GRAFI

Corso INGEGNERIA INFORMATICA E DEI SISTEMI PER LE TELECOMUNICAZIONI
Curriculum comune
Anno Accademico 2023/2024
Anno 2
Crediti 6
Ore aula 48
Settore Scientifico Disciplinare MAT/03 - GEOMETRIA
Attività formativa A scelta dello studente
Ambito A scelta dello studente

Docenti

Foto Vittoria BONANZINGA
Responsabile Vittoria BONANZINGA
Crediti 3
Semestre Secondo Ciclo Semestrale

Foto Gioia FAILLA
Responsabile Gioia FAILLA
Crediti 3
Semestre Secondo Ciclo Semestrale

Informazioni dettagliate relative all'attività formativa

Origini: problema dei ponti di Königsberg. Definizioni e concetti fondamentali: definizioni, ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti. Matrici e spazi vettoriali di grafi. Cammini e circuiti euleriani. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza. Matching. Grafi e colorazioni. Alberi con radice. Alberi di copertura minimali. Reti. Cammini nelle reti. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero. Algoritmi: di Dijkstra, di Kruskal e di Prim. Applicazioni della teoria dei grafi ai trasporti, alle reti elettriche, alle reti di calcolatori per la distribuzione e l’immagazzinamento di informazioni.

Definizioni di base di algebra commutativa: definizione di anello commutativo, di campo, ideale di un anello, operazione tra ideali. Anello dei polinomi in n-indeterminate a coefficienti su campo. Ordinamenti monomiali. Ordinamento delle variabili. Introduzione dell’algebra computazionale mediante l’uso delle basi di Groebner per lo studio della K-colorazione, della copertura minimale di un grafo e del calcolo dei cicli di un grafo. Utilizzo delle basi di Grobner sia dal punto vista teorico che pratico. Uso dei software di algebra computazionale CoCoA o Macaulay 2 per lo svolgimento di esercizi.


Ultimo aggiornamento: 08-10-2023

  • W. D. Wallis, A Beginner’s Guide to Graph Theory, Second edition, Birkhäuser, 2007.
  •  W.W. Adams, P. Loustaunau, An Introduction to Groebner Bases, American Mathematical Society, 2012
  • Tutorial software CoCoA (Capani - G. Niesi - L. Robbiano, A system for doing computations in commutative algebra, Available via anonymous ftp from: cocoa.dima.unige.it.)




Ultimo aggiornamento: 08-10-2023

Conoscenza delle nozioni di base della teoria dei Grafi:grafo semplice,ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Rappresentazione di grafi. Alberi e grafi planari. Matrice di adiacenza. Matrice di incidenza.

Conoscenza degli strumenti e delle tecniche proprie della teoria dei Grafi: Copertura minimale di un grafo, k-colorazione, percorso minimo,albero di copertura minimale. Capacità di comprendere e utilizzare strumenti matematici adeguati per la risoluzione di problemi di connessione tramite l'utilizzo dei grafi. Capacità di comunicare le conoscenze acquisite attraverso un linguaggio tecnico-scientifico adeguato.

Conoscenze relative agli aspetti metodologico-operativi della Teoria dei grafi, ai fini dell’interpretazione e descrizione di applicazioni nell’ambito dell’Ingegneria, ad esempio applicazioni nell'ambito delle reti elettriche, problemi di flusso e dei trasporti.

Conoscenza delle nozioni di base dell’algebra computazionale. Capacità di risolvere mediante tecniche di natura computazionale i problemi di colorazione di un grafo, il problema del minimal vertex cover, calcolo dei cicli di un grafo.


Ultimo aggiornamento: 08-10-2023

Conoscenze della matematica di base: insiemi numerici. Risoluzione di equazioni algebriche. Scomposizione dei polinomi algebrici. Concetto di matrice e rango di una matrice. Risoluzione dei sistemi lineari.


Ultimo aggiornamento: 08-10-2023

Metodo tradizionale. Lezione alla lavagna e svolgimento di esercizi anche con l’utilizzo dei software CoCoA o Macaulay2.


Ultimo aggiornamento: 08-10-2023

Ricevimento sia in studio che in aula. Possibilità anche di supporto per lo svolgimento di esercizi o eventuali spiegazioni anche tramite email o collegamento online.


Ultimo aggiornamento: 28-11-2023

Modalità di accreditamento e valutazione:

I possibili argomenti su cui verterà l'esame sono:

1. ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio.

2. Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti.

3. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza. Cammini e circuiti euleriani.

4. Grafi e colorazioni. Alberi di copertura minimali.

5. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero. Algoritmo di Dijkstra.


Modalità di apprendimento:

Svolgimento di esercizi tramite l’utilizzo dell’algebra computazionale e di software di calcolo simbolico.

Possibili quesiti:

1)    Basi di Groebner, Ordinamenti monomiali

2)    Colorazione di un grafo

3)    Copertura minimale di un grafo

4)    Calcolo dei cicli in un grafo


Nelle verifiche in itinere si valutano le capacità critiche raggiunte dallo Studente nell'inquadrare le tematiche oggetto del Corso ed il rigore metodologico delle risoluzioni proposte in risposta ai quesiti formulati. La prova orale consiste in un colloquio sugli argomenti delle verifiche in itinere e sugli argomenti teorici che fanno parte del programma del corso. Si valuta la capacità dello studente di comunicare le nozioni acquisite attraverso un linguaggio scientifico adeguato e la capacità di esposizione.


Il voto finale sarà attribuito secondo il seguente criterio di valutazione:

30 - 30 e lode: ottima conoscenza degli argomenti, ottima proprietà di linguaggio, completa ed originale capacità interpretativa, spiccata capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;

26 - 29: conoscenza completa degli argomenti, buona proprietà di linguaggio, completa ed efficace capacità interpretativa, in grado di applicare autonomamente le conoscenze per risolvere i problemi proposti;

24 - 25: conoscenza degli argomenti con un buon grado di apprendimento, discreta proprietà di linguaggio, corretta e sicura capacità interpretativa, capacità di applicare in modo corretto la maggior parte delle conoscenze per risolvere i problemi proposti;

21 - 23: conoscenza adeguata degli argomenti, ma mancata padronanza degli stessi, soddisfacente proprietà di linguaggio, corretta capacità interpretativa, limitata capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;

18 - 20: conoscenza di base degli argomenti principali e del linguaggio tecnico, capacità interpretativa sufficiente, capacità di applicare le conoscenze acquisite;

<18 Insufficiente: non possiede una conoscenza accettabile degli argomenti trattati durante il corso.


Ultimo aggiornamento: 08-10-2023


Eliminare le disparità di genere nell'istruzione e assicurarsi che tutti gli studenti, compresi i più vulnerabili quali le persone con disabilità, acquisiscano le conoscenze e le competenze necessarie, fornire ambienti di apprendimento sicuri, non violenti, inclusivi ed efficaci per tutti


Ultimo aggiornamento: 28-11-2023


Ulteriori informazioni

Nessun avviso pubblicato
Nessuna lezione pubblicata
Codice insegnamento online non pubblicato

Impostazione cookie

Cerca nel sito

 

Posta Elettronica Certificata

Direzione

Tel +39 0965.1695510

Fax +39 0965.1695343

Indirizzo e-mail


Biblioteca

Tel +39 0965.1695306-7-8

Fax +39 0965.1695345

Indirizzo e-mail

Orientamento

Tel +39 0965.1695364

Fax -

Indirizzo e-mail


Segreteria studenti

Tel +39 0965.655293

Fax +39 0965.654177

Indirizzo e-mail

Didattica

Giurisprudenza - +39 0965.1695402

Indirizzo e-mail

Economia - +39 0965.1695368

Indirizzo e-mail Indirizzo e-mail

Scienze Umane - +39 0965.1695404

Indirizzo e-mail Indirizzo e-mail Indirizzo e-mail


Social

Facebook

Twitter

YouTube

Instagram