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 Curriculum unico
Orientamento Metodi e Dispositivi per le Trasmissioni Wireless
Anno Accademico 2019/2020
Crediti 6
Settore Scientifico Disciplinare MAT/03
Anno Secondo anno
Unità temporale Secondo semestre
Ore aula 48
Attività formativa Attività formative a scelta dello studente (art.10, comma 5, lettera a)

Canale unico

Docente VITTORIA BONANZINGA
Obiettivi Conoscenza delle nozioni di base di grafi planari e problema della K-colorazione, di concetti base di algebra di algebra computazionale, quali ordinamenti monomiali, basi di Groebner, per studiare i grafi con strumenti di algebra computazionale.
Conoscenza degli strumenti e delle tecniche proprie della teoria dei Grafi riguardanti la Copertura minimale di un grafo, il problema della k-colorazione e del calcolo dei cili di un grafo.
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.
Capacità di utilizzare il software di algebra computazionale per la risoluzione di problemi riguardanti il calcolo dei cicli in un grafo, la k-colorazione e la copertura minimale di un grafo..
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.

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. (5pt)
2. Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti.(3 pt)
3. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza.Cammini e circuiti euleriani.( 4t)
4. Grafi e colorazioni. Alberi con radice. Alberi di copertura minimali. (4pt)
5. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero. Algoritmo di Dijkstra.(5 pt)
6. Studio della K-colorazione, della copertura minimale di un grafo e del calcolo dei cicli di un grafo mediante l'utilizzo dell'algebra computazionale. (5 pt)
7. Utilizzo del software CoCoA per la risoluzione di esercizi(4pt)


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. Tali verifiche in itinere hanno una durata di 30 minuti. 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;
Insufficiente: non possiede una conoscenza accettabile degli argomenti trattati durante il corso.

Programma Origini: problema dei ponti di Königsberg. Definizioni e concetti fondamentali: raggio, diametro, eccentricità, distanza pesata, ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Grado. Teorema: In un grafo o multigrafo la somma
dei gradi dei vertici è uguale a due volte il numero dei lati. (con dimostrazione). Collezione grafica. Collezione valida. Operazioni con i grafi. Prodotto cartesiano di due grafi. Isomorfismo tra grafi. Rappresentazione di grafi. Alberi. Grafi diretti. Cammini e circuiti euleriani. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza. Alberi di copertura minimali. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema del massimo flusso e minimo taglio. 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.
Testi docente W. D. Wallis, A Beginner’s Guide to Graph Theory, Second edition, Birkhäuser, 2007.

Erogazione tradizionale
Erogazione a distanza No
Frequenza obbligatoria No
Valutazione prova scritta
Valutazione prova orale
Valutazione test attitudinale No
Valutazione progetto
Valutazione tirocinio No
Valutazione in itinere
Prova pratica No
Docente GIOIA FAILLA
Obiettivi Conoscenza delle nozioni di base di grafi planari e problema della K-colorazione, di concetti base di algebra di algebra computazionale, quali ordinamenti monomiali, basi di Groebner, per studiare i grafi con strumenti di algebra computazionale.
Conoscenza degli strumenti e delle tecniche proprie della teoria dei Grafi riguardanti la Copertura minimale di un grafo, il problema della k-colorazione e del calcolo dei cili di un grafo.
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.
Capacità di utilizzare il software di algebra computazionale per la risoluzione di problemi riguardanti il calcolo dei cicli in un grafo, la k-colorazione e la copertura minimale di un grafo..
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.

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. (5pt)
2. Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti.(3 pt)
3. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza.Cammini e circuiti euleriani.( 4t)
4. Grafi e colorazioni. Alberi con radice. Alberi di copertura minimali. (4pt)
5. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero. Algoritmo di Dijkstra.(5 pt)
6. Studio della K-colorazione, della copertura minimale di un grafo e del calcolo dei cicli di un grafo mediante l'utilizzo dell'algebra computazionale. (5 pt)
7. Utilizzo del software CoCoA per la risoluzione di esercizi(4pt)


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. Tali verifiche in itinere hanno una durata di 30 minuti. 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;
Insufficiente: non possiede una conoscenza accettabile degli argomenti trattati durante il corso.

Programma Grafi planari e problema della K-colorazione. Polinomio cromatico. Nozioni di base di algebra per lo studio dei grafi tramite l'algebra computazionale: Definizione di Anello, di anello dei polinomi in n indeterminate, di ideale. Ordinamenti di variabili, ordinamenti monomiali. Definizione di base di Groebner, cenni sull'algoritmo di Buchberger ed S-coppia. Studio della K-colorazione, della copertura minimale di un grafo e del calcolo dei cicli di un grafo mediante l'utilizzo dell'algebra computazionale. Introduzione all'uso del software di algebra computazionale CoCoA. Svolgimento di numerosi esercizi con l'utilizzo del software. Esempi di applicazioni della teoria dei grafi ai trasporti, alle reti elettriche.
Testi docente 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

Capani - G. Niesi - L. Robbiano, A system for doing computations in
commutative algebra, Available via anonymous ftp from: cocoa.dima.unige.it.
Erogazione tradizionale No
Erogazione a distanza
Frequenza obbligatoria No
Valutazione prova scritta No
Valutazione prova orale
Valutazione test attitudinale No
Valutazione progetto No
Valutazione tirocinio No
Valutazione in itinere
Prova pratica No

Ulteriori informazioni

Nessun avviso pubblicato
Nessuna lezione pubblicata
Codice insegnamento online pubblicato. Per visualizzarlo, autenticarsi in area riservata.

Impostazione cookie

Cerca nel sito

 

Posta Elettronica Certificata

Direzione

Tel +39 0965.1693217/3252

Fax +39 0965.1693247

Indirizzo e-mail


Protocollo

Tel +39 0965.1693422

Fax +39 0965.1693247

Indirizzo e-mail

Didattica e orientamento

Tel +39 0965.16933385

Fax +39 0965.1693247

Indirizzo e-mail

Indirizzo e-mail

Segreteria studenti

Tel +39 0965.1691475

Fax +39 0965.1691474

Indirizzo e-mail

Amministrazione

Tel +39 0965.1693214

Fax +39 0965.1693247

Indirizzo e-mail


Ricerca

Tel +39 0965.1693422

Fax +39 0965.1693247

Indirizzo e-mail

Social

Facebook

Twitter

YouTube

Instagram