WebHome < Intro_algo/EO

Tags: view all tags
---++!! <big>Introduzione agli Algoritmi  (Corso di Laurea in Informatica)</big>

---+++!! A.A. 2014-2015, secondo semestre, secondo canale

<table width="100%" border=0 cellpadding=0>
<tr>

<td width="75%" valign="top">

<table width="100%" border=0 cellspacing=0>
<tr> <td valign="top">

<font color=#AF0F0F size="+1"><b>Docente: [[http://www.dsi.uniroma1.it/~finocchi][Irene Finocchi]]</b></font>

*Ricevimento*: giovedì 14:00-15:30 durante il corso (speditemi mail prima di venire), per appuntamento al termine del corso. 
Ufficio: sede di Via Salaria, stanza 345/A. Tel: 06-49918426. E-mail: finocchi AT di.uniroma1.it

</td></tr>

<tr> <td valign="top">

<font color=#AF0F0F size="+1"><b>Esercitatore: [[http://wwwusers.di.uniroma1.it/~carlucci/][Lorenzo Carlucci]]</b></font>

*Ricevimento*: su appuntamento via e-mail. 
Ufficio: sede di Viale Regina Elena, Palazzina G II piano st. G26. Tel: 06-49255163. E-mail: carlucci AT di.uniroma1.it


</td></tr>
</table>

</td>

<td width="25%" valign="top"  style="border-left: 1px solid #999999; ">

%TOC%

</td>

</tr>
</table>


---++++Avvisi

   * *<font color=#AF0F0F>APPELLO STRAORDINARIO APRILE 2016</font>*: l'appello si svolgerà giovedì *14 aprile* alle *ore 9:00* in *Aula 13 (Via Scarpa)*, in concomitanza con la prova intermedia del canale MZ A.A. 2015-2016. E' obbligatoria la prenotazione su Infostud.

   * [[%ATTACHURL%/risultatiIntroAlgo1Febbraio2016.pdf][Risultati appello del 1 febbraio]]: per le verbalizzazioni, giovedì 25 febbraio ore 11:00 nel mio ufficio. Nel caso in cui non possiate venire in tale data contattatemi per email. Se non avete necessità di vedere il compito, posso verbalizzare direttamente io su Infostud: anche in questo caso contattatemi per email prima del 25 febbraio.

   * <font color=#AF0F0F><b>Appello del 1 febbraio</b></font>: come indicato sulla pagina degli appelli nel sito del [[http://www.studiareinformatica.uniroma1.it/appelli-di-esame-gennaio-e-febbraio-2016-corsi-di-studio-informatica][corso di studio in Informatica]], l'appello del 1 febbraio gennaio si svolgerà in *aula Gini (edificio di statistica) alle ore 9:00*. Chi deve sostenere solo la seconda parte può presentarsi alle 10:30.

   * [[%ATTACHURL%/IntroAlgoGennaio2016.pdf][Risultati esame 13 gennaio 2016]]: gli studenti che devono verbalizzare, avendo superato entrambe le parti, possono presentarsi venerdì alle 14:30 per avere la firma sul certificato d'esame. Se invece non avete bisogno del certificato e non volete vedere il compito, posso verbalizzare direttamente io su Infostud: in tal caso fatemi sapere per email se posso procedere.

   * <font color=#AF0F0F><b>Appello del 13 gennaio</b></font>: come indicato sulla pagina degli appelli nel sito del [[http://www.studiareinformatica.uniroma1.it/appelli-di-esame-gennaio-e-febbraio-2016-corsi-di-studio-informatica][corso di studio in Informatica]], l'appello del 13 gennaio si svolgerà in *aula 13 alle ore 9:00*. Chi deve sostenere solo la seconda parte può presentarsi alle 10:30.

   * *<font color=#AF0F0F>RISULTATI APPELLO STRAORDINARIO</font>*: gli unici due studenti che hanno avuto una sufficienza all'appello straordinario sono Ornati (20 alla parte 1, parte 2 da rifare nella sessione invernale) e Samele (18 alla parte 1, parte 2 da rifare nella sessione invernale). Contattatemi per email per prendere un appuntamento nel caso in cui vogliate vedere gli errori commessi.

   * *<font color=#AF0F0F>APPELLO STRAORDINARIO</font>*: l'esame si svolgerà il *5 novembre* alle *ore 9:00* in *aula seminari* (via Salaria 113, terzo piano). Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 10:30. E' obbligatoria la prenotazione su Infostud.

   * *<font color=#AF0F0F>RISULTATI APPELLO DEL 3 SETTEMBRE  2015</font>*: [[%ATTACHURL%/risultatiSettembre2015.pdf][risultati]]. 
      * Poiché sarò all'estero per motivi di lavoro, gli studenti che hanno superato entrambe le parti (o coloro che vogliono vedere i propri errori) possono presentarsi *giovedì 1 ottobre*, alle ore 9:30, presso il mio ufficio. Manterrò l'appello aperto fino a tale data. 
      * Chi ha superato solo una delle due parti può completare l'esame nell'appello di gennaio o febbraio (ultima data disponibile: dopo tale data il voto acquisito a una singola parte andrà perso).
      * Le studentesse Marcozzi e Scangella sono pregate di presentarsi all'orale alle 9:30.

   * *<font color=#AF0F0F>APPELLO DEL 3 SETTEMBRE  2015</font>*: la prima parte dell'esame avrà inizio alle ore 9:30. Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 11:00. La prova per entrambi i canali si svolgerà in *aula 1 di ingegneria*.  L'aula 13 non è disponibile contrariamente a quanto disposto in un primo momento e solo l'aula 1 di ingegneria è disponibile, esclusivamente di mattina. 

   * *<font color=#AF0F0F>RISULTATI APPELLO DEL 2 LUGLIO  2015</font>*: [[%ATTACHURL%/risultati_2_07_15_parte1.pdf][parte1]], [[%ATTACHURL%/risultati_2_07_15_parte2.pdf][parte2]]. Gli studenti che hanno superato entrambe le parti (o coloro che vogliono vedere i propri errori) possono presentarsi *venerdì 24 luglio*, ore 9:30, presso il mio ufficio. Chi ha superato solo una delle due parti può completare l'esame nell'appello del 3 settembre.

   * *<font color=#AF0F0F>VERBALIZZAZIONI APPELLO DEL 2 LUGLIO  2015</font>*: le verbalizzazioni avranno luogo nella settimana 20 - 24 luglio. Controllate il sito Web dopo il 15 luglio per ulteriori avvisi in merito.  

   * *<font color=#AF0F0F>APPELLO DEL 2 LUGLIO  2015</font>*: la prima parte dell'esame avrà inizio alle ore 9:30. Gli studenti esonerati dalla prima parte devono presentarsi direttamente alle 11:00. La prova per il canale 2 (MZ) si svolgerà in *aula 13 di ingegneria*, dove solitamente si tengono le lezioni del primo canale (l'aula 13 si trova in Via Antonio Scarpa 12, una traversa di Via del Castro Laurenziano).  

   * [[%ATTACHURL%/IntroAlgoritmiRisultati9giugno2015.pdf][Risultati appello del 9 giugno 2015]]: per la verbalizzazione e la visione del compito, *martedì 23*, *ore 9:30*, presso il mio studio in Via Salaria, stanza 345A. 

   * [[%ATTACHURL%/esonero2015.pdf][Risultati prova intermedia]]

