Vai al contenuto principale
Oggetto:
Oggetto:

Algoritmi per l'algebra (DM 270) - a.a. 2014/15

Oggetto:

Algorithms for the algebra

Oggetto:

Anno accademico 2014/2015

Codice dell'attività didattica
MFN1418
Docente
Prof. Giorgio Ferrarese (Titolare del corso)
Corso di studi
Laurea in Matematica
Anno
3° anno
Periodo didattico
Secondo semestre
Tipologia
D.M. 270 TAF D - A scelta dello studente
Crediti/Valenza
6
SSD dell'attività didattica
MAT/02 - algebra
Modalità di erogazione
Tradizionale
Lingua di insegnamento
Italiano
Modalità di frequenza
Facoltativa
Tipologia d'esame
Scritto e Orale
Prerequisiti
Argomenti di base di algebra e geometria.
Basics of algebra and geometry.
Propedeutico a
Corsi di algebra e geometria e corsi di matematica applicata.
Algebraic and geometry courses and applied math courses.
Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

La teoria dei grafi, pur essendo una branca della matematica pura, ha numerose applicazioni nei più disparati settori della scienza e della tecnologia (ottimizzazione dei trasporti e delle risorse, architettura dei circuiti stampati, ecc.). Il corso si propone di fornire agli studenti le conoscenze di base della teoria dei grafi e di renderli in grado di studiare e risolvere le problematiche collegate anche utilizzando gli algoritmi introdotti durante il corso.

Graph theory is part of pure mathematics, but it has many applications in
several sectors of science and technology. The aim of the course is to
give basics in graph theory with a particular attention to the algorithmic
aspects of the theory.

Oggetto:

Risultati dell'apprendimento attesi

L'allievo dovrà ottenere padronanza con gli argomenti, le tecniche e gli algoritmi introdotti durante il corso. In particolare dovrà dimostrare di saper risolvere, utilizzando le tecniche proprie della teoria dei grafi, vari problemi di tipo combinatorio che nascono tanto in ambito teorico quanto nelle applicazioni. Dovrà dimostrare di saper maneggiare concetti quali la traversabilità, la planarità, le diverse etichettatura dei grafi.

The student will understand arguments,techniques and algurithms
introduced during the course. In particular, the student will be able to
solve, using graph theory techniques,different combinatorics problems
which spring both in theoretic and applied math. The student will prove
to have understood concepts like traversability, planarity and labelling.

Oggetto:

Modalità di verifica dell'apprendimento

La prova scritta è costitutita da esercizi. La prova è valutata in 30simi. Per essere ammessi alla prova orale occorre raggiungere il punteggio di 15/30. La prova orale consiste in domande relative alla teoria e alle dimostrazioni presentate nel corso. Non ci sono domande che richiedono lo svolgimento di esercizi. Durante la prova orale ci sarà una discussione degli errori della prova scritta.
Written examination: exercises. Grade: 30-ths To be admitted to the oral examination it is required a grade 15 or more. Oral examination: questions about the contents and the proofs seen during the lessons of the course. No exercises requested. There will be a discussion about the mistakes done in the written examination.
Oggetto:

Programma

 

Grafi e sottografi: grafi, sottografi, grafi speciali, operazioni sui grafi, successioni dei gradi.
Grafi connessi e sconnessi: cammini e cicli, complemento di un grafo e grafi autocomplementari, vertici separanti e ponti, grafi euleriani, grafi hamiltoniani, blocchi. Matrici e alberi: grafi e matrici, alberi, il numero degli alberi non identici, alberi ricoprenti e teorema degli alberi e delle matrici.
Grafi planari e non planari: la formula di Eulero, condizioni algebriche necessarie planarità, grafi planari e poliedri, omeomorfismo, caratterizzazione dei grafi planari.


Graphs and subgraphs. Special graphs. Operations on graphs. Degree sequences. Connected and disconnected graphs. Paths and cycles. Complementary graph. Autocomplementary graphs. Cut vertices and bridges. Eulerian graphs. Hamiltonian graphs Blocks. Matrices. Trees. The number of nonidentical trees. Spanning trees.  Matrices and trees theorem. Planar and nonplanar graphs. Euler formula. Algebraic conditions to planarity. Planar graphs and polyhedra. Homeomorphism. Characterization of planar graphs. 

 

Testi consigliati e bibliografia

Oggetto:

M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt.

S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley.

M. BURZIO - Dispense del Corso, disponibili in Materiale Didattico.

Corso di Teoria dei Grafi: cartella Dropbox che il docente rende disponibile su richiesta dello studente.

M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt.

S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley. 

M. BURZIO, Lectures notes, downloadable from Materiale Didattico



Oggetto:

Orario lezioni

GiorniOreAula
Lezioni: dal 02/03/2015 al 05/06/2015

Nota: Per l'orario delle lezioni consultare la pagina "Orario Lezioni":http://www.educmatematica.unito.it/CMSOrari/index.html

Oggetto:

Note

ALGORITMI PER L'ALGEBRA, MFN1418 (DM270), 6 CFU, MAT/02, TAF D Libero, Ambito: a scelta dello studente. 

Oggetto:

Altre informazioni

http://www.matematica.unito.it/cgi-bin/home.pl/View?doc=Orario_LT.html
Oggetto:
Ultimo aggiornamento: 06/07/2015 17:14

Non cliccare qui!