Il,
Anno:Periodo 2:l Lezione, Esercitazione: 4+4(oresettimanali) Docente: PaoloCamurati (Collab.: Massimo Poncino)
Le lezioni si propon gonodiillustrare i concetti fondamentali relativialle strutture dati edagli algoritmi.Si tratterann ogli algoritmi classicidi ordinamento,ricerca e relativi ai grafi, analizzandone la complessità. Saranno, inoltre, presentate metodologie generali per la progettazione dialgoritmi. Le esercitazioni tratterannogli aspetti avanzati della programmazionein linguaggio C,quali lestrutture dinamiche e la recursione,le meto -dologie dianalisistrutturata disistemi ed un'introduzionealla programmazione orienta-ta agli oggetti .
REQUISITI
Fondamentidiinformatica I(INF)
PROGRAMMA
Introduzioneaglialgoritmi [l ora]
AnalisidiComplessità [Sore]
- Comportamenti asintotici - Equazioni alle ricorrenze Algoritmidi ordinamento [7ore]
- Limite inferiore di comple ssità - Heap e code a priorità,heapsort - Quicksort
- Algoritmi lineari Strutture dati [13ore]
- Code,pile,liste,alberi - Tabelledi hash - Alberi binari di ricerca - AlberiRB
- B-tree - AlberiOS
Tecniche avanzate dianalisi e progetto [4ore]
- Programmazionedinamica - Algoritmigreedy
- Analisiammortizzata Teoria deigrafi [14 ore]
- Rappresentazioneevisita di grafi - Alberi ricoprenti minimi
- Single-so urceshortestpath - All-pairs shortest path - Retidi flusso
Teoria dell a complessi tà [4ore]
- Class i dicompl essità
ESE RCITAZION I l. Cavanzato [8 ore]
- Modularità.Recur sion e.Puntatori ed allocazionedinamic adellamemoria 2. Strutture datied algoritmi inC(12ore]
- Liste,pile,code,alberi,codea priorità.
3. Risoluzionedi problem icompl essi[14 ore]
4. Applicaz ioni della teor iadei grafi[8ore]
5. Analisistrutturata di sistemi [4 ore]
6. Introduzion ealla programm azioneorientataaglioggetti [4 ore]
BIBLIOGRAFIA
T.H. Cormen,C.E.Leiserson,R.L.Rivest, "Introduction loAlgorithms",McGrawHiIl, 1992 (anchein versio ne italiana)
Testi ausilia ri
B.W. Kernighan, D.M. Ritchie , "The C programming /anguage", 2nd ed., Prentice Hall,EnglewoodCliffs, NJ(USA), 1988
C. Gane,T.Sarson, "StructuredSystemsAna/ysis",PrenticeHall,Englewood Cliffs,NJ (USA),1979
1. Rumbaugh, M. Blaha, W. Premerlani, F.Eddy, W. Lorensen, "Obj ect-oriented mo-delingand design",Prentice Hall,EnglewoodCliffs, NJ (USA), 1991
ESAME
L'esame consiste didue prove scritte, una di teoria ed una di progettazione e program-mazione e di una prova orale.Le combinazioni di appelli ai quali si può consegnareun elaborato sono quelle ufficiali della Facoltà.La validitàdi ogni elaborato consegnatoè limitata ad una sessione. Le tre prove sono indipendenti e possono essere sostenute in appelli diversi,purché nella stessa sessione.II superamento dellaprova di teoria permet-tedi accedere alla prova orale,durante laquale vieneverificato l'elaborato della prova di progettazione e programmazione.
F2300-L2300-N2300
Geometria
Anno:Periodo 1:2
Docenti:NadiaChiarii, Silvio Greco
PROGRAMMA
Vettori applicati e liberi. Spazi vettori ali e sottospazi. Operazioni sui sottospazi.
Combinazionilineari. Insiemiliberi. Basi.
- Scarti successivi e completamento di un insieme libero Dimensione.Dimensione dei sottospazi. Dimensione e base di una somma diretta. Rango. Riduzione con appli -cazione aisottospazi. Prodotto tra matrici.Matrici inverti bili.Sistemi ridotti.
Teoremadi Rouché-Capelli.Sistemi omogenei. Sistemi ad incognite vettoriali. Cal-colo dell'inversa di una matrice.Numeri complessi:definizione, forma alg., trig., radici .Polinomi.Spazi vettorialisuC.Determinanti.Teorema di Kronecker.
Applicazionilineari:kerf e Imf.Isomorfismi. Applicazione lineare associata a una matrice. Matrice associata ad una applicazione lineare.Terzo modo. Calcolo Imf.
Isomorfismi e matrici.
Teoremadiestensione.Controimmagine.CalcoloKerf. Autovalori e autovettori: def.
ed esempi.Polinomio caratteristico. Cambiobase.Invarianza delp.c.
Endo semplici:teoremi sugli endo semplici. Diagonalizzazione. Spazi con p.s.Ortogonalitàe basio.n.Gram-Schmidt.Matriciortogonali.Endoa.a.
Teorema fondamentalesugli endo a.a.Matrici simmetriche.Forme quadratiche. Poli.' nomio minimo.Teoremadi Cayley-Hamilton.Relazione tra il p.m.e il p.c.
Matrici diagonali a blocchi.Autospazi generalizzati.Endomorfismi nilpotenti:defi -nizione,proprietà,forma canonica.
Forma canonica di Jordan.Sistemidifferenziali.Equazioni diff.lineari
Geometria analitica piana.Cambiamenti di riferimento.Riduzione di coniche a for-ma canonica: teorefor-ma con esempi.Coniche degeneri.
Rette e piani nello spazio.Sfere. Generalitàsucurve e superficie .
Curve piane. Cilindri. Coni.Superficie di rotazione. Quadriche. Triedro.Curvatura, cerchioosculatore.
BIBLIOGRAFIA
Le lezioniseguonoil testo:
S.Greco,P.Valabreg a,"Lezioni dialgebra linearee geometria"2 vol.,Levrotto&Bella, Torino
Per gli esercizi si possonoconsultare:
S.Greco, P.Valabrega,"Esercizi risolti ",Levrotto&Bella,Torino G.Cervelli, A.Di Lello, "Geometria:esercizi svolti",CLUT N.Chiarli , "L'esamediGeometria ",Levrotto&Bella,Torino N.Chiarli, S.Greco,P.Valabrega, "100 esercizi diAlgebra lineare"
N.Chiarli ,S.Greco,P.Valabreg a, "100 esercizi diGeometria Analiticapiana"
N.Chiarli, S.Greco, P.Valabrega, "100 esercizi di GeometriaAnalitica dellospazio", Levrotto&Bella,Torino
ESAME
L'esameconsiste in una prova scritta della durata di due ore e in una prova orale La prova scrittaèsuddivisa in tre sezioni:
- nella prima sezione, del valore globale di 20 punti,lo studente deve inserire in ap-posite caselle le risposte ai quesiti proposti
- nelle seconda sezione, del valore globale di 5 punti, lo studente deve risolvere per esteso uno o più esercizi
- nella terza sezione,del valore globale di 5 punti, lo studente deve dimostrare uno o più risultati di tipo teorico visti nel corso
Per accedere alla prova orale occorre aver conseguito un punteggio di almeno 15 punti sui 25 delle prime due sezioni.
AI termine della prova scritta viene affissa in bacheca la correzione del compito e lo studente ha facoltà di ritirarsi dall'esame,senza che ciò comporti conseguenze.
Gli studenti che non si ritirano consegnano lo statino alla segreteria didattica del Dip. di Matematica nei tempi comunicati in sede di prova scritta.
L'esito dell'esameviene registrato qualunque esso risulti.
La prova orale si svolge nello stesso appello della prova scritta (la commissione, a suo insindacabile giudizio può decidere di esonerare lo studente dalla prova orale).
Esoneri
Orientativamente dopo le vacanze pasquali viene proposta agli studenti immatricolati nel 95/96 una prova facoltativa di esonero
Tale prova, della durata di un'ora, è strutturata nella forma di 30 quiz a risposta multi-pla.
Supera la prova lo studente che fornisce almeno 15 risposte esatte (le risposte sbagliate contano O).
Lo studente che ha superato la prima prova di esonero è ammesso alla seconda prova di esonero, che ha la durata di un'ora e mezzo e consiste di 20 quiz a risposta multipla, un esercizio, la dimostrazione di un risultato teorico visto nel corso.
Supera la prova lo studente che abbia conseguito un punteggio di almeno 15, di cui al-meno IOnei quiz (le risposte sbagliate contano O).
Lo studente che abbia superato entrambe le prove di esonero con una media di almeno 18 può:
- accettare il voto come voto finale d'esame,se ciò gli viene proposto dalla commis-sione
presentarsi all'orale in uno ed un solo dei tre appelli della sessione estiva (in tal caso l'esitoècomunque registrato, con annullamento dell'esonero)
- rinunciare al voto dell' esonero e presentarsi a sostenere l'esame regolare.