<!--

ESAMI 2013 - 2014

   * [[%ATTACHURL%/RisultatiIntro27Gennaio2015.pdf][Risultati appello 27 Gennaio 2015]]: la verbalizzazione e l'eventuale visione del compito si svolgeranno *martedì 10 febbraio, ore 9:30*, presso il mio studio. Essendo quello del 27 gennaio l'ultimo appello previsto per il corso svolto nell'A.A. 2013-2014, gli studenti che alla data odierna hanno ottenuto la sufficienza solo su una delle due parti del compito, dovranno risostenere l'esame *per intero* a partire dal primo appello disponibile.

   * *<font color=#AF0F0F>RISULTATI APPELLO 9 GENNAIO  2015</font>*: la verbalizzazione si svolgerà ad inizio febbraio, in concomitanza con quella dell'appello del 27 gennaio. La data precisa sarà annunciata a breve. 

| *Cognome* | *Es. 1* | *Es. 2* | *Es. 3* | *Es. 4* | *Voto proposto* |
| Magnanini | 6 | 2 | 7 | 6 | insuff |
| Manduca | 11 | 7 | 3 | 1 | 18 parte 1. Rifare parte 2 il 27 gennaio |
| Rampello | 15 | 7 | 6 | 14 | 21 |
| Samele | 7 | 1 | 1 | 4 | insuff |
| Schifalacqua | 13 | 0 | 8 | - | insuff |

  * *<font color=#AF0F0F>RISULTATI APPELLO STRAORDINARIO NOVEMBRE 2014</font>*. Gli studenti che hanno ottenuto la sufficienza sono: Mohammad (voto finale 18), Paladini (voto finale 23), Provenzano (voto finale 19). Per la verbalizzazione contattare il docente.

   * [[%ATTACHURL%/votiSettembre2014.pdf][Risultati appello Settembre 2014]]: gli studenti che hanno ottenuto la sufficienza sia sulla prima che sulla seconda parte del compito possono verbalizzare il giorno *venerdì 3 ottobre* alle ore *10:00* presso il mio studio. Nella stessa data sarà anche possibile visionare il compito per tutti gli studenti. Gli studenti che hanno ottenuto la sufficienza solo in una delle due parti possono completare l'esame, rifacendo lo scritto sulla parte insufficiente, nella sessione invernale.

   * [[%ATTACHURL%/risultati10luglio2014.pdf][Risultati appello Luglio 2014]]: gli studenti che hanno ottenuto la sufficienza sia sulla prima che sulla seconda parte del compito possono verbalizzare il giorno 24 luglio alle ore 15:00 presso il mio studio. Nella stessa data sarà anche possibile visionare il compito per tutti gli studenti. Gli studenti che hanno ottenuto la sufficienza solo in una delle due parti possono completare l'esame, rifacendo lo scritto sulla parte insufficiente, nell'appello di settembre.

   * [[%ATTACHURL%/risultatiIntroAlgoGiugno2014.pdf][Risultati appello Giugno 2014]]: per la verbalizzazione, *giovedì 3 luglio ore 15:00* nel mio studio.

   * *<font color=#AF0F0F>PROVA INTERMEDIA E APPELLO STRAORDINARIO</font>*: [[%ATTACHURL%/risultati14apr2014.pdf][risultati]]

ALTRI AVVISI

*E' obbligatorio prenotarsi alla prova intermedia entro venerdì 11 aprile*, seguendo [[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2014_04_14_IntroduzioneAgliAlgoritmiCanale2][questo link]]. 

   *<font color=#AF0F0F>DATE D'ESAME</font>*: 
   * scritto martedì *4 giugno* aula V Mat, ore 9:00 (verbalizzazione ed eventuali orali: venerdì *7 giugno* in Sala Riunioni, Via Salaria, ore 9:00);  
   * scritto martedì *25 giugno* aula V Mat, ore 9:00 (verbalizzazione ed eventuali orali: martedì *9 luglio* in Sala Riunioni, Via Salaria, ore 9:00);
   * scritto martedì *10 settembre* aula 1 NEC, ore 9:30 (verbalizzazione ed eventuali orali: data da definire, Via Salaria, stanza 345/A);

   * Ordinamento... a suon di musica!: [[http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html][buon divertimento]]! 

   * Auguri! <img src="%ATTACHURLPATH%/tree.png" alt="tree.png" width='35%' />

   * <font color=#AF0F0F><b>Preparazione all'esame</b></font>: vi segnalo una corposa lista di esercizi utili per prepararsi all'esame. Gli esercizi (disponibili su questo sito Web o sul libro di testo) si riferiscono principalmente agli argomenti trattati nella seconda parte del corso. Per gli esercizi relativi alla prima parte, guardate il corrispondente avviso "Preparazione all'esonero". Buon lavoro!
      * Le esercitazioni 5 e 6 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli) 
      * La dispensa 5 del Dott. Carlucci
      * Esercizio 3 degli appelli del 5 febbraio 2009, 22 gennaio 2009, 9 settembre 2008, 17 giugno 2008, 11 febbraio 2008, 28 gennaio 2008
      * Esercizio 4 dell'appello del 17 giugno 2008
      * Dal libro di testo: esercizi 3.4, 3.5, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.10 (solo per alberi AVL), 7.1, 7.2, 7.3, 7.5. 
      * Dal libro di testo: problemi 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 4.8, 4.9, 4.10, 4.11, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 7.1, 7.2, 7.3, 7.4, 7.5.

   * <font color=#AF0F0F><b>Preparazione all'esonero</b></font>: vi segnalo una corposa lista di esercizi utili per prepararsi all'esonero. Gli esercizi sono disponibili su questo sito Web (in alcuni casi ci sono anche le soluzioni) o sul libro di testo. Vi segnalo anche le dispense messe in rete dal Dott. Carlucci. Buon lavoro!
      * Le esercitazioni 1, 2, 3 e 4 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. De Agostino) 
      * Le esercitazioni 2, 3 e 4 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli) 
      * Paragrafo 2 (solo punti 2 e 3) dell'esercitazione 5 di Algoritmi I dell'A.A. 2008-2009 (a cura del Dott. Accattoli) 
      * Prove intermedie del 14 novembre 2007 e del 27 novembre 2008
      * Esercizio 2 dell'appello del 28 gennaio 2008
      * Esercizi 1 e 2 degli appelli dell'11 febbraio 2008, 17 giugno 2008, 9 settembre 2008, 22 gennaio 2009, 5 febbraio 2009
      * Dal libro di testo: esercizi 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 2.6, 2.7, 2.8, 2.9, 2.11, 3.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.9, 4.12, 4.13, 4.14
      * Dal libro di testo: problemi 1.3, 1.4, 2.2, 2.3, 2.4, 2.6, 2.8, 2.9, 2.10, 3.3, 4.1, 4.3, 4.4, 4.5, 4.7, 4.12, 4.13, 5.1, 5.2
