---++ *Diario delle Lezioni (Angelo Monti) a.a. 2023/2024* *NOTA:* le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il link al pdf delle slides utilizzate. ---+++ Settimana 1 - 26 Febbraio *26 Febbraio 2024 (Lunedì):* Presentazione del corso. Introduzione all'asintotica delle funzioni significato dell'insieme O [[%ATTACHURL%/lez01Introduzione24.pdf][lez01Introduzione24.pdf]]<a href="https://twiki.di.uniroma1.it/pub/Intro_algo/PZ/DiarioA/lez01Introduzione23.pdf" target="_top"><br /></a> <b>29 Febbraio 2024 (Giovedì): </b>asintotica delle funzioni, definizione, significato ed esercizi per gli insiemi Ω e Θ. [[%ATTACHURL%/lez02Asintotica24.pdf][lez02Asintotica24.pdf]] ---+++ Settimana 02 - 4 Marzo <b>4 Marzo 2024 (Lunedì):</b>-lezione sul calcolo della complessità asintotica di un algoritmo [[%ATTACHURL%/lez03CostoAlgoritmi.pdf][lez03CostoAlgoritmi.pdf]] ESERCIZI su sommatorie e altro [[%ATTACHURL%/Esempi_ed_eserciziAsintotica24.pdf][Esempi_ed_eserciziAsintotica24.pdf]] <b>7 Marzo 2024 (Giovedì): </b>esercizi sul calcolo della complessità di semplici programmi iterativi [[%ATTACHURL%/ESERCIZICostoAlgoritmi.pdf][ESERCIZICostoAlgoritmi.pdf]] Il problema della ricerca. Algoritmo sequenziale e sua complessità nel caso pessimo, ottimo e medio. L'algoritmo di ricerca binaria per la ricerca in vettori ordinati e sua complessità nel caso pessimo, ottimo e medio. [[%ATTACHURL%/lez04ProblemaRicerca.pdf][lez04ProblemaRicerca.pdf]] ---+++ Settimana 03 - 11 Marzo *11 Marzo 2024 (Lunedì):* Esempi di algoritmi ricorsivi: ricerca sequenziale, ricerca binaria, calcolo delle palindromi, calcolo dei numeri di fibonacci. Impostazione dell'equazione di ricorrenza per il calcolo della complessita' degli algoritmi ricorsivi. [[%ATTACHURL%/lez05AlgoritmiRicorsivi.pdf][lez05AlgoritmiRicorsivi.pdf]] *14 Marzo 2024 (Giovedì):* Risolvere equazioni di ricorrenza tramite il metodo iterativo e\o il metodo dell'albero. Esempi svolti in aula: T(n)=T(n-1) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(n) T(n)=T(n-1) +Θ(n) , T(1)=Θ(1). Soluzione: Θ(n^2) T(n)=T(n-1) +Θ(log n) , T(1)=Θ(1). Soluzione: Θ(n log n) T(n)=T(n/2) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(log n) T(n)=2T(n/2) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(n) T(n)=T(n/2) +Θ(n) , T(1)=Θ(1). Soluzione: Θ(n) [[%ATTACHURL%/lez06EquazioniRicorrenza24.pdf][lez06EquazioniRicorrenza24.pdf]] [[%ATTACHURL%/lez06EquazioniRicorrenza24.pdf][<br />]] ---+++ Settimana 04 - 18 Marzo * *18 Marzo 2024 (Lunedì)*:* -Risolvere equazioni di ricorrenza tramite il teorema principale e\o il metodo di sostituzione. *21 Marzo 2024 (Giovedì):* -Esercizi svolti in classe con tutti e 4 i metodi: T(n)=T(n^{1/2}) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(loglog n) T(n)=2T(n/4) +Θ(n^{1/2}) , T(1)=Θ(1). Soluzione: Θ(n^{1/2}log n) T(n)=2T(n/2) +Θ(n^3) , T(1)=Θ(1). Soluzione: Θ(n^3) [[%ATTACHURL%/07_EserciziEqRicorrenza2024.pdf][07_EserciziEqRicorrenza2024.pdf]] [[%ATTACHURL%/lez07EserciziEquaRic.pdf][<br />]] ---+++ Settimana 05 - 25 Marzo * *25 Marzo 2024 (Lunedì)*:*algoritmi elementari di ordinamento a complessità Θ(n^2) al caso pessimo: insertion sort, seleciton sort e bubble sort. Loro implementazione in python. Gli alberi di decisione e la prova Gli algoritmi di ordinamento basati sul confronto richiedono Ω(nlog n) confronti. [[%ATTACHURL%/lez08Ordinamento1Naive.pdf][lez08Ordinamento1Naive.pdf]] esercizi sulle ricorrenze [[%ATTACHURL%/eserciziEquazioniDiRicorrenza.pdf][eserciziEquazioniDiRicorrenza.pdf]] <b>28 Marzo 2024 (Giovedì): </b>VACANZE DI PASQUA ---+++ Settimana 06 - 1 Aprile Settimana 06 - 1 Aprile *1 Aprile 2024 (Lunedì):* VACANZE DI PASQUA *4 Marzo 2024 (Giovedì): prima prova per la verifica delle conoscenze. [[%ATTACHURL%/PrimoEsonero24_conSol.pdf][PrimoEsonero24_conSol.pdf]]* per non tenervi sulle spine ecco i risultati (chi non ha superato ha il simbolo "-") [[%ATTACHURL%/risultatiIntroduzione1.pdf][risultatiIntroduzione1.pdf]] [[%ATTACHURL%/risultatiIntro.pdf][<br />]] ---+++ Settimana 07 - 8 Aprile *8 Aprile 2024 (Lunedì):*La tenica algoritmica del divide et impera. L' Algoritmo di ordinamento Θ(nlog n) mergesort e la sua funzione "fondi" di tempo Θ(n). Implementazione iterativa del mergesort. [[%ATTACHURL%/lez09Ordinamento2Merge.pdf][lez09Ordinamento2Merge.pdf]] L'algoritmo di quicksort, implementazione con spazio di lavoro O(n^2) . Analisi al caso pessimo Θ(n^2). Analisi al caso ottimo Θ(n log n). Quicksort randomizzato.- [[%ATTACHURL%/lez10Ordinamento3Quik.pdf][lez10Ordinamento3Quik.pdf]] <b>11 Aprile 2024 (Giovedì): </b>La funzione partition del quicksort.Alberi completi e quasi completi. Definizione di heap (minimo) e sua rappresentazione tramite aray. La libreria heapq di python. Le funzioni heapify(), heappush(), heappop() per costruire un heap di n elementi, aggiungere un elemento ad un heap di n elementi ed estrarre il minimo dall'heap di n elementi in tempo O(n), O(log n), O(log n) , rispettivamente. Algoritmo di ordinamento <a href="https://twiki.di.uniroma1.it/twiki/edit/Intro_algo/PZ/HeapSort?topicparent=Intro_algo/PZ.DiarioA;nowysiwyg=0" title="HeapSort (this topic does not yet exist; you can create it)">HeapSort</a> con spazio di lavoro O(n). Implementazione della funzione di heappop() in O(log n). [[%ATTACHURL%/lez11HeapSort1.pdf][lez11HeapSort1.pdf]] ---+++ Settimana 08 - 15 Aprile *15 Aprile 2024 (Lunedì):* * implementazione della funzione di heappush in tempo O(log n) e implementazione della funzione heapify in tempo Θ(n) (vedi le slide di lez11) * l'algoritmo di ordinamento Counting-Sort per ordinare interi nell'intervallo [0...M] e sua implementazione in O(M+n). * Soluzione dell'esercizio 2 assegnato nell'appello di marzo 2023 [[%ATTACHURL%/lez12OrdinamentiLineari.pdf][lez12OrdinamentiLineari.pdf]] [[%ATTACHURL%/lez12OrdinamentiLineari.pdf][<br />]] <b>18 Aprile 2024 (Giovedì): </b>strutture dati statiche e strutture dati dinamiche: vantaggi e svantaggi. Gli array e le liste a puntatori. Le liste di python. Creazione di una lista a puntatori da una lista e stampa di una lista a puntatori in tempo in tempo Θ(n). Inserimento e cancellazione da una lista a puntatori. [[%ATTACHURL%/lez13struttureDati1.pdf][lez13struttureDati1.pdf]] ---+++ Settimana 19 - 22 Aprile * <b>22 Aprile 2024 (Lunedì):</b> L'algoritmo Bucket-Sort per ordinare n elementi (non necessariamente interi) nell'intervallo [0...m], sua implementazione che produce tempo di esecuzione Θ(n) quando i buckets sono una frazione costante di n e gli interi da ordinare sono equamente distribuiti nell'intervallo [0...m] (vedi appunti lez12). Pile e code su array e su liste concatenate. Implementazione tramite array e tramite liste concatenate in modo da avere tempi d'esecuzione Θ(1) sia per l'inserimento che per la cancellazione. [[%ATTACHURL%/lez14StruttureDati2.pdf][lez14StruttureDati2.pdf]] *25 Aprile 2024 (Giovedì): festa della liberazione* ---+++ Settimana 10 - 29 Aprile *29 Aprile 2024 (Lunedì):* <strong>2 Maggio 2024 (Giovedì): <br /></strong> ---+++ Settimana 11 - 6 Maggio *6 Maggio 2024 (Lunedì):* *9 Maggio 2024 (Giovedì):* ---+++ Settimana 12 - 13 Maggio *13 Maggio 2023 (Lunedì):* *16 Maggio 2023 (Giovedì):* <strong><br /></strong> ---+++ Settimana 13 - 20 Maggio <b>*20 Maggio 2024 (Lunedì):*</b> *23 Maggio 2024 (Giovedì):* ---+++ Settimana 14 - 27 Maggio *27 Maggio 2024 (Lunedì):* *30 Maggio 2024 (Giovedì):* ---+++
Attachments
Attachments
Topic attachments
I
Attachment
History
Action
Size
Date
Who
Comment
pdf
07_EserciziEqRicorrenza2024.pdf
r2
r1
manage
1822.1 K
2024-03-21 - 14:06
AngeloMonti
key
ESERCIZICostoAlgoritmi.key
r1
manage
1913.3 K
2024-03-07 - 12:43
AngeloMonti
pdf
ESERCIZICostoAlgoritmi.pdf
r1
manage
423.6 K
2024-03-07 - 12:44
AngeloMonti
pdf
ESERCIZIOlistaPDF.pdf
r1
manage
89.0 K
2021-04-19 - 13:22
AngeloMonti
pdf
Esempi_ed_eserciziAsintotica.pdf
r3
r2
r1
manage
169.5 K
2023-03-02 - 13:22
AngeloMonti
pdf
Esempi_ed_eserciziAsintotica24.pdf
r1
manage
188.0 K
2024-03-04 - 13:29
AngeloMonti
pdf
EserciziListeLinkate.pdf
r1
manage
472.1 K
2022-05-02 - 13:01
AngeloMonti
pdf
EserciziListeLinkatePDF.pdf
r1
manage
551.7 K
2021-04-22 - 12:11
AngeloMonti
pdf
Lez21Esercizi.pdf
r1
manage
696.0 K
2022-05-23 - 08:11
AngeloMonti
pdf
Lez21EserciziVari1PDF.pdf
r1
manage
483.6 K
2021-05-13 - 12:51
AngeloMonti
pdf
Lez21tracce.pdf
r1
manage
354.6 K
2022-05-23 - 05:00
AngeloMonti
pdf
Lez22Esercizi.pdf
r1
manage
640.6 K
2022-05-26 - 12:34
AngeloMonti
pdf
Lez22EserciziPDF.pdf
r1
manage
523.5 K
2021-05-18 - 16:00
AngeloMonti
pdf
Lez22tracce.pdf
r1
manage
559.9 K
2022-05-23 - 08:16
AngeloMonti
pdf
Lez23EserciziPDF.pdf
r1
manage
914.1 K
2021-05-24 - 17:37
AngeloMonti
pdf
Lez23TRACCEserciziPDF.pdf
r1
manage
687.3 K
2021-05-18 - 16:07
AngeloMonti
pdf
PrimoEsonero24_conSol.pdf
r1
manage
148.3 K
2024-04-04 - 10:08
AngeloMonti
pdf
eserciziEquazioniDiRicorrenza.pdf
r1
manage
133.2 K
2024-03-25 - 22:44
AngeloMonti
pdf
esercizioMatrice.pdf
r1
manage
104.1 K
2021-04-15 - 16:39
AngeloMonti
pdf
lez01Introduzione22.pdf
r1
manage
390.7 K
2022-02-19 - 09:58
AngeloMonti
pdf
lez01Introduzione23.pdf
r1
manage
390.6 K
2023-02-20 - 13:08
AngeloMonti
pdf
lez01Introduzione24.pdf
r1
manage
1068.4 K
2024-02-26 - 13:53
AngeloMonti
pdf
lez01IntroduzionePDF.pdf
r1
manage
841.9 K
2021-02-22 - 13:53
AngeloMonti
pdf
lez02Asintotica22.pdf
r2
r1
manage
942.2 K
2022-02-21 - 14:21
AngeloMonti
pdf
lez02Asintotica23.pdf
r1
manage
946.2 K
2023-02-23 - 15:42
AngeloMonti
pdf
lez02Asintotica24.pdf
r1
manage
1199.1 K
2024-02-29 - 12:16
AngeloMonti
pdf
lez02AsintoticaPDF.pdf
r1
manage
848.6 K
2021-02-25 - 18:27
AngeloMonti
pdf
lez03CostoAlgoritmi.pdf
r3
r2
r1
manage
596.4 K
2024-03-04 - 13:26
AngeloMonti
pdf
lez03CostoAlgoritmi22.pdf
r1
manage
587.4 K
2022-02-27 - 09:57
AngeloMonti
pdf
lez03CostoAlgoritmiEsercizi.pdf
r2
r1
manage
422.2 K
2022-03-07 - 10:58
AngeloMonti
pdf
lez03CostoAlgoritmiPDF.pdf
r1
manage
820.8 K
2021-03-01 - 13:22
AngeloMonti
pdf
lez04ProblemaRicerca.pdf
r3
r2
r1
manage
754.3 K
2024-03-07 - 12:46
AngeloMonti
pdf
lez04ProblemaRicercaPDF.pdf
r1
manage
525.4 K
2021-03-04 - 14:01
AngeloMonti
pdf
lez04ProblemaRicercab.pdf
r1
manage
463.3 K
2022-03-13 - 14:11
AngeloMonti
pdf
lez05AlgoritmiRicorsivi.pdf
r4
r3
r2
r1
manage
1905.5 K
2024-03-11 - 13:20
AngeloMonti
ps
lez05AlgoritmiRicorsivi.ps
r1
manage
5550.6 K
2023-03-05 - 10:17
AngeloMonti
pdf
lez05AlgoritmiRicorsiviPDF.pdf
r1
manage
1217.9 K
2021-03-08 - 13:43
AngeloMonti
pdf
lez06EquazioniRicorrenza.pdf
r3
r2
r1
manage
572.1 K
2023-03-13 - 14:22
AngeloMonti
pdf
lez06EquazioniRicorrenza24.pdf
r3
r2
r1
manage
632.1 K
2024-03-17 - 10:51
AngeloMonti
pdf
lez06EquazioniRicorrenzaPDF.pdf
r1
manage
599.2 K
2021-03-11 - 14:39
AngeloMonti
pdf
lez07EserciziEquaRic.pdf
r1
manage
555.7 K
2022-03-25 - 17:07
AngeloMonti
pdf
lez08Ordinamento1Naive.pdf
r4
r3
r2
r1
manage
519.8 K
2024-03-25 - 22:40
AngeloMonti
pdf
lez08Ordinamento1NivePDF.pdf
r1
manage
1524.1 K
2021-03-18 - 12:08
AngeloMonti
pdf
lez09Merge.pdf
r1
manage
433.0 K
2022-04-04 - 08:10
AngeloMonti
pdf
lez09Ordinamento2Merge.pdf
r2
r1
manage
690.2 K
2024-04-08 - 13:36
AngeloMonti
pdf
lez09Ordinamento2MergePDF.pdf
r1
manage
516.7 K
2021-03-25 - 13:20
AngeloMonti
pdf
lez10Ordinamento3Quik.pdf
r2
r1
manage
607.1 K
2024-04-08 - 13:38
AngeloMonti
pdf
lez10Ordinamento3QuikPDF.pdf
r1
manage
630.6 K
2021-03-29 - 16:59
AngeloMonti
pdf
lez10Quick.pdf
r2
r1
manage
522.1 K
2022-04-07 - 12:23
AngeloMonti
pdf
lez11.pdf
r2
r1
manage
585.8 K
2022-04-21 - 05:53
AngeloMonti
pdf
lez11HeapSort1.pdf
r2
r1
manage
938.9 K
2024-04-11 - 14:19
AngeloMonti
pdf
lez11Ordinamento4HeapPDF.pdf
r1
manage
569.4 K
2021-04-08 - 11:17
AngeloMonti
pdf
lez12OrdinamentiLineari.pdf
r4
r3
r2
r1
manage
747.8 K
2024-04-22 - 09:18
AngeloMonti
pdf
lez12Ordinamento5LineariPDF.pdf
r1
manage
660.3 K
2021-04-12 - 13:15
AngeloMonti
pdf
lez13.pdf
r1
manage
685.6 K
2022-05-19 - 19:30
AngeloMonti
pdf
lez13struttureDati1.pdf
r2
r1
manage
1011.0 K
2024-04-18 - 11:17
AngeloMonti
pdf
lez13struttureDati1PDF.pdf
r1
manage
656.8 K
2021-04-15 - 16:39
AngeloMonti
pdf
lez14.pdf
r1
manage
654.7 K
2022-04-30 - 09:35
AngeloMonti
pdf
lez14StruttureDati2.pdf
r2
r1
manage
825.4 K
2024-04-22 - 12:38
AngeloMonti
pdf
lez14StruttureDati2PDF.pdf
r1
manage
644.7 K
2021-04-19 - 13:22
AngeloMonti
pdf
lez16Alberi1.pdf
r1
manage
598.3 K
2023-04-17 - 13:57
AngeloMonti
pdf
lez16Alberi1aPDF.pdf
r1
manage
577.8 K
2021-04-26 - 11:44
AngeloMonti
pdf
lez16Alberi1bPDF.pdf
r1
manage
456.1 K
2021-04-29 - 13:04
AngeloMonti
pdf
lez16a.pdf
r1
manage
534.2 K
2022-05-04 - 08:15
AngeloMonti
pdf
lez16b.pdf
r1
manage
439.8 K
2022-05-04 - 08:15
AngeloMonti
pdf
lez17.pdf
r1
manage
456.5 K
2022-05-06 - 12:56
AngeloMonti
pdf
lez17VisiteAlberi.pdf
r1
manage
458.5 K
2023-05-05 - 09:35
AngeloMonti
pdf
lez17VisiteAlberiPDF.pdf
r1
manage
620.4 K
2021-04-29 - 13:04
AngeloMonti
pdf
lez18ABR.pdf
r3
r2
r1
manage
819.2 K
2023-05-08 - 17:01
AngeloMonti
pdf
lez18Dizionari1.pdf
r1
manage
861.7 K
2021-05-03 - 17:55
AngeloMonti
pdf
lez19ABR_RB.pdf
r1
manage
982.2 K
2022-05-15 - 07:14
AngeloMonti
pdf
lez19Dizionari2ABRPDF.pdf
r1
manage
743.2 K
2021-05-12 - 07:56
AngeloMonti
pdf
lez20Dizionari1.pdf
r2
r1
manage
868.9 K
2023-05-05 - 09:34
AngeloMonti
pdf
lez20Dizionari3bPDF.pdf
r1
manage
1143.1 K
2021-05-12 - 07:56
AngeloMonti
pdf
risultatiIntro.pdf
r1
manage
55.6 K
2024-04-05 - 06:46
AngeloMonti
pdf
risultatiIntroduzione1.pdf
r1
manage
51.7 K
2024-04-11 - 14:12
AngeloMonti
pdf
solEqRic1PDF.pdf
r1
manage
386.1 K
2021-03-18 - 12:01
AngeloMonti
pdf
solEqRic4PDF.pdf
r1
manage
417.1 K
2021-03-22 - 12:28
AngeloMonti
pdf
solEqRic5PDF.pdf
r1
manage
421.5 K
2021-03-22 - 12:28
AngeloMonti
pdf
solEqRic6PDF.pdf
r1
manage
404.8 K
2021-03-22 - 12:28
AngeloMonti
pdf
solEsercizi1PDF.pdf
r1
manage
425.4 K
2021-03-11 - 14:39
AngeloMonti
This topic: Intro_algo/PZ
>
WebHome
>
DiarioA
Topic revision: r129 - 2024-04-22 - AngeloMonti
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback