Emanuela Fachini
STUDIO: D.to Informatica - Via Salaria,113 - 00198 ROMA
TEL. 0649918314
E-MAIL: fachini[AT]di.uniroma1.it
ORARIO DI RICEVIMENTO: scrivete un email per un appuntamento.

*Appelli gestiti dalla prof.ssa Calamoneri:*

RISULTATI APPELLO 28/1/2021

Siete pregati di farmi sapere entro domenica 31/1/2021 se accettate il voto scrivendo una email a calamo@diNOSPAM.uniroma1.it. Grazie.

Presentazione del corso Informazioni generali: orari lezioni, modalità di esame, testi esercizi esami a.a. precedenti

Obiettivi e risultati attesi

Programma del corso

Avvisi per gli studenti

Diario delle lezioni

Link utili o anche solo divertenti

Avvisi per gli studenti

Appello di ottobre

Qui il testo e le soluzioni: SolIntrAlg15ott20.pdf

Dettagli appello di settembre

Il testo proposto: IntrAlg17Sett2020.pdf La valutazione: ValIntrAlgSett20_.pdf Le soluzioni: SolIntrAlg17Sett2020.pdf.

testi e soluzioni degli esercizi della prova del 7 luglio

Il testo: IntrAlg7luglio2020.pdf: IntrAlg7luglio2020.pdf

Le soluzioni: SolIntrAlg7luglio2020.pdf: SolIntrAlg7luglio2020.pdf

Dettagli appello di luglio Si terrà il 7 luglio, qui potete consultare il quadro generale degli appelli di luglio. https://docs.google.com/spreadsheets/d/1Jl23I28CPLwNah4RlkcvgF1owtBrJ5_ymDvLfBSGfhI/edit#gid=0

La prova scritta si svolgerà il 7 luglio 2020 dalle 10 alle 13. L'esame scritto si svolgerà da remoto. Attrezzature necessarie Verificate di possedere le attrezzature elencate nel seguito e che esse funzionino correttamente. Collegamento a Internet stabile e di qualità sufficiente a mantenere attiva una sessione di exam.net sul PC ed una sessione Zoom sul cellulare, quindi è necessario un telefono cellulare che sia in grado di collegarsi a Internet. In sua assenza non sarà possibile svolgere l'esame. PC fisso o portatile con Sistema operativo Windows o Mac OS, browser web Google Chrome (preferibile, altrimenti anche altro browser).

SE NON SIETE IN GRADO DI AVERE ALL'ESAME UN PC CON SISTEMA OPERATIVO WINDOWS O MAC OS FATEMELO SAPERE AL PIU' PRESTO!

Azioni da compiere Se non lo avete già fatto per altri esami, dovete installare i seguenti software: - Client Zoom, da installare sullo smartphone (e anche sul pc se l'audio dello smartphone non funziona a dovere); - SEB (Safe Exam Browser), da installare solo sul PC con sistema operativo Mac OS o Windows. Inoltre, se non lo avete già fatto per altri esami, caricate su Infostud un vostro documento in corso di validità. Inquadratura della postazione di lavoro mediante cellulare Il vostro cellulare dovrà essere posizionato in modo da inquadrare la vostra postazione di lavoro da una distanza di circa due metri: deve essere visibile la vostra persona, lo schermo del PC, il piano della scrivania, la parte inferiore della scrivania. Poiché tale inquadratura sarà visibile anche agli altri partecipanti, vi invitiamo a predisporla in modo che non violi la vostra privacy. Approfittate dei prossimi giorni per fare delle prove.

Testi e soluzioni prova dell' 11 giugno Qui i testi, per l'esame completo: IntrAlg11giugno2020.pdf, e quello sulla seconda parte: IntrAlg11Giugno20P2.pdf.

E qui le soluzioni:esame completo SolIntrAlg11giugno2020.pdf e quello sulla seconda parte:SolIntrAlg11Giugno20P2.pdf

Testi e soluzioni prova del 3 giugno Qui testi per l'esame intero ProvaEsame3Giu20.pdf, e per la seconda prova ProvaEsameEsonerati3Giu20.pdf.

Qui invece trovate le soluzioni: tutto l'esame SolProvaEsame3Giu20_.pdf e solo la seconda parte SolIntrAlg11Giugno20Parte2.pdf.

Chi non ha potuto partecipare alla prova può comunque farla da solo, sia semplicemente usando i testi qui sopra riportati che collegandosi su Exam.net e cliccando sul codice dell'esame e cronometrando il tempo di esecuzione.

Chi non fosse riuscito a risolvere almeno due degli esercizi proposti, in modo da rispondere a tutte le richieste espresse nel testo difficilmente potrà recuperare da qui a una settimana, quindi consiglio a chi si trovasse in questa condizione di cancellare la sua prenotazione per consentire un più veloce svolgimento dell'esame e di studiare più approfonditamente per affrontare con successo la prova di luglio. Le prenotazioni si chiudono oggi, quindi se qualcuno decide di non presentarsi nei prossimi giorni è pregato di inviarmi un'email, in modo che si possa organizzare l'appello con il giusto numero di studenti.

Valutazione esercizi del 5 maggio 2020

Nel file seguente trovate una valutazione delle vostre soluzioni agli esercizi proposti. Tutti quelli che sono risultati insufficienti dovranno sostenere una prova intera a giugno, gli altri avranno una prova riservata e più concentrata sulla seconda parte del programma. ValIntrAlgMaggio2020.pdf. Per chiarimenti o dettagli collegatevi martedì prossimo nell'orario di ricevimento. Qui potete consultare il programma 2019/2020 del corso: ProgrammaIntrAlg1920.pdf.

Appello straordinario di maggio il 7 maggio

Qui il testo degli esercizi proposti: IntrAlg7maggio2020.pdf, e le soluzioni SolAlg7maggio2020.pdf.

Materiale per le lezioni

Continuo ad aggiornare il diario delle lezioni qui sotto, ma ho anche caricato dei file nella cartella condivisa di Introduzione agli algoritmi. In particolare alcuni testi di esercizi che vi invito a cercare di risolvere da soli, mandandomi la vostra soluzione avrete anche una correzione ad personam e le presentazioni dei lucidi comprese le animazioni, forse troppo pesanti per essere scaricati, ma che potete visualizzare tranquillamente. Per tutti gli esercizi saranno poi viste a lezione le soluzioni, una settimana dopo la proposta.

ESERCITIAMOCI, ovvero momenti di confronto tra pari anche a distanza

Il lunedì e non più mercoledì dalle 16 alle 19 alcuni studenti "anziani" selezionati dal Dipartimento di Informatica saranno a vostra disposizione in modalità telematica, sempre con Google Meet, per aiutarvi a svolgere esercizi e per rispondere a vostre domande sul contenuto delle lezioni

Ricevimento

Poiché ora l'emergenza limita ogni tipo di attività didattica, come qui sotto riportato, vi propongo di fare anche il ricevimento studenti con Google Meet. Anche voi potete avviare una riunione con me per fare domande su quanto visto finora a lezione, oggi pomeriggio dalle 15 alle 16, o mandarmi un email con le vostre domande o con la richiesta di una riunione via Google Meet. Per la settimana prossima tornerei all'orario solito del ricevimento: ogni martedì dalle 14 alle 16, sempre via Google Meet.

Comunicato. Sulla base delle disposizioni delle autorità competenti (Decreto del Presidente del Consiglio dei Ministri del 9 marzo 2020), in relazione all'emergenza Coronavirus sono sospese le attività didattiche curriculari fino al 3 aprile 2020. Sono sospese le sedute di laurea in presenza; è stato predisposto quanto necessario per consentire lo svolgimento delle sedute in modalità telematica. E' stato autorizzato il prolungamento della sessione di laurea corrente al 30 aprile 2020 per consentire alle Facoltà la migliore organizzazione delle sedute di lauree a distanza. Tale prolungamento non comporterà il pagamento della terza rata delle tasse e contributi di iscrizione. Gli esami di profitto non possono essere svolti in presenza; pertanto sono rinviati e potranno essere svolti secondo modalità telematiche che saranno successivamente comunicate. Sono sospesi i tirocini curriculari ed extracurriculari a eccezione dei tirocini delle professioni sanitarie e medica, come previsto dai Dpcm dell'8 e del 9 marzo 2020. Sono sospese fino a nuova comunicazione tutte le borse di collaborazione degli studenti (attività part time 150 ore). Oltre a quanto segnalato è sospeso il ricevimento studenti in presenza (fino al 3 aprile 2020);

Esito valutazione esame del 3 febbraio 2020

Qui il file con i voti ottenuti: MatIntrAlg3Feb2020.pdf.

Inizio lezioni

Le lezioni di Introduzione agli algoritmi avranno inizio il 27 febbraio 2020 nell'Aula III - Matematica "Guido Castelnuovo" e proseguiranno secondo l'orario: https://www.studiareinformatica.uniroma1.it/laurea/orario-lezioni

Questionario on line delle opinioni studenti Gli studenti sono invitati a rispondere ai quesiti del questionario di valutazione del corso di Introduzione agli algoritmi.

Avviso date appelli

Qui trovate il calendario degli appelli di giugno e luglio 2020: https://docs.google.com/spreadsheets/d/1TCbnLQCpghkyy8aON_bZg3N2A1oYwBYaH0gYBKBtdN0/edit#gid=0

Presentazione del corso. Si tratta di un insegnamento introduttivo all'area di studio degli algoritmi. Si studieranno gli algoritmi e le strutture dati più noti per risolvere semplici ma fondamentali problemi come la ricerca di un elemento in insieme o come ottenere una sequenza ordinata di numeri da una qualsiasi data in input. Per confrontare le soluzioni algoritmiche proposte in funzione delle risorse computazionali (tempo e spazio) necessarie per la loro esecuzione, si introdurranno gli strumenti più semplici e fondamentali per analizzare gli algoritmi, cioè calcolarne la complessità di tempo e spazio.

Programma del corso
Programma di massima: Metodi per l'analisi asintotica delle risorse di calcolo utilizzate da algoritmi iterativi e ricorsivi. Strutture dati fondamentali (pile, code, code di priorità); Principali algoritmi di ordinamento ; Il dizionario e le sue implementazioni: alberi binari di ricerca, alberi bilanciati e tabelle hash.

Qui trovate il programma dettagliato del corso per l'a.a. 2019/2020 ProgrammaIntrAlg1920.pdf.

Obiettivi corso
Conoscenze acquisite.
Al termine del corso gli studenti conosceranno le metodologie di base per la progettazione e l'analisi di algoritmi iterativi e ricorsivi, le principali strutture dati, i principali algoritmi di ordinamento e le implementazioni più elementari dei dizionari.
Competenze acquisite
Al termine del corso gli studenti:

• • avranno acquisito familiarità con le principali strutture dati elementari, in particolare quelle che implementano i dizionari. Sapranno spiegarne gli algoritmi e analizzarne la complessità, evidenziando come le prestazioni dipendano dalla struttura dati utilizzata. Saranno in grado di progettare nuove strutture dati e i relativi algoritmi, rielaborando quelli esistenti;

• • sapranno spiegare i principali algoritmi di ordinamento, illustrando le stategie di progetto sottostanti e la relativa analisi di complessità;

• • saranno in grado di confrontare i comportamenti asintotici di funzioni ottenute componendo in modo semplice polinomi, funzioni logaritmiche o esponenziali;

• • saranno in grado di progettare soluzioni ricorsive di problemi e di analizzare asintoticamente gli algoritmi risultanti.

Informazioni generali.

Prerequisiti
Si presuppongono una conoscenza di base di analisi matematica (studio di funzioni ed equazioni numeriche) ed una buona conoscenza di un linguaggio di programmazione.

I libri
Il corso si baserà sul testo di [CLRS] T.H. Cormen, C.E. Leiserson,R.L. Rivest,C. Stein, Introduzione algi algoritmi e strutture dati, (tutte le edizioni vanno bene, sia in inglese che in italiano) Mc Graw-Hill, 2010. Durante le lezioni saranno suggeriti anche link a risorse in rete, inoltre i lucidi delle lezioni saranno disponibili su questa pagina.

Altri libri di utile consultazione sono:

• [DFI07] C. Demetrescu, I. Finocchi, G.F. Italiano, "Algoritmi e Strutture Dati in Java". Mc Graw-Hill, 2008.

• [DFFI07] C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G.F. Italiano, "Progetto di Algoritmi e Strutture Dati in Java". Mc Graw-Hill, 2007.

• [A99] M. H. Alsuwaiyel, "Algorithms - Design Techniques and Analysis", Word Scientific, 1999.

• [KT06] R. Kleinberg ed E. Tardos. Algorithm Design. Addison Wesley, 2006.

Gli esami
Appelli: ci saranno cinque appelli: due tra giugno e luglio, uno in settembre e due tra gennaio e febbraio. Per informazioni ufficiali su date, orari e luoghi degli appelli (scritti, orali & verbalizzazioni), fate riferimento al http://www.studiareinformatica.uniroma1.it/appelli-d-esame nelle pagine Web del corso di laurea.
Modalità L'esame consiste in una prova scritta che conterrà:

• esercizi di ragionamento non svolti precedentemente a lezione (e.g., analisi del tempo di esecuzione di un frammento di codice o progettazione di nuovi algoritmi);
• domande tipiche da esame orale, tese a verificare la conoscenza e la comprensione di base della materia (e.g., definizioni, dimostrazioni, strutture dati e algoritmi presentati durante il corso).

Nella prova scritta non sarà possibile utilizzare libri, appunti o dispense in formato cartaceo né elettronico. L'esame durerà due e mezzo ore nelle quali lo studente dovrà svolgere tre esercizi. Le soluzioni degli esercizi scritte in modo illeggibile o in cui compaiano solo conti o pseudocodice senza commenti e risposte non motivate saranno valutati 0. Prima di descrivere un algoritmo in pseudocodice si deve delineare l’idea algoritmica. Inoltre deve essere precisato l'input e l’output atteso da eventuali singole funzioni utilizzate, oltre agli eventuali vincoli sul loro input (precondizioni). Per esempio, se si usa la ricerca binaria si deve precisare che la precondizione per la sua correttezza è che l'array su cui opera sia ordinato e qual'è l'output.

In generale, il superamento della prova scritta permette di verbalizzare il voto conseguito. Il docente ha facoltà di richiedere un orale suppletivo in casi specifici tra cui: sufficienza non piena allo scritto, dubbi di copiatura, voti alti o proposta di lode. Anche lo studente ha facoltà di richiedere un orale suppletivo nel caso intenda migliorare il voto ottenuto allo scritto.

Prova intermedia. E' prevista una prova intermedia nella settimana di interruzione della didattica. La prova riguarderà tutti gli argomenti svolti fino alla data della prova stessa. E' prevista una prova a fine corso sulla seconda parte del programma. Ognuna delle due prove conterrà 3 esercizi e il tempo a disposizione per risolverli sarà di 2 ore.

Per partecipare alle prove scritte (inclusa quella intermedia) è obbligatoria la prenotazione. Il docente, soprattutto a ridosso delle prove di esame, può usare l'indirizzo email indicato da infostud per comunicazioni importanti relative all'appello, si raccomanda dunque di consultare la propria casella di posta.

Visione dei compiti: E' fortemente consigliato visionare il compito scritto soprattutto nel caso in cui non sia stata ottenuta la sufficienza. Per motivi organizzativi sarà pubblicato un calendario di convocazioni.

Testi e alcune soluzioni di esercizi dati agli esami

IntrAlg3Feb20.pdf IntrAlg13gen20.pdf esercizi seconda prova intermedia 1918/19 SolIIEsIntrAlg2019.pdf IntAlgGiu19.pdf. IntrAlg5luglio19.pdf, SolIntrAlg5luglio19.pdf. solIntrAlgSett19.pdf. Esame2019_04_12.pdf Esame2019_01_14.pdf SolIntrAlgSett18.pdf SolIntrAlg31mag2018.pdf. IntrAlg30Gen18.pdf. IntrAlg4sett17.pdf. SolIntrAlg6giu17.pdf IntrAlg6Giu17testoA.pdf IntrAlg6Giu17TestoB.pdf SolIntrAlg25Giugno18.pdf. EsIntrAlg28Giu17testoA.pdf, EsIntrAlg28Giu17testoB.pdf, EsIntrAlg28Giu17P1.pdf. SolEsIntrAlg28Giu17P2A.pdf, SolEsIntrAlg28Giu17parte1.pdf, solEsIntrAlg28Giu17P2B.pdf. Qui il testo della prova del 3 febbraio 2017: IntrAlgFeb17.pdf. Le soluzioni della prova di esame del 7 novembre 2016. IntrAlg7Nov16.pdf I testi proposti nella prova di settembre 2016: TestiIntrAlgSett16.pdf e la soluzione SolIntrAlgSett16.pdf. Il testo e la soluzione della seconda parte della prova del 30 giugno 2016: Testo2A30Giugno16Sol.pdf, Testo2B30Giugno16Sol.pdf, Qui trovate i testi degli esercizi proposti nel primo appello di giugno 2016 Testo1A7Giugno16.pdf, Testo1B7Giugno16.pdf, Testo2A7Giugno16.pdf, Testo2B7Giugno16.pdf, Testo2C7Giugno16.pdf, Testo2D7Giugno16.pdf. Qui trovate i testi degli esercizi proposti nella prova intermedia del 2016 1ProvaIntermedia15:16.pdf, 2ProvaIntermedia15:16.pdf, 3ProvaIntermedia15:16.pdf, 4ProvaIntermedia15:16.pdf. IntrAlg1Feb2016.pdf IntrAlgGennaio2016.pdf IntrAlg9Giu15_.pdf e le soluzioni SolIntrAlg9Giu15.pdf IntrAlgLu2015.pdf e le soluzioni SolIntrAlgLu2015.pdf. IntrAlg27Gen15_.pdf e le soluzioni SolIntrAlg27Gen15_.pdf, IntrAlg9Gen15_.pdf e le soluzioni, * SolIntrAlg9Gen15_.pdf, EsIntrAlgNov14.pdf, IntrAlgLu14_.pdf e le soluzioni SolIntrAlgLu14.pdf, SolIntrAlgSett14.pdf, IntroAlgGiu14.pdfe le soluzioni SolIntrAlgGiu14.pdf, IntrAlgFebb2014.pdf, EsIntrAlgGen14.pdf EsIntrAlg17feb13.pdf. EsIntrAlgLu3.pdf, EsIntrAlgGiu12.pdf, EsIntrAlgGiu12testo2.pdf.

Link utili o anche solo divertenti

Ordinamenti.

Qui un confronto velocissimo tra 24 algoritmi di ordinamento:

Questo è un sito didattico, l'animazione aiuta la comprensione : qui

Qui trovate altre visualizzazioni dell'esecuzione di alcuni algoritmi di ordinamento. qui qui

Questo articolo fa un'analisi "spietata" del bubble sort qui

Qui anche Obama si pronuncia sul bubble sort! Obama e il Bubble
Lo studente Francesco Campo mi ha suggerito questo link: una versione folkloristica del quicksort!

Biografie di persone citate durante il corso.
Alan Turing
John Von Neumann
Grace Hopper
Antony Hoare

Alberi bilanciati
Qui un buona animazione per capire gli AVL
Qui altri esempi di inserimenti in un AVL, con modifica del fattore di bilanciamento, e una implementazione in java.
Qui una implementazione java che riflette fedelmente il procedimento illustrato a lezione.

Diario delle lezioni a.a. 2019/2020.

mercoledì 3/6/2020

Alle ore 11 di mercoledì prossimo 3 giugno si svolgerà una prova per l'esame dell'11 giugno.Vi saranno proposti tre esercizi da risolvere in un'ora e mezza, di complessità analoga e con le modalità previste per l'esame. Sarà quindi anche un'occasione per una prova tecnica sugli strumenti da usare per l'esame. Al termine saranno pubblicate su twiki le soluzioni così ognuno di voi potrà autovalutarsi confrontando la propria soluzione con quella proposta. La prova di esame resterà fruibile fino a sera, per coloro che non possono partecipare alle 11, ma vogliono cimentarsi autonomamente nella prova.

giovedì 28/5/2020 10,00 - 13,00. Lezione in streaming. AVL, cancellazione ed esercizi. AVLcancEsercizi.pdf, Alcuni esercizi semplici di inserimenti e cancellazioni in un AVL. AVLcancEsercizi.pdf.

martedì 26/5/2020 11,00 - 13,30. Lezione in streaming. Alberi bilanciati in altezza, AVL AlberiAVL.pdf. Esercizio di analisi: EsAnalisi.pdf.

giovedì 21/5/2020 10,00 - 13,00. Lezione in streaming. ABR, la cancellazione. ABRcancellazione.pdf, Esercizi visti a lezione: EsCammino.pdf, SostChiaveDaABRaABRdeg.pdf, VisInorderIterat.pdf. Esercizi da fare a casa: EserciziProposti21Maggio2020testi.pdf.

martedì 19/5/2020 11,00 - 13,30. Lezione in streaming. Alberi binari di ricerca, ABR: definizione e prime proprietà. AlberiBinariABR.pdf.

giovedì 14/5/2020 10,00 - 13,00. Lezione in streaming.Visite di alberi binari ed esempi di problemi che si risolvono con visite sugli alberi e un esercizio sugli alberi quasi completi. VisiteEs.pdf. Esercizi sulle relazioni di ricorrenza: EsRelRic1.pdf, EsRelRic2.pdf. Costruzione di un albero binario a partire da due visite. AlberidaVisite.pdf.

martedì 12/5/2020 11,00 - 13,30. Lezione in streaming. Soluzioni esercizi proposti in aula: SolIntrAlg5Maggio20Es1e2.pdf, SolIntrAlg5Maggio20Es3.pdf, SolIntrAlg5Maggio20Es4.pdf. Strutture dati astratte, primi esempi di algoritmi che necessitano di una pila o di una coda. StruttureDatiPileCode.pdf, code di priorità: CodePriorit.pdf.

martedì 5/5/2020 10,00 - 13,00. Lezione in streaming. Esercizi in aula, qui i testi IntrAlg5Maggio20Es4.pdf.

giovedì 30/4/2020 10,00 - 13,00. Lezione in streaming. Esercizi vari su relazioni di ricorrenza, notazione asintotica e analisi di algoritmi iterativi, progettazione di algoritmi. Es30aprile2020.pdf.

martedì 28/4/2020 11,00 - 13,00. Lezione in streaming. Ancora sulle relazioni di ricorrenza e il Quiksort. QuickSortHoare.pdf, EserciziPerGioved.pdf.

giovedì 23/4/2020 10,00 - 13,00. Lezione in streaming. Il Mergesort ricorsivo: esempio della strategia Divide et Impera. Analisi della complessità del Mergesort con introduzione alle relazioni di ricorrenza. Metodo della sostituzione per risolvere le ricorrenze. MergeSort_con_analisi.pdf. EsRelRic1.pdf. Esercizio per casa: EsModa.pdf.

martedì 21/4/2020 11,00 - 13,00. Lezione in streaming. Un algoritmo di ordinamento lineare: CountingSort.pdf

giovedì 16/4/2020 10,00 - 13,00. Lezione in streaming. Esercitazione sul programma svolto. Es16Aprile2020.pdf. Esercizi da svolgere a casa: EserciziCasa.pdf.

martedì 14/4/2020 11,00 - 13,00.Vacanza di Pasqua

giovedì 9/4/2020 10,00 - 13,00. Vacanza di Pasqua

martedì 7/4/2020 11,00 - 13,00. Lezione in streaming. Soluzione esercizi proposti sul Max-Heap. EsHeap2Aprile2020.pdf. Trasformare un array qualunque in un max-heap: l'algoritmo di Floyd e l'algoritmo basato sull'inserimento di un elemento in un max-heap BuildMaxHeap.pdf. Durante il ricevimento studenti del pomeriggio: ripasso mergesort e heapsort EsMergesortHeapsort.pdf, risolti insieme alcuni esercizi sulla notazione asintotica e di analisi di cicli presi dai testi degli esami dati in precedenza e consultabili nella sezione informazioni generali. Purtroppo per motivi tecnici la registrazione non è disponibile.

giovedì 2/4/2020 10,00 - 13,00. Lezione in streaming. Heap binari:definizione, esempi e prime operazioni, HeapMaxheap.pdf. Un nuovo ordinamento: L'HEAPSORT , heapsort.pdf. Esercizi svolti durante la lezione: EsFuoriPosto.pdf, OrdArrayLgn_diversi.pdf Esercizi sugli Heap da svolgere a casa EsHeap.pdf, saranno visti a lezione martedì.

martedì 31/3/2020 11,00 - 13,00. Lezione in streaming. Limiti inferiori per i problemi: il caso dell'ordinamento. LimInfOrdinamenti.pdf. Un esercizio di progettazione di algoritmi: EsTripartition.pdf. Esercizio svolto insieme: MergeKarrays.pdf.

giovedì 26/3/2020 10,00 - 13,00. Lezione in streaming. Alberi, alberi binari, misure sugli alberi binari e loro relazioni. AlberiPreliminari.pdf. Soluzione degli esercizi proposti giovedì scorso, SolEs23Marzo2020.pdf, Tripartition.pdf, EsMerge.pdf.

martedì 24/3/2020 11,00 - 13,00. Lezione in streaming. mergesort_iterativo.pdf. Un esercizio di progettazione di algoritmi: MassimoLocale.pdf.

giovedì 19/3/2020 10,00 - 13,00. Lezione in streaming. La fusione di due array ordinati in un unico array ordinato. Trovate una versione di merge a pag 26 del Cormen, ultimo capoverso. L'esercizio di progettazione di un algoritmo proposto a lezione: la determinazione di un elemento comune tra due array ordinati. La partizione di un array intorno a un elemento. La prima versione della Partition a pag. 142 del Cormen. La seconda presa da Wikipedia, https://it.wikipedia.org/wiki/Quicksort. Un altro esercizio di progettazione di un algoritmo: la tripartizione di un array intorno a un valore dato x. Si tratta di sistemare gli elementi di un array in modo tale che la prima parte contenga quelli minori di x poi quelli uguali e infine i maggiori. Esercizi sulla notazione asintotica. Merge_e_Partition.pdf, EsNotazioneAsintoticaSol.pdf.

martedì 17/3/2020 11,00 - 13,00. Lezione in streaming. Ordinamenti quadratici: insertionSort, selectionSort e bubbleSort: OrdQuadr.pdf. RBISECT, seguire questo link per una specifica in Python https://docs.python.org/2/library/bisect.html.

giovedì 12/3/2020 10,00 - 13,00. Lezione in streaming: ancora sulla notazione asintotica, esempi e uso nell'analisi del tempo di esecuzione di un algoritmo. NotAsint.pdf: file aggiornato

martedì 10/3/2020 11,00 - 13,00. Lezione in streaming: notazione asintotica, definizione, esempi e uso nell'analisi del tempo di esecuzione di un algoritmo. In questo file i lucidi della lezione.

martedì 10/3/2020 11,00 - 13,00. Lezione in streaming: notazione asintotica, definizione, esempi e uso nell'analisi del tempo di esecuzione di un algoritmo. In questo file i lucidi che userò domani: NotAsint.pdf.

giovedì 5/3/2020 10,00 - 13,00. Lezione annullata per coronavirus

martedì 3/3/2020 11 - 13,00. Lezione annullata per coronavirus

giovedì 27/2/2020 10,00 - 13,00. Introduzione al corso. Motivazioni all'approccio teorico rispetto a quello sperimentale per la determinazione del tempo di esecuzione asintotico di un algoritmo. Confronto di algoritmi equivalenti: la determinazione dei doppioni in un array. L'esempio della ricerca lineare per introdurre il caso peggiore e il caso migliore.

Diario delle lezioni a.a. 2018/2019.

giovedì 30/5/2019 11 - 13,00 seconda prova di esonero.

martedì 28/5/2019 10,30 - 13,00 Esercizi riassuntivi sulla seconda parte del corso. Esercizi proposti: la relazione di ricorrenza T(n) = 16T(n/4) + Theta(n^2), il calcolo del rango di un nodo di un ABR T dato in input insieme al puntatore alla radice di T, individuazione di un nodo di rango r in un ABR T, individuazione del nodo più a destra con FB=1 a una data profondità k in un AVL, calcolo del mediano in un ABR, cioè dell'elemento di rango n/2, effettuando un'unica visita dell'albero. Calcolo del minimo numero di nodi con FB =1 lungo un cammino radice foglia di un AVL. Domani a ora di pranzo metto in rete le soluzioni. EserciziSvolti.pdf.

giovedì 23/5/2019 10,30 - 13,00 La cancellazione negli AVL. AVLcanc.pdf Esercizi su rotazioni e ABR EsABR.pdf.

martedì 21/5/2019 10,30 - 13,00 Alberi binari di ricerca bilanciati. Gli AVL o alberi bilanciati in altezza: definizione ed esempi. Alberi di Fibonacci e dimostrazione che l'altezza di un AVL è logaritmica nel numero dei nodi. Inserimento in AVL. AlberiAVL.pdf.

giovedì 16/5/2019 10,30 - 13,00 Individuazione del minimo e del successivo di un elemento in un ABR. La cancellazione in un ABR. Esercizi sugli ABR: visita inorder iterativa, con l'uso della funzione che calcola il successivo. Il successivo di un elemento calcolato scendendo dalla radice, individuazione del k-simo elemento. Esercizio da svolgere: calcolare il numero delle chiavi in un ABR comprese in un intervallo determinato da due chiavi j e k fornite in input e presenti nell'ABR e confrontare la soluzione con quella ottenuta applicando semplicemente la visita inorder ricorsiva. ABRes1.pdf.

martedì 14/5/2019 10,30 - 13,00 Visita in ampiezza di un albero binario. Tipi di dati astratti: pile, code e dizionari. Alberi binari di ricerca, ABR: definizione, esempi e prime funzioni. AlberiBinariABR.pdf

giovedì 9/5/2019 10,30 - 13,00 Alberi binari: visite e altre funzioni ricorsive. VisiteEs.pdf.

martedì 7/5/2019 10,30 - 13,00 QuickSort, QuickSort.pdf. Alberi binari: visite e altre funzioni ricorsive. Qui degli esercizi risolti sulle relazioni di ricorrenza. RelRic.pdf.

giovedì 2/5/2019 10,30 - 13,00 Esercizi sulle relazioni di equivalenza, metodo della sostituzione. Un caso di previsione sbagliata. Esercizio 1: Risovere T(n) = 2T(n/2) + cnlg n, se n>1 e T(n) = d altrimenti. Es.2 Data una funzione ricorsiva ricavare e risolvere la relativa relazione di ricorrenza. La prima ricorrenza ricavata è T(x) = T(x-1) + cx, se x>1 e T(x) = d altrimenti. La seconda è T(y) = T(y/3) + cy^2, se y > 0, T(y)= d altrimenti.

martedì 30/4/2019 10,30 - 13,00 Il Mergesort ricorsivo: esempio della strategia Divide et Impera. Analisi della complessità del Mergesort con introduzione alle relazioni di ricorrenza. Metodo della sostituzione per risolvere le ricorrenze. MergeSort_con_analisi.pdf.

martedì 15/4/2019 10,30 - 13,00 Counting sort: un algoritmo lineare di ordinamento. Limiti di applicazione e stabilità. [CLRS10] cap. 8 par.8.2. CountingSort.pdf. Soluzioni degli esercizi proposti nella prova intermedia. Qui le soluzioni SolEs12Apr2019.pdf.

venerdì 12/4/2019 11,00 - 13,00 Prima prova intermedia. Qui il testo proposto: Esonero1_2019_04_12.pdf.

giovedì 4/4/2019 10,30 - 13,00 Esercizi sul programma svolto, qui i testi: EsAula4Apr19.pdf.

martedì 2/4/2019 10,30 - 13,00 Heapsort, heapsort.pdf. Limite inferiore al numero dei confronti nel caso peggiore per un algoritmo di ordinamento basato sui confronti. ([CLRS10] cap. 8, par 1) LimInfOrdinamenti.pdf.

giovedì 28/3/2019 10,30 - 13,00 Max-Heap: inserimento e due metodi di trasformazione di una array qualunque in un maxheap. OpHeap.pdf, BuildMaxHeap.pdf.

martedì 26/3/2019 10,30 - 13,00 Alberi, alberi binari e misure fondamentali: numero dei nodi e altezza. Relazione tra numero dei nodi e altezza e tra numero delle foglie e altezza ([CLRS] appendice B.5), AlberiPreliminari.pdf. Heap binari: definizione e prime proprietà. Max-heap: prime operazioni. HeapMaxheap.pdf

giovedì 21/3/2019 10,30 - 13,00 Partizione di un array in due parti, contenenti gli elementi minori o uguali di un elemento dato e quelli maggiori. Esercizi su partizione e ordinamento. ([CLRS10] cap. 7, pag. 142 e problema 7.1) Partition.pdf

martedì 19/3/2019 10,30 - 13,00 Il mergeSort iterativo: progettazione, pseudocodice e analisi. Appunti sul mergesort iterativo: mergesortIt.pdf. Esercizi di applicazione dell'idea di fusione tra array ordinati: la determinazione di un elemento comune tra due array ordinati l'ordinamento di un array che da ordinato viene modificato diminuendo il valore di k elementi. In questo file le soluzioni: EsMerge.pdf

giovedì 14/3/2019 10,30 - 13,00 Creare un array ordinato fondendo due array ordinati, dividere un array in due porzioni contenenti l'una gli elementi minori o uguali a un dato elemento e l'altra i maggiori. Esercizi di analisi di algoritmi iterativi: [[https://twiki.di.uniroma1.it/pub/Intro_algo/AD/PaginaWebPrecedente/EsAnAlgIt.pdf][EsAnAlgIt.pdf].

martedì 12/3/2019 10,30 - 13,00 Descrizione e analisi di algoritmi per l'ordinamento incrementali. In queste slide i tre algoritmi OrdQuadr.pdf. Esercizi di determinazione del tempo di esecuzione asintotico, analisi, di frammenti di pseudocodice. Qui ancora qualche esercizio sulla notazione asintotica: EsNotazioneAsintotica.pdf.

giovedì 7/3/2019 10,30 - 13,00 Notazione Omega grande e O grande: esempi ed esercizi. Uso delle notazioni nell'analisi degli algoritmi: esempi ed esercizi. [CLRS] pag. 38-41 oppure consultate le dispense qui: http://twiki.di.uniroma1.it/pub/Infogen/DispenseELibriDiTesto/Capitolo_2.pdf Analisi dell'algoritmo per la ricerca binaria e della sua variante nella quale l'output è il punto di inserimento più a destra di altre eventuali occorrenze già presenti di un elemento, in un array ordinato, RBISECT. Seguire questo link per una specifica https://docs.python.org/2/library/bisect.html. L'inserimento di un elemento in un array ordinato: il caso particolare in cui l'elemento da inserire è l'ultimo e quindi l'input è costituito di un array di interi ordinato fino alla penultima entrata e l'output è lo stesso array completamente ordinato. Analisi dell'algoritmo semplice in cui l'elemento da inserire è confrontato con gli elementi dell'array da destra verso sinistra e in cui ogni elemento maggiore di quello da inserire è spostato a destra di una posizione. Confronto con l'algoritmo in cui la ricerca della corretta posizione di inserimento è eseguita utilizzando la RBISECT.

martedì 5/3/2019 10,30 - 13,00 Il problema dello spostamento dei k elementi più grandi nelle prime k posizioni in un array. Soluzione algoritmica basata sul calcolo del massimo tra gli n-i elementi rimanenti quando i primi i più grandi sono già stati scambiati e sua analisi. Conteggio dei confronti eseguiti su un array di n elementi. Definizione di Theta grande ed espressione del tempo di esecuzione dell'algoritmi presentato in termini di Theta grande. Esempi di dimostrazioni di appartenenza a Theta grande di semplici funzioni. Seconda soluzione algoritmica per il problema dello spostamento dei k elementi più grandi nelle prime k posizioni in un array. Calcolo del minimo tra i primi k elementi e suo scambio con l'elemento i-simo se questo risulta maggiore del minimo calcolato. Correttezza dell'algoritmo basata sull'osservazione che all'i-simo passo gli elementi da indice k a indice i-1 sono minori o uguali dei primi k elementi (o perché l'elemento confrontato era già minore o uguale del minimo o a seguito dello scambio). Analisi dell'algoritmo e confronto con la prima soluzione. Riferimento: [CLRS] pag 35-38 oppure consultate le dispense qui: http://twiki.di.uniroma1.it/pub/Infogen/DispenseELibriDiTesto/Capitolo_2.pdf

giovedì 28/2/2019 10,30 - 13,00 lezione cura della prof.ssa Petreschi. Rappresentazione dell'algoritmo di ricerca dicotomico su un albero decisionale. Algoritmo per la valutazione di un polinomio: dal tempo quadratico al tempo lineare. Approfondimento sul concetto di algoritmo e sulla sua efficienza. Confronto, al crescere di n, di funzioni tipiche del calcolo dell'efficienza. Calcolo della linearità dell' algoritmo per il conteggio di iterazioni tramite serie geometrica. Calcolo tramite serie armonica dell' algoritmo per il conteggio di iterazioni in tempo nlogn.

martedì 26/2/2019 10,30 - 13,00 Introduzione al corso a cura della prof.ssa Petreschi. Algoritmo: etimologia della parola e suo significato. Precisone,Finitezza ed Eseguibilità di un algoritmo Introduzione alla efficienza computazionale. Algoritmo di Euclide per la ricerca del MCD: soluzione lineare (per sottrazioni successive) e soluzione logaritmica (per divisioni successive). Algoritmo per la somma dei primi n numeri interi: soluzione in tempo lineare e soluzione in tempo costante. Algoritmo per la ricerca di un elemento in un vettore qualunque. Algoritmo per la ricerca di un elemento in un vettore ordinato.

Diario delle lezioni a.a. 2017/2018.

Programma dettagliato a.a. 2017/18

Qui trovate il programma dettagliato di questo a.a. ProgrammaIntrAlg1718.pdf.

martedì 4/6/2018 10,30 - 13,00 Esercitazione riassuntiva argomenti del corso.

giovedì 31/5/2018 8,00 - 10,30 (al posto della lezione di Calcolo numerico, che si terrà a seguire dalle 10,45) Seconda prova in aula, il testo degli esercizi proposti: IntrAlg31mag18.pdf.

martedì 29/5/2018 10,45 - 13,15 esercizi riassuntivi sulla seconda parte del programma. EsAVL.pdf.

giovedì 24/5/2018 10,45 - 13,15 La cancellazione in un AVL. AVLcanc.pdf

martedì 22/5/2018 L'inserimento in un AVL. Esercizi sugli AVL.

giovedì 17/5/2018 10,45 - 13,15. Ancora esercizi su ABR. ABResercizi2.pdf. Operazioni per modificare gli ABR: le rotazioni, RotazioniABR.pdf. Alberi AVL: definizione ed esempi. Alberi di Fibonacci e dimostrazione che l'altezza di un AVL è O(lg n) AlberiAVL.pdf.

martedì 15/5/2018 10,45 - 13,15 La cancellazione di un elemento in un ABR. ABRcancellazione.pdf, Esercizi sugli ABR, ABResercizi1.pdf.

giovedì 10/5/2018 10,45 - 13,15 Il minimo, il massimo, il successivo e il precedente di un elemento in un ABR. Definizione ricorsiva di ABR e algoritmi per stabilire se un albero binario è un ABR. Esercitazione in aula: una relazione di ricorrenza ricavata dall'analisi di un algoritmo.

martedì 8/5/2018 10,45 - 13,15 Ancora esercizi su alberi binari. Alberi binari di ricerca: definizione ed esempi. La ricerca di un elemento in un ABR AlberiBinariABR.pdf

lunedì 7/5/2018 10,45 - 13,15 lezione di introduzione agli algoritmi al posto della lezione di Calcolo integrale del professor Orsina Alberi binari: visite in profondità e per livelli ed esempi di algoritmi ricorsivi su alberi. AlbBinVisiteEs.pdf.

venerdì 4/5/2018 10,45 - 13,15 lezione di introduzione agli algoritmi al posto della lezione di Architettura degli elaboratori del professore Mei Ancora sulle relazioni di ricorrenza e il Quiksort. QuickSort.pdf. RelRic.pdf.

giovedì 3/5/2018 10,45 - 13,15 normale lezione di introduzione agli algoritmi. La ricorsione: Mergesort e la sua relazione di ricorrenza. Soluzioni esercizi della prova intermedia. SolPIAlg19apr2018.pdf, MergeSort_con_analisi.pdf.

martedì 1/5/2018 Festa del lavoro - niente lezione

giovedì 26/4/2018 Dalle 10,30 alle 13 lezione di Architettura degli elaboratori del professore Mei

martedì 24/4/2018 Dalle 10,30 alle 13 lezione di Calcolo integrale del professore Orsina

giovedì 19/4/2018 2 ore e mezza dalle 9,30 alle 13 - Prova di esonero -

giovedì 12/4/2018 Esercizi di progettazione e analisi di algoritmi. EsMaxHep.pdf, MinMax.pdf, Es10Aprile18.pdf.

martedì 10/4/2018 Come ordinare in tempo lineare dei numeri di un intervallo: CountingSort.pdf. Esercizi di progettazione e analisi di algoritmi, MassimoLocale.pdf.

giovedì 5/4/2018 Costruire un maxheap, BuildMaxHeap.pdf, code di priorità CodePriorita.pdf.

martedì 27/3/2018 Heap binario, max-heap e heapsort, heapsort.pdf. Correzione esercizi proposti in aula. SolEs2232018serie1.pdf, SolEs2232018serie2.pdf.

giovedì 22/3/2018 10,45 - 12,15 Limite inferiore all'ordinamento: LimInfOrdinamenti.pdf, 12,30 - 13,15 Esercitazione sulla notazione asintotica e il suo uso nell'analisi degli algoritmi. I testi: Es2232018serie2.pdf, Es2232018serie1.pdf.

martedì 20/3/2018 Ancora applicazioni di merge e partition: mergeSortIt.pdf, EserciziMergeEMergeSort.key. Gli alberi, terminologia e relazioni tra altezza e numero dei nodi o foglie: AlberiPreliminari.pdf.

giovedì 15/3/2018 3 ore; Il problema della fusione di arrays ordinati in un unico array ordinato e il problema della partizione di un array qualunque intorno a un pivot. Merge_e_Partition.pdf. Esercizi: EsMergePartition.pdf, Tripartizione.pdf.

martedì 13/3/2018 2h 30m. Ordinamenti quadratici, OrdQuadr.pdf Esercizi sulla notazione asintotica e altro: EsNotAsintEvari.pdf.

giovedì 8/3/2018 3 ore; Notazione asintotica: Theta grande. Esempi di analisi di semplici algoritmi ComplessitaII.pdf

martedì 6/3/2018 3 ore; Esempi di analisi tempo di esecuzione: accesso a un elemento di una lista Python, inserimento di un elemento in una posizione della lista, inserimento in una lista ordinata Complessit.pdf

giovedì 1/3/2018 3 ore; Introduzione al corso. AlgIntrCorso18.pdf.

Diario delle lezioni a.a. 2016/2017.

martedì 30/5/2017 5 ore; Dalle 14 -17,30 Esercizi su relazioni di ricorrenza, ABR e AVL. EsBSTAVL.pdf, EsRelRic.pdf.

giovedì 25/5/2017 3 ore; Cancellazione in un AVL. AVLcanc.pdf. Esercizi su ABR: EserciziABR.pdf.

martedì 23/5/2017 3 ore; Inserimento in un AVL.

giovedì 18/5/2017 4 ore; alberi binari di ricerca: la cancellazione. ABRcancellazione.pdf, Alberi AVL. Dimostrazione che un AVL ha altezza logaritmica. AlberiAVL.pdf. Esercizio relazione di ricorrenza.

martedì 16/5/2017 3 ore; alberi binari di ricerca: una struttura dati per il dizionario. Le operazioni fondamentali. ABR.pdf. Discussione prova intermedia

giovedì 11/5/2017 3 ore; alberi binari, visite e applicazioni delle visite per risolvere problemi su alberi. AlbBinVisiteEs.pdf.

martedì 9/5/2017 2 ore; Code di priorità: CodePriorit.pdf, esercizi: Span_problem.pdf, esOrdinamenti.pdf.

lunedì 8/5/2017 3 ore; Ancora qualche relazione di ricorrenza. Pile e code nella progettazione di algoritmi PileCode.pdf, soluzioni degli esercizi della prova intermedia: solPIIntrAlg20162017.pdf

giovedì 4/5/2017 3 ore; Quicksort. QuickSort.pdfRelazioni di ricorrenza: esempi RelRic.pdf.

martedì 2/5/2017 2 ore; Divide et impera: mergesort e relazioni di ricorrenza per l'analisi degli algoritmi ricorsivi, MergeSort.pdf

giovedì 27/4/2017 3 ore; Il prof. Orsina anticiperà oggi la sua lezione dell'otto maggio.

martedì 25/4/2017 2 ore; festa nazionale

giovedì 20/4/2017 3 ore; settimana prove intermedie, didattica sospesa

martedì 18/4/2017 2 ore; vacanze pasquali

giovedì 13/4/2017 3 ore; vacanze pasquali

martedì 11/4/2017 2 ore; settimana prove intermedie, didattica sospesa

lunedì 10/4/2017 4 ore; prova intermedia.

giovedì 6/4/2017 3 ore; lezione scambiata con il prof. Cenciarelli, quindi nelle prime due ore la lezione è di Metodologie di Programmazione.

martedì 4/4/2017 2 ore; lezione anticipata prolungando le lezioni del martedì

giovedì 30/3/2017 in aula 201 di Giurisprudenza, edificio CU002. 3 ore; esercizi riassuntivi sugli argomenti del programma svolto. Es30M2017.pdf.

martedì 28/3/2017 2 ore e mezza; esercizi riassuntivi suoi argomenti del programma svolto. Es28marzo2017.pdf.

venerdì 24/3/2017 2 ore e mezza; Un ordinamento in tempo lineare: il counting sort. Stabilità degli ordinamenti. CountingSort.pdf. Esercizi sugli ordinamenti: EserciziOrdin.pdf.

giovedì 23/3/2017 in aula 201 di Giurisprudenza, edificio CU002. 3 ore; Heapsort. La trasformazione di un array in un max-heap in tempo lineare. BuildMaxHeap.pdf. Esercizi su ordinamenti, su fondi e partition e su notazione asintotica e maxheap. SolEsHeap.pdf, INTERVALLI.pdf, RicercaMatrice.pdf.

martedì 21/3/2017 2 ore e mezza; Fine partition di Hoare, tripartizione. Heap binario e max-heap. heapsort2.pdf Esercizio ricerca di un massimo locale MassimoLocale.pdf, Esercizi proposti su Max-heap EserciziHeap.pdf.

giovedì 16/3/2017 3 ore; Limite inferiore all'ordinamento: LimInfOrdinamenti.pdf, Merge e Partition: due funzioni fondamentali. Merge_e_Partition.pdf, esercizi notazione asintotica: EsNotazioneAsintoticaSol.pdf.

martedì 14/3/2017 2 ore e mezza; Fine ordinamenti quadratici, esercizi su ordinamenti. Alberi, alberi binari e misure sugli alberi AlberiPreliminari.pdf. Esercizio di progettazione algoritmi: il massimo in un array bitonico, Bitonico.pdf. Esercizio ordinamenti: EserciziOrdin.pdf.

martedì 7/3/2017 2 ore; lezione annullata per malattia

lunedì 6/3/2017 3 ore; Ordinamenti quadratici. Esercizi sulla notazione asintotica e il suo uso nell'analisi degli algoritmi. OrdQuadr.pdf

giovedì 2/3/2017 3 ore; Notazione asintotica. ComplessitII.pdf

martedì 28/2/2017 2 ore; Introduzione all'analisi del tempo di esecuzione degli algoritmi. * Complessit.pdf

giovedì 23/2/2017 3 ore; Introduzione al corso. AlgIntrCorso1617.pdf.

-- EmanuelaFachini - 23 Feb 2009

-- EmanuelaFachini - 23 Feb 2009

-- EmanuelaFachini - 23 Feb 2009

Intro_algo/AD Web Utilities