-->

---++++Orario lezioni 

| *Giorno* | *Ore* | *Aula* |
| Lunedì | 8:45-10:15 | Aula 1 - Aule L di Ingegneria |
| Giovedì | 8:45-11:15 | Aula 1 - Aule L di Ingegneria |

---++++Mailing list del corso

Iscrivetevi alla <a href="http://groups.google.com/group/intro_alg_finocchi?hl=en">mailing list</a> su Google Groups. La mailing list sarà usata per discutere gli esercizi assegnati durante il corso, per porre domande di interesse generale al docente ed all'esercitatore, per avvisare tempestivamente gli studenti di qualsiasi problematica inerente al corso. 

<table border=0 style="background-color: #fff; padding: 5px;" cellspacing=0>
  <tr><td>
  <img src="http://groups.google.com/intl/en/images/logos/groups_logo_sm.gif" height=30 width=140 alt="Google Groups">
  </td></tr>
  <tr><td style="padding-left: 5px">
  <b>Subscribe to Introduzione agli Algoritmi (Sapienza, Irene Finocchi)</b>
  </td></tr>
  <form action="http://groups.google.com/group/intro_alg_finocchi/boxsubscribe">
  <input type=hidden name="hl" value="en">
  <tr><td style="padding-left: 5px;">
  Email: <input type=text name=email>
  <input type=submit name="sub" value="Subscribe">
  </td></tr>
</form>
<tr><td align=right>
  <a href="http://groups.google.com/group/intro_alg_finocchi?hl=en">Visit this group</a>
</td></tr>
</table>


---++++Obiettivi e programma

In questo corso, attraverso lo studio di algoritmi e strutture dati classiche, acquisirete la capacità di analizzare problemi e progettare soluzioni algoritmiche corrette ed efficienti. Apprenderete inoltre varie tecniche utili per analizzare le prestazioni di un algoritmo tramite strumenti matematici rigorosi.

Formalmente non ci sono insegnamenti propedeutici. Sono comunque fondamentali le conoscenze impartite nel corso di Fondamenti di Programmazione ed una conoscenza di base di analisi matematica (soprattutto studio di funzioni e serie numeriche).

*Per un buon esito dell'esame è fondamentale seguire le lezioni, svolgere gli esercizi assegnati settimanalmente e preparare l'esame di pari passo con lo svolgimento del corso.*

<font color=#AF0F0F><b>Programma del corso</b></font> 
   * Introduzione all'algoritmica
      * Metodi per l'analisi delle risorse di calcolo utilizzate da algoritmi iterativi e ricorsivi [cap. 1 fino al par. 1.6]
      * Notazione asintotica [par. 2.2]
      * Caso peggiore e caso migliore. Cenni all'analisi nel caso medio [par. 2.3 e 2.4]
      * Soluzione di equazioni di ricorrenza: metodo di iterazione, metodo di sostituzione, teorema master (senza dimostrazione) [par. 2.5]
   * Strutture dati fondamentali
      * Pile [par. 3.1 e 3.2]
      * Code [par. 3.1 e 3.2]
      * Code con priorità: heap binari [par. 4.3.1]
   * Principali algoritmi di ricerca ed ordinamento
      * Ricerca sequenziale e binaria [par. 2.4]
      * Ordinamenti quadratici: bubbleSort, selectionSort, insertionSort [par. 4.2]
      * Ordinamenti ottimi: mergeSort, heapSort [par. 4.3 e 4.4]
      * !QuickSort (solo analisi nel caso peggiore ed intuizione del caso medio) [par. 4.5]
      * Lower bound per il problema dell'ordinamento tramite confronti [par. 4.1]
      * Ordinamenti lineari: integerSort [par. 4.6]
   * Alberi
      * Rappresentazioni in memoria indicizzate e collegate [par. 3.3]
      * Visita per livelli [par. 3.3]
      * Visite in profondità [par. 3.3]
   * Dizionari
      * Alberi binari di ricerca: definizione ed operazioni fondamentali [par. 6.1]
      * Alberi AVL: fattore di bilanciamento, rotazioni, operazioni fondamentali [par. 6.2]
<!--      * Tabelle hash [cap. 7]. -->

Per tutti gli algoritmi presentati nel corso si richiede la conoscenza delle dimostrazioni di correttezza e complessità.

Per maggiori informazioni guardate anche il [[Intro_algo/EO.DiarioLezioni][diario delle lezioni]].

---++++Modalità e date d'esame

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.

In generale, il superamento della prova scritta permette di verbalizzare il voto conseguito. Il docente ha però facoltà di richiedere un colloquio orale suppletivo in casi specifici tra cui: sufficienza non piena allo scritto, sospetto di copiatura, votazione alta (con possibilità di lode), dubbi nell'interpretazione del compito.

<b>Prova intermedia.</b> E' prevista una prova intermedia nella settimana di interruzione della didattica. La prova riguarderà tutti gli argomenti svolti fino alla data della prova stessa.  La sufficienza ottenuta alla prova intermedia è  valida fino all'ultimo appello dell'anno accademico di riferimento. La prova intermedia è anch'essa strutturata in esercizi di ragionamento e domande di comprensione.

<font color="#AF0F0F"><b>Data prova intermedia:</b></font> *martedì 14 aprile 2015*, *data soggetta a conferma* (da parte della segreteria didattica).

<b>Appelli.</b> Ci saranno cinque appelli, rispettivamente due nella sessione estiva (giugno-luglio), uno in settembre, due nella sessione invernale (gennaio- febbraio).  Tutti gli appelli saranno divisi in due parti. Lo studente potr&agrave;  sostenere tutto l'esame oppure affrontare una prova sugli stessi argomenti di quella intermedia in un appello e completare la prova scritta in un appello successivo. 

<font color="#AF0F0F"><b>Date appelli:</b></font> da definire da parte della segreteria didattica. *Per informazioni ufficiali su date, orari e luoghi degli appelli fate sempre riferimento al [[http://w3.uniroma1.it/dipinfo/corsi_di_studio/default.asp?iId=LLMEE][calendario pubblicato dalla segreteria didattica]] nelle pagine Web del corso di laurea*. 

<b>Voto.</b> Il voto finale verrà incrementato di un punto per chi termina nella sessione estiva avendo superato la prova intermedia, e di mezzo punto per chi conclude l'esame nella sessione estiva (senza prova intermedia).

<b>Prenotazioni.</b> Per partecipare alle prove scritte (inclusa quella intermedia) è obbligatoria la prenotazione. Sarà possibile prenotarsi agli appelli d'esame tramite infostud, e alla prova intermedia tramite twiki.


---++++Libro di testo

<table width="100%" border=0 cellspacing=0>
<tr> 
<td width="10%" valign="top"> <img src="%ATTACHURLPATH%/DFI08.jpg" alt="DFI08.jpg" width='90'/> </td>
<td valign="top">
<font color=#AF0F0F><b>C. Demetrescu, I. Finocchi, G.F. Italiano, "Algoritmi e Strutture Dati",  2/ed. !McGraw-Hill, 2008.</b></font>

Raccomando l'uso della seconda edizione del libro. Nell'[[http://www.ateneonline.it/demetrescu/areastudentiA.asp][area studenti relativa al libro]], troverete animazioni di alcuni degli algoritmi e delle strutture dati presentati in classe.
</td>
</tr>
</table>

Un utile libro di consultazione è il seguente: T.H. Cormen, C.E. Leiserson, R.L.  Rivest e C. Stein, "Introduction to Algorithms", 2/ed. Mit Press e !McGraw-Hill, 2001.

#DiarioLezioni
---++++Diario delle lezioni

<!--
%CALENDAR{month="3" year="2010" topic="Intro_algo/EO.DiarioLezioni" cellalignment="center" headercontentcolor="#FFFFFF" weekendheadercolor="#edf4f9" weekdayheadercolor="#edf4f9" headercolor="#6b7f93" width="100%" format="$old<br />$description" lang="Italian" showweekdayheaders="1" weekstartsonmonday="1" weekendcolor="#EEEEEE"}%

%CALENDAR{month="4" year="2010" topic="Intro_algo/EO.DiarioLezioni" cellalignment="center" headercontentcolor="#FFFFFF" weekendheadercolor="#edf4f9" weekdayheadercolor="#edf4f9" headercolor="#6b7f93" width="100%" format="$old<br />$description" lang="Italian" showweekdayheaders="1" weekstartsonmonday="1" weekendcolor="#EEEEEE"}%

%CALENDAR{month="5" year="2010" topic="Intro_algo/EO.DiarioLezioni" cellalignment="center" headercontentcolor="#FFFFFF" weekendheadercolor="#edf4f9" weekdayheadercolor="#edf4f9" headercolor="#6b7f93" width="100%" format="$old<br />$description" lang="Italian" showweekdayheaders="1" weekstartsonmonday="1" weekendcolor="#EEEEEE"}%

%CALENDAR{month="6" year="2010" topic="Intro_algo/EO.DiarioLezioni" cellalignment="center" headercontentcolor="#FFFFFF" weekendheadercolor="#edf4f9" weekdayheadercolor="#edf4f9" headercolor="#6b7f93" width="100%" format="$old<br />$description" lang="Italian" showweekdayheaders="1" weekstartsonmonday="1" weekendcolor="#EEEEEE"}%
-->

[[Intro_algo/EO.DiarioLezioni][Diario delle lezioni A.A. 2014-2015]] ed esercizi di riepilogo assegnati periodicamente. 



---++++Esercizi (svolti)

Risolvere esercizi è indispensabile per l'apprendimento e per il superamento di questo esame. Per ogni esercizio, cercate sempre di elaborare una soluzione personale. Leggete le soluzioni (eventualmente) fornite di seguito solo in un secondo momento, al fine di verificare la correttezza del vostro approccio.

<!--
<b>Esercizi</b>

_Esercizio 4._ Proporre un algoritmo ricorsivo, il più possibile efficiente, per verificare se un albero binario T ai cui nodi sono associate chiavi prese da un universo totalmente ordinato è un albero binario di ricerca. Analizzare il tempo di esecuzione nel caso peggiore e nel caso migliore. Ripetere l'esercizio proponendo un algoritmo iterativo.

_Esercizio 5._ Considerare le cinque rappresentazioni di alberi viste in classe: vettore padri, vettore posizionale, puntatori ai figli, lista di figli, primo figlio - fratello successivo. Proporre algoritmi di conversione da una rappresentazione all'altra. Discutere sotto quali ipotesi gli algoritmi proposti operano correttamente (alberi generici, alberi d-ari con d fissato) ed analizzare i tempi di esecuzione delle implementazioni proposte.

   4 Fornire un'implementazione ricorsiva dell'algoritmo per la ricerca dei duplicati visto in classe (e discusso anche nel capitolo 1 del libro [DFFI07]) ed analizzarne il tempo di esecuzione. Risolvere l'equazione di ricorrenza sia tramite l'albero della ricorsione che per iterazione.  
   5 Verificare che i confronti tra elementi sono l'operazione dominante negli algoritmi !InsertionSort, !SelectionSort e !MergeSort.  A tale scopo, calcolate il numero di linee di codice mandate in esecuzione nelle implementazioni proposte e mostrate che tale numero è Theta(numero di confronti).
   6 Nella implementazione del !MergeSort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=(2i+f-2)/3. Con tale scelta, l'array da ordinare viene partizionato in due sottoarray, il secondo dei quali è grande  il doppio del primo. Disegnate l'albero della ricorsione ed analizzate il numero di confronti eseguiti dall'algoritmo risultante. Per semplificare i calcoli, nell'analisi potete assumere che n sia una potenza di 3.
   7 Nella implementazione del !MergeSort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=min { (i+f)/2, i+3 }. Con tale scelta, se c'e' un numero di  elementi sufficiente, l'array da ordinare viene partizionato in due sottoarray, il primo dei quali ha dimensione 4. Disegnate l'albero della ricorsione ed analizzate il numero di confronti eseguiti dall'algoritmo risultante.
   8 Fornire un'implementazione iterativa della procedura fixHeap.
   9 Analizzare, impostando e risolvendo un'equazione di ricorrenza, il numero di confronti eseguiti dall'implementazione ricorsiva della procedura fixHeap nel caso in cui l'heap sia completo fino all' ultimo livello. Come può essere generalizzata la ricorrenza per heap qualsiasi?
   10 Dare una procedura ricorsiva per l' ordinamento a bolle e analizzarne la complessità.
   11 Proporre un algoritmo ricorsivo per verificare se un albero binario T ai cui nodi sono associate chiavi prese da un universo totalmente ordinato è un albero binario di ricerca. Analizzare il tempo di esecuzione nel caso peggiore e nel caso migliore. Ripetere l'esercizio proponendo un algoritmo iterativo.
   12 Implementare le classiche operazioni su un albero binario di ricerca (search, insert, max, pred, delete) assumendo che l'albero sia rappresentato tramite vettore-padri. Discutere i tempi di esecuzione delle implementazioni proposte.
   13 Considerare le cinque rappresentazioni di alberi viste in classe: vettore padri, vettore posizionale, puntatori ai figli, lista di figli, primo figlio - fratello successivo. Proporre algoritmi di conversione da una rappresentazione all'altra. Discutere sotto quali ipotesi gli algoritmi proposti operano correttamente (alberi generici, alberi d-ari con d fissato) ed analizzare i tempi di esecuzione delle implementazioni proposte.
-->

<b>Soluzioni di alcuni degli esercizi del libro di testo</b>

   * [[%ATTACHURL%/problemSet1.pdf][Problema 1.3]]: Tribonacci
<!--   * [[%ATTACHURL%/problemSet2bis.pdf][Problemi 2.4, 2.8 e 2.9]] -->

<b>Appunti di approfondimento ed esercizi svolti a cura del Dott. Carlucci</b>

   * [[%ATTACHURL%/e_01_09_10.pdf][Appunti 1]]: Notazione Asintotica, metodo algebrico e metodo analitico.
   * [[%ATTACHURL%/e_01.pdf][Appunti 2]]: Notazione Asintotica, Logaritmi, Polinomi, Esponenziali, Fattoriali.
   * [[%ATTACHURL%/e_02_09_10.pdf][Appunti 3]]: Logaritmi, polinomi, esponenziali. Numeri di Fibonacci.
   * [[%ATTACHURL%/esercizi_riepilogo_01.pdf][Appunti 4]]: Correzione degli Esercizi di Riepilogo (A). 
   * [[%ATTACHURL%/e_04_09_10.pdf][Appunti 5]]: Ricerca Binaria, Bubble Sort.
   * [[%ATTACHURL%/e_04.pdf][Appunti 6]]: Ricerca binaria ricorsiva, esercizi di riepilogo.
   * [[%ATTACHURL%/e_05_09_10.pdf][Appunti 7]]: Quick Sort.
   * [[%ATTACHURL%/esercizi_esonero_09_10.pdf][Appunti 8]]: Correzione esercizi 2 e 3 dell'esonero A.A. 2009-2010.
   * [[%ATTACHURL%/e_07_09_10.pdf][Appunti 9]]: Counting Sort. Esercizi.
   * [[%ATTACHURL%/e_08_09_10.pdf][Appunti 10]]: Esercizi di riepilogo.
   * [[%ATTACHURL%/e_05.pdf][Appunti 11]]: Alberi.
   * [[%ATTACHURL%/e_06.pdf][Appunti 12]]: AVL e ABR.
   
<!--
<b>Esercizi svolti a cura del Dott. Accattoli</b>

   * [[%ATTACHURL%/esercitazione_02_soluzioni.pdf][Esercitazione 2]]: analisi del tempo di esecuzione di algoritmi ricorsivi
   * [[%ATTACHURL%/esercitazione_3_soluzioni.pdf][Esercitazione 3]]: progettazione di algoritmi, ricerca binaria, notazione asintotica
   * [[%ATTACHURL%/esercitazione_4_soluzioni.pdf][Esercitazione 4]]: equazioni di ricorrenza, heap, analisi di algoritmi ricorsivi, notazione asintotica
   * [[%ATTACHURL%/Esercitazione_5_soluzioni.pdf][Esercitazione 5]]: alberi AVL, algoritmi di ordinamento
   * [[%ATTACHURL%/Esercitazione_6_soluzioni.pdf][Esercitazione 6]]: rappresentazioni e visite di alberi, tabelle hash
<!--   * [[%ATTACHURL%/Esercitazione_7_soluzioni.pdf][Esercitazione 7]]: grafi -->


---++++Compiti d'esame


 <b>Esami di Introduzione agli Algoritmi, A.A. 2013-2014</b>
   * Esonero 14 aprile 2014: [[%ATTACHURL%/testo1_14aprile2014.pdf][testo 1]], [[%ATTACHURL%/testo2_14aprile2014.pdf][testo 2]], [[%ATTACHURL%/testo3_14aprile2014.pdf][testo 3]], [[%ATTACHURL%/testo4_14aprile2014.pdf][testo 4]]

 <b>Esami di Introduzione agli Algoritmi, A.A. 2012-2013</b>

   * [[%ATTACHURL%/EsIntrAlgGennaio2014.pdf][Appello del 23 gennaio 2014]]
   * [[%ATTACHURL%/Esame_IntrAlgo_4Giugno2013.pdf][Appello del 4 giugno 2013]]
   * [[%ATTACHURL%/Esonero16aprile2013.pdf][Esonero del 16 aprile 2013]]
   * [[%ATTACHURL%/Appello7feb2013.pdf][Appello del 7 febbraio 2013]]
   * [[%ATTACHURL%/Appello17gen2013.pdf][Appello del 17 gennaio 2013]]


 <b>Esami di Introduzione agli Algoritmi, A.A. 2011-2012</b>

   * [[%ATTACHURL%/AppelloStraordinario24aprile2012.pdf][Appello straordinario del 24 aprile 2012]]
   * [[%ATTACHURL%/23gennaio2012.pdf][Appello del 23 gennaio 2012]]
   * [[%ATTACHURL%/ProvaIntermedia26aprile2012-testo1.pdf][Prova Intermedia 26 aprile 2012 - testo 1]]
   * [[%ATTACHURL%/ProvaIntermedia26aprile2012-testo2.pdf][Prova Intermedia 26 aprile 2012 - testo 2]]
   * [[%ATTACHURL%/EsIntrAlgLu3-irene.pdf][Appello del 3 luglio 2012]]
   * [[%ATTACHURL%/EsIntrAlgGiu12.pdf][Appello del 12 giugno 2012]]

 <b>Esami di Introduzione agli Algoritmi, A.A. 2010-2011</b>

   * [[%ATTACHURL%/scritto20giugno2011.pdf][Appello del 20 giugno 2011]]
   * Esonero 28 aprile 2011: [[%ATTACHURL%/esonero28aprile2011.pdf][traccia 1]], [[%ATTACHURL%/esonero28aprile2011-B.pdf][traccia 2]]
   * [[%ATTACHURL%/scritto15novembre2011.pdf][Appello del 15 novembre 2011]]

 <b>Esami di Introduzione agli Algoritmi, A.A. 2009-2010</b>

   * [[%ATTACHURL%/IntroAlg2Feb2011.pdf][Appello del 2 febbraio 2011]]
   * [[%ATTACHURL%/esame21luglio.pdf][Appello del 21 luglio 2010]]
   * [[%ATTACHURL%/esame24giugno2010.pdf][Appello del 24 giugno 2010]]
   * [[%ATTACHURL%/EsoneroAlgo290410.pdf][Prova intermedia del 29 aprile 2010]]

 <b>Esami di Introduzione agli Algoritmi, A.A. 2008-2009</b>

   * [[%ATTACHURL%/esame2marzo10.pdf][Appello del 2 marzo 2010]]
   * [[%ATTACHURL%/EsIntrAlg15Sett09.pdf][Appello del 15 settembre 2009]]
   * [[%ATTACHURL%/IntrAlgEs14Lu09.pdf][Appello del 14 luglio 2009]]
   * [[%ATTACHURL%/appello23giu09testo.pdf][Appello del 23 giugno 2009]]
   * [[%ATTACHURL%/esonero23apr09testo.pdf][Prova intermedia del 23 aprile 2009]]

 <b>Esami di Algoritmi I, A.A. 2008-2009</b>

   * [[%ATTACHURL%/AlgoIEs10Set09.pdf][Appello del 10 settembre 2009]]
   * [[%ATTACHURL%/appello6luglio2009.pdf][Appello del 6 luglio 2009]]
   * [[%ATTACHURL%/5feb09.pdf][Appello del 5 febbraio 2009]]
   * [[%ATTACHURL%/appello22gen09.pdf][Appello del 22 gennaio 2009]], sketch soluzione [[%ATTACHURL%/esercizi1e2appello20gen09.pdf][esercizi 1 e 2]]   
   * [[%ATTACHURL%/esonero27nov08.pdf][Prova intermedia del 27 novembre 2008]], [[%ATTACHURL%/esercitazione5.doc][sketch soluzione]] (a cura del dott. De Agostino)

<b>Esami di Algoritmi I, A.A. 2007-2008</b>
 
   * [[%ATTACHURL%/appelloSettembre08.pdf][Scritto del 9 settembre 2008]], sketch soluzione [[%ATTACHURL%/es1_090908.pdf][esercizio 1]]
   * [[%ATTACHURL%/appelloGiugno08.pdf][Scritto del 17 giugno 2008]], sketch soluzione [[%ATTACHURL%/es1_170608.pdf][esercizio 1]]
   * [[%ATTACHURL%/appello11feb08.pdf][Scritto dell'11 febbraio 2008]], sketch soluzione [[%ATTACHURL%/es2_110208.pdf][esercizio 2]]
   * [[%ATTACHURL%/appello28gennaio08.pdf][Scritto del 28 gennaio 2008]], sketch soluzione [[%ATTACHURL%/es2_280108.pdf][esercizio 2]]
   * [[%ATTACHURL%/esonero14nov07.pdf][Prova intermedia del 14 novembre 2007]]

<!-- <b>Esami di Algoritmi I, Anni Accademici [[Algoritmi1/Inf.VecchiScritti][precedenti al 2007-2008]]</b> -->

<br />