Algoritmi e strutture dati

Docenti: Andrea Clementi, Luciano Guala'

Comunicazioni

ASD: PROPEDEUTICITA'

28-09-2020 20:29

Viste le numerose richieste di chiarimento, si ribadisce che le propedeuticità concernenti l'esame ASD I e II modulo devono essere soddisfatte senza alcuna eccezione: non si puo' sostenere l'esame se non si sono verbalizzati gli esami relativi ai corsi che sono stati definiti propedeutici al corso ASD. In particolare, è necessario aver verbalizzato con esito positivo i seguenti esami del I anno:

Analisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.


ModalitÓ d'esame per la sessione estiva

29-05-2020 17:39

Modalità d'esame per il corso di Algoritmi e Strutture Dati (ASD) per la sessione estiva

 

Gli appelli di giugno e luglio di ASD non sono esclusivi, anche se è consigliato non presentarsi due volte per lo stesso modulo. Lo studente, ad ogni appello, può decidere di svolgere uno solo dei due moduli o entrambi. Deve comunque prenotarsi su Delphi (all'unica prenotazione relativa all'appello che vuole sostenere).

 

La modalità di svolgimento del singolo modulo è la seguente. 

Ci sarà uno scritto a risposte multiple (erogato in modalità telematica) più una prova orale (in modalità remota). Lo scritto non dà voto ma è propedeutico alla prova orale, ovvero, lo studente che alla prova scritta prenderà un punteggio sopra una certa soglia stabilita sarà ammesso all'orale che costituirà la prova d'esame vera e propria. 

 

I risultati dello scritto (di tutti e due i moduli) verranno resi noti subito dopo le prove. Le prove orali cominceranno lo stesso giorno dello scritto e, qualora il numero di studenti sia elevato, nei giorni immediatamente successivi. Scritto e orale di uno stesso modulo devono essere superati nello stesso appello (non si può fare lo scritto in un appello e l'orale in un altro). Se non si supera l'orale bisogna rifare lo scritto.

 

Il giorno lunedì 8 giugno alle ore 9,30 ci sarà una lezione su Teams, nel canale del corso, in cui si discuteranno eventuali dubbi relativi alle modalità d'esame e si prevede un test di prova per prendere confidenza con gli strumenti Teams e Forms. Tutti gli studenti interessati a sostenere l'esame di ASD in questa sessione sono invitati caldamente a partecipare. 


MEETING/LEZIONE ASD POSTICIPO

26-04-2020 09:30

Il Meeting/Lezione di Lunedi 27/04/20 e' posticipato a Martedi 28/04/2020 allo stesso orario.

 

 


MEETING/LEZIONE DEL 14-04- SU TEAMS

14-04-2020 09:18

Si ricorda a tutti gli interessati che oggi alle 9.30 ci sara' il consueto meeting/lezione sulla piattaforma Teams


asd: III Meeting su Teams

30-03-2020 09:05

Lunedi 30 marzo  alle 9.30 vi sara' IL III  meeting sulla piattaforma Teams del corso ASD


ASD: II MEETING/LEZIONE su TEAMS

19-03-2020 16:14

Lunedi prossimo 23 marzo  alle 9.30 vi sara' un nuovo meeting sulla piattaforma Teams del corso ASD


ASD: ORGANIZZAZIONE MATERIALE DIDATTICO

16-03-2020 12:43

Visti i problemi di sincronizzazione mostrati da Teams, in questo link pubblicheremo le slides (solo audio) delle lezioni svolte. I file audio, compatibilmente con i suddetti problemi, verranno invece di volta in volta pubblicati su Teams.


LEZIONI ASD: PIATTAFORMA TEAMS

11-03-2020 12:07

Si informano gli studenti che sulla piattaforma Teams, è disponibile una versione di prova di una prima lezione multimediale svolta mediante  PowerPoint con commento audio del docente.

 

https://uniroma2.sharepoint.com/sites/msteams_c8acd9/Materiale%20del%20corso/MST-PROVA.ppsm

 

OR 

 

https://uniroma2-my.sharepoint.com/:p:/g/personal/andrea_clementi_uniroma2_eu/EbQG98JrFepBgrzqbh8UNkoBV-UDWZWRgB5SkA2JC_ztfw?e=WMX0MW

 

Nei prossimi giorni verranno preparate altre lezioni con questo metodo. Si ricorda tuttavia che   questi strumenti sono solo una parte integrante dello studio che deve essere svolto sul libro di testo.

 

Entro pochi giorni, verranno programmati,  sempre mediante Teams, dei meeting settimanali in cui gli studenti accreditati (si leggano gli avvisi ufficiali su come iscriversi ai singoli insegnamenti di interesse) potranno porre domande sulle lezioni svolte.

 

 


ASD: ALCUNI SUGGERIMENTI PER QUESTA LUNGA SOSPENSIONE

05-03-2020 10:07

 

 

 

ALLO SCOPO DI NON INTERROMPERE  TOTALMENTE LO STUDIO, GLI STUDENTI SONO INVITATI A SEGUIRE QUESTI CONSIGLI. VA CHIARITO CHE QUESTA E’ SOLO UNA PROPOSTA INFORMALE, NON OBBLIGATORIA, ATTA A CERCARE DI AIUTARE GLI STUDENTI INTERESSATI A NON PERDERE DEL TEMPO PREZIOSO.

 

 

I) il passo più importante,  fondamentale,  e’ quello di studiare sul libro adottato:

 

"algorithm design" Kleinberg-Tardos = kt

 

Gli argomenti della prima lezione svolta e delle due successive  lezioni che si faranno, svolgendo gli esercizi suggeriti nel libro. In particolare:

 

1.     LEZIONE I (SHORTEST PATHS) (si vedano le slides ma soprattutto cap. 4.4. del libro KT). Esercizio: Dimostrare per induzione sul numero K di nodi inseriti in S, che il K-mo nodo inserito in S corrisponde anche al K-mo nodo più vicino alla sorgente s. Esercizio 2: scrivere il programma in Python (o in C) dell'algoritmo realizzando per i nodi in V-S una struttura HEAP (coda di priorità).

2.     LEZIONE 2 (MINIMUM SPANNING TREE - MST - I). A partire dalle slides (secondo file), si studi il cap. 4.5 del KT sino al Theorema 4.19 a pag 147 e si eseguano gli algoritmi di Prim e Kruskal su vari esempi di grafi pesati di dimensione almeno 10. Svolgere gli esercizio 1 e 2 a pag. 188-9.

3.     LEZIONE 3 (MINIMUM SPANNING TREE - MST - II).  A partire dale slides (secondo file), si studi il cap. 4.5 da pag 147 a pag 151. In particolare, si dimostri la correttezza del Reverse-Delete Algorithm basandosi sulla Cycle Property (si studi la dimostrazione di questa proprietà: Teorema 4.20).     Esercizio I: si dimostri rigorosamente, per assurdo (mediante la tecnica exchanging argument),  la correttezza degli algoritmi studiati  per il MST anche nel caso di pesi NON distinti (si veda pag 149). Esercizio II: studiare l’esercizio svolto n. 3 del KT a pag. 187.

 

II) Come possibile modalità d’interazione, nei prossimi giorni, siete fortemente invitati, ove possibile,  a stabilire dei piccoli gruppi di 4-5 studenti per studiare insieme (possibilmente mediante video-conference – SKYPE, JITSI, etc etc) le tre lezioni suddette e per svolgere gli esercizi.

Gli argomenti proposti nelle tre suddette lezioni verranno rivisti in classe appena possibile ma sarà fondamentale la vostra collaborazione, nel vostro interesse, per svolgere    un programma sufficiente per questo insegnamento.

Nel caso di dubbi, dopo essersi confrontati a fondo con il proprio gruppo (ed anche eventualmente con altri gruppi), potete inviare una email a:

clementi@mat.uniroma2.it

La mail deve avere il subject: ASD: LEZIONE X , con X= 1,2,3.

-       La mail deve descrivere in modo chiaro e sintetico (MAX 300 parole) il dubbio riferendosi esclusivamente agli argomenti della lezione X (e dei relativi esercizi proposti).

-       La mail va firmata con cognome, matricola ed email  di ogni studente del gruppo.

-       La mail deve contenere in cc tutti e soli gli indirizzi email del gruppo.

-       Per ovvii motivi di possibile congestionamento, ogni gruppo potrà formulare al più una mail per ogni lezione.

-       Nel caso di qualsiasi deviazione significativa rispetto ai punti di cui sopra, la mail verrà totalmente ignorata.

 

 


SOSPENSIONI LEZIONI

05-03-2020 09:10

IN ACCORDO CON LE DIRETTIVE MINISTERIALI E DEL RETTORE, SI COMUNICA CHE LE LEZIONI DEL CORSO ASD SONO ATTUALMENTE SOSPESE SINO AL 15-03-2020. SALVO ULTERIORI COMUNICAZIONI, IL CORSO RIPRENDERA' LUNEDI 16-03-2020 NEGLI ORARI STANDARD DEL CORSO.


ASD: LEZIONE DEL 5/3/20

03-03-2020 11:19

Per poter operare lo spostamento delle lezioni in un'aula adeguata,  la lezione in oggetto non avra' luogo. Le lezioni riprenderanno lunedi 9 e si svolgeranno normalmente il lunedi ed il martedi in aula 4 PP2.


ASD: INIZIO II MODULO

02-03-2020 08:45

Il corso avrà inizio lunedi 2 marzo alle 9.15 presso l'aula 4 PP2.

 

Le successive  lezioni seguiranno secondo  l'orario standard con orario d'inizio sempre alle 9.15, salvo comunicazioni. 


risultati VI appello corso a.a.2018/19

24-02-2020 18:03

Si comunica che sono usciti i risultati della prova scritta del 24/02/20 relativa al VI appello del corso dell'a.a. 2018/19. Gli orali si svolgeranno mercoledì 26 alle ore 14,30 nell'ufficio del prof. Clementi. 
I risultati possono essere consultati a questa pagina:
http://www.mat.uniroma2.it/~guala/ASDL_2018.htm 


Spostamento aula lezione giovedý 14 novembre.

07-11-2019 12:07

La lezione di giovedì 14 novembre si volgerà in aula 18. 


Cambio aula.

10-10-2019 14:39

Si comunica che le lezioni di ASD si svolgeranno il lunedì in aula 3 PP2 e il giovedì in aula 2 PP2.  


Lezioni

4111-05-2020

Ripasso delle definizioni formali per problemi di OTTIMIZZAZIONE

Versione decisionale di un problema di ottimizzazione

relazioni di complessità

problemi di ottimizzazione NP-Hard

Concetto di Approssimazione per un problema di ottimizzazione

Un primo esempio di algoritmo approssimante: Il problema Min-VC e l'algoritmo 2-approssimante

analisi della approssimazione

4004-05-2020

LA CLASSE NP: ripasso delle definizioni principali

Le tecniche di riduzioni polinomiali mediante gadget.

 

Directed Hamiltonian Cycle < Hamiltonian Cycle

 

3-SAT < Directed Hamiltonian Cycle

 

Hamiltonian Cycle < Hamiltonian Path

 

Hamiltonian Path < Longest Paths 

 

Hamiltonian Cycle < Traveling Salesman Problem

3927-04-2020

LA CLASSE NP: ripasso delle definizioni principali

Le tecniche di riduzioni polinomiali.

La tecnica dei gadget

3-SAT < Independent Set

- Ripasso sulle tecniche di riduzione

- Proprietà di Transitività delle riduzioni

- Self-Reducibility

3827-04-2020

LA CLASSE NP: ripasso delle definizioni principali

Le tecniche di riduzioni polinomiali.

Riduzioni semplici:

Independent Set < Vertex Cover (equivalenza tra i problemi)

Vertex Cover < Set Cover

 

3723-04-2020

LA CLASSE NP: ripasso delle definizioni principali

L'asimmetria di NP: la classe Co-NP

problemi in NP ∩ Co-NP

Primalita' e Fattorizzazione

il Thm di Pratt e la dimostrazione per PRIME in NP ∩ Co-NP

 

3620-04-2020

LA CLASSE NP,

esempi, riducibilita' polinomiali

NP-completezza

il primo problema NP completo: 3 SAT

P vs NP

3517-04-2020

LA CLASSE NP

IL CONCETTO DI CERTIFICATIONS E CERTIFIERS

DEFINIZIONE DI NP

ESEMPI DI PROBLEMI IN NP E DIMOSTRAZIONE DI APPARTENENZA

RELAZIONE TRA P NP et EXP

CONSIDERAZIONI GENERALI TRA ALGORTIMI E VERIFICATORI

3413-04-2020

LA PROGRAMMAZIONE DINAMICA

IL PROBLEMA SEQUENCE ALIGNMENT

MODELLAZIONE E MOTIVAZIONI

CONCETTO DI DISTANZA: GAP E MISMATCH PENALTIES

UNA PARTIZIONE DELLA STRUTTURA OTTIMA CON DUE PARAMETRI

DIMOSTRAZIONE DI OTTIMALITA'

IMPLEMENTAZIONE DELL'ALGORITMO

ANALISI DELLA COMPLESSITA'

 

3307-04-2020

LA PROGRAMMAZIONE DINAMICA

IL PROBLEMA KNAPSACK

UN APPROCCIO CON UN SOLO PARAMETRI NON VALIDO

UNA PARTIZIONE DELLA STRUTTURA OTTIMA CON DUE PARAMETRI

DIMOSTRAZIONE DI OTTIMALITA'

IMPLEMENTAZIONE DELL'ALGORITMO

ANALISI DELLA COMPLESSITA'

PSEUDOPOLINOMIALITA'

3207-04-2020

PROGRAMMAZIONE DINAMICA

 

IL PROBLEMA DEL SEGMENTED LEAST SQUARES (SLS)

 

STRUTTURA DELL'OTTIMO E SUA PARTIZIONE IN SOTTO-ISTANZE

 

UN ALGORITMO DI PROGR. DINAMICA

 

ANALISI DELL'OTTIMALITA' E DELLA COMPLESSITA'

 

IMPLEMENTAZIONE ITERATIVA

3106-04-2020

INTRODUZIONE ALLA PROGRAMMAZIONE DINAMICA

 

IL PROBLEMA DEL WEIGHTED INTERVAL SCHEDULING (WIS)

 

UN ALGORITMO DI PROGR DIN ALG PER WIS

 

OTTIMALITA' DI ALG

 

ANALISI DELLA VERSIONE RICORSIVA NON EFFICIENTE

 

VERSIONE ITERATIVA

 

MEMOIZATION

3031-03-2020

Il problema del Data Compression (DC)

 

Altre Proprieta' strutturali di soluzioni ottime

 

Un approccio ricorsivo Bottom-Up: Algoritmo greedy di Huffman H

Pseudo-codice di H

Ottimalità di H

Complessità di H

Esempi di esecuzioni di H su istanze concrete

2930-03-2020

Il problema del Data Compression (DC)

Introduzione

Codici a lungh fissa e codici prefissi a lungh variabile

Esempi di compressione

Definizione del concetto di compressione: ABL di una distribuzione di frequenze di simboli in un testo

Definizione del problema di minimizzazione min-ABL

Equivalenza codici prefissi = Labeled Tree

Proprieta' strutturali di soluzioni ottime: full trees

Un approccio top-down: Algoritmo Shannon-Fano S-F

Non ottimalita' di SF

 

2824-03-2020

LEZIONE 6

I problemi di scheduling 

Il problema Interval PARTITIONING (IP)

I vari approcci greedy x IP

 Un approccio ottimale greedy: starting time e

"open class when you need"

Dimostrazione dell'ottimalità

Il concetto di DEPTH di una Istanza

Lower Bound sull'Ottimo

Dimostrazione analitica del fatto che il greedy raggiunge il 

Lower Bound

Esempi 

2723-03-2020

 Lezione 5

 

I problemi di scheduling: Intorduzione e definizione

Il problema Interval Scheduling (IS)

I vari approcci greedy x IS

Schema generale di greedy algorithms

Un approccio ottimale greedy: finish time

Dimostrazione dell'ottimalità

Tecnica Greedy Stays Ahead

Tecnica Exchange Argument

Esempi e Domande Studenti

 

2616-03-2020

LEZIONE 3 et 4. (Libro Demetrescu et Al del  I Modulo).

 

- Strutture Dati per UNION and FIND

- Motivazioni e Definizione formale

- Soluzioni basate su Foreste

- Soluzione Quick Find 

- Descrizione ed Esempi

- Realizzazione

- Analisi dei Costi (Caso Peggiore)

- Soluzione Union By Size 

- Descrizione ed Esempi

- Il concetto di analisi ammortizzata

- Analisi ammortizzata (Caso Peggiore su una sequenza arbitraria di operazioni)

2516-03-2020

LEZIONI ONLINE:

 

 

 

2.     LEZIONE N. 2  (Section 4.5 – tutta quanta + esercizio n.3 a p. 187)

a.     Il problema del MST: definizione formale e size dell’istanza

b.     L’approccio  greedy dei tre algoritmi

c.     Le proprietà del taglio e del ciclo con dimostrazioni

d.     Correttezza dell’algoritmo di Prim

3.     LEZIONE N. 3 (Section 4.5 – tutta quanta + esercizio n.3 a p. 187)

a.     Complessità algoritmo di Prim (esercizio)

b.     Correttezza e complessità dell’algoritmo di Kruskal (escludendo l’implementazione della struttura UNION-FIND)

c.     Rimozione dell’assunzione: pesi distinti

d.     Esercizio n. 3 pag. 187

e.     Altri semplici esercizi e la relazione con lo Shortest Path Tree

f.      Il problema del K-Clustering: definizione informale e formale

g.     Un algoritmo basato sul MST

h.     Prova dell’ottimalità dell’algoritmo basato sul MST

2402-03-2020

LEZIONE 02-03-2020

1.    Introduzione generale al II modulo . Conoscenze  necessarie per gli studenti.

2.    Linguaggio logico e matematico, pseudocodice, e nozioni fondamentali  utilizzati nelle lezioni e richiesti come obiettivi formativi essenziali del corso.

3.    Un argomento già visto nel I modulo, rivisitato sotto la luce dei suddetti obiettivi: L’algoritmo di Dijkstra per i cammini minimi.

4.    Definizione formale del problema

5.    Lo Shortest Path Tree (SPT)

6.    Il Principio di Sub-Ottimalità dei cammini minimi

7.    Lo schema dell'algoritmo di D.

8.    Correttezza dello schema

9.    Dettagli implementativi e complessità

2209-01-2020

Correzione Esercizio 1 e discussione Esercizio 2 del Problem Set 2.

2119-12-2019

Cammini minimi in grafi pesati. Il problema del calcolo dei cammini minimi a singola sorgente. Un algoritmo veloce quando il grafo ha pesi non negativi: l'algoritmo di Dijkstra.

2016-12-2019

Usi meno comuni della visita DFS. Catalogare per tipo gli archi del grafo. Individuare un ciclo in grafi diretti. Grafi diretti aciclici (DAG) e ordinamento topologico. Usare la visita DFS per trovare un ordinamento topologico di un DAG. Componenti fortemente connesse: un algoritmo lineare per calcolarle.

1912-12-2019

Strutture dati per rappresentare un grafo. Matrice di adiacenza e Liste di adiacenza. Visite di un grafo. Visita in ampiezza (BFS): cammini minimi da una sorgente. Visita in profondità (DFS): uscire da un labirinto.

1809-12-2019

I Grafi (diretti, non diretti, pesati). Nozioni preliminari. Cammini, distanze, diametro. Alberi. Grafi Euleriani. I grafi come linguaggio potente per descrivere scenari e problemi. Esempi di scenari/problematiche descrivibili come grafi/problemi su grafi (reti stradali/di trasporto, reti sociali, reti “delle dipendenze”).

1705-12-2019

Esercitazione. Progettare un algoritmo che, dato un vettore ordinato A[1:n] di n bit, trova il numero k di zero presenti in A. Algoritmo con complessità O(log n). Un miglior algoritmo con tempo O(log k) (Es. 9). Progettare un algoritmo con complessità lineare che, dato un vettore A[1:n] di n bit, trova l’indice k tale che il numero di zeri in A[1:k] è uguale al numero di uni in A[k+1:n] (Es. 10).

1602-12-2019

Il problema della Coda con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci e complessità ammortizzata.

1528-11-2019

Esercitazione: ricerca binaria e tecnica del divide et impera. Es. 7 e Es. 8.

1425-11-2019

Il problema del Dizionario: secondo episodio. Alberi AVL: definizione ed esempi. Dimostrazione della delimitazione superiore dell’altezza di un albero AVL (che usa la nozione di albero di Fibonacci). Operazioni sugli alberi AVL: search, insert, delete.

1321-11-2019

Il problema del Dizionario. Alberi binari di ricerca. Definizione. Visita in ordine simmetrico di un BST. Ricerca, inserimento, cancellazione (ricerca del massimo, del minimo, del predecessore e del successore di un nodo). Correzione Esercizio 4 del Problem Set 1.

1214-11-2019

Esercitazione sulle visite di alberi. Progettazione di un algoritmo che, preso un albero con valori e colori (rosso e nero), trova il valore del cammino rosso di tipo nodo-radice di valore massimo (Es 4). Altro esercizio: progettare un algoritmo che,  preso un albero e in intero h, restituisce il numero di nodi dell'albero di profondità almeno h (Es 5). Altro esercizio: preso un albero binario con valori, calcola il numero di nodi per cui la somma dei valori degli antenati è uguale alla somma dei valori dei discendenti (Es. 6).

1111-11-2019

Strutture dati elementari: rappresentazioni indicizzate e rappresentazioni collegate. Implementazione di un dizionario con array ordinato/non ordinato e lista ordinata/non ordinata. Rappresentazioni di alberi. Algoritmi di visita di un albero: profondità versione iterativa, profondità versione ricorsiva (preordine, postordine, ordine simmetrico), ampiezza. Algoritmo per calcolare l’altezza di un albero.

1007-11-2019

Esercitazione. Primo esercizio: dato un array di n interi compresi fra 1 e k, costruire in tempo O(n+k) un oracolo (struttura dati) che sia in grado di rispondere in tempo costante a domande del tipo "quanti interi nell'array sono compresi fra a e b?"(Esercizio e soluzioni a fine delle slide sull'IntegerSort). Secondo esercizio: dato un vettore A di n numeri, progettare un algoritmo che in tempo O(n) trova due indici i e j con i<j che massimizzano A[j]-A[i] (Es. 3).

904-11-2019

Esercitazione. Esercizio: dimostrare o confutare una relazione asintotica (Es. 1). Esercizio di progettazione di un algoritmo che, dato un vettore ordinato A di n interi distinti e un valore x, trova (se esistono) due elementi di A che sommano a x. Soluzione banale con complessità quadratica, soluzione di complessità O(n log n) e soluzione con tempo O(n) (Es. 2). 

831-10-2019

Delimitazioni superiori e inferiori di algoritmi e problemi. Un lower bound alla complessità temporale necessaria per ordinare n elementi (per una classe di algoritmi ragionevoli, quelli basati su confronti). Algoritmi veloci per ordinare interi: IntegerSort, BucketSort, RadixSort.

728-10-2019

Progettare algoritmi efficienti attraverso la progettazione di strutture dati efficienti. Un esempio: l'HeapSort - che ordina in loco n elementi in tempo O(n log n) nel caso peggiore.

624-10-2019

Il Problema dell’ordinamento. Un algoritmo semplice ma inefficiente: il Selection Sort. Un algoritmo migliore: il MergeSort. Un altro algoritmo che usa la tecnica divide et impera: il QuickSort: analisi del caso peggiore, migliore, e intuizioni sul caso medio. Discussione versione randomizzata del QuickSort e differenza fra complessità nel caso medio e tempo atteso di un algoritmo randomizzato.

521-10-2019

Ancora sulle equazioni di ricorrenza. Metodo della sostituzione. Teorema Fondamentale delle Ricorrenze (Master). Semplici esempi. Quando non si può applicare. Metodo del cambiamento di variabile.

417-10-2019

Analisi della complessità nel caso medio: un esempio. Il problema della ricerca di un elemento in un insieme: ricerca sequenziale e ricerca binaria. Equazioni di ricorrenza. Metodo dell’iterazione. Metodo che usa l’albero della ricorsione.

314-10-2019

Modello di calcolo RAM. Costi uniformi e logaritmici. Complessità caso peggiore, migliore, medio. Notazioni asintotiche: O-grande, Omega-grande, Theta. O-piccolo, Omega-piccolo. Definizioni e semplici esempi. Proprietà. Usare la notazione asintotica nelle analisi della complessità computazionale degli algoritmi. 

210-10-2019

Il problema del calcolo dell’n-esimo numero di Fibonacci. Un algoritmo numerico e un algoritmo ricorsivo. Analisi della complessità temporale dell’algoritmo ricorsivo. Un algoritmo iterativo di complessità temporale O(n) e di complessità spaziale O(n) (Fibonacci3). Portare la memoria a O(1): Fibonacci4. Introduzione informale alla notazione asintotica. Algoritmo con complessità O(log n) per il calcolo dell’n-simo numero di Fibonacci. Discussione della complessità spaziale degli algoritmi ricorsivi Fibonacci2 e Fibonacci6.

107-10-2019

Introduzione al corso. Motivazioni e concetti fondamentali. Un primo esempio: il problema di trovare una moneta falsa (più pesante) fra n monete usando una bilancia a due piatti.


Materiale didattico

LEZIONE 17 del II MOD di ASD

LEZIONE 16 del II MOD di ASD

LEZIONE 15 del II MOD di ASD

LEZIONE 14 del II MOD di ASD

LEZIONE 13 del II MOD di ASD

LEZIONE 12 del II MOD di ASD

LEZIONE 11 del II MOD di ASD

LEZIONE 10 del II MOD di ASD

LEZIONE 9 del II MOD di ASD

LEZIONE 8 del II MOD di ASD

LEZIONE 7 del II MOD di ASD

LEZIONE 6 del II MOD di ASD (seconda parte)

LEZIONE 5 del II MOD di ASD

LEZIONE 4 del II MOD DI ASD

LEZIONE 3 del II MOD di ASD

LEZIONE 2 del II MOD di ASD

LEZIONE 1 del II MOD di ASD

Informazioni

Anno accademico2019-2020
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàAnalisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.

Programma

http://www.mat.uniroma2.it/~guala/ASDL_2019.htm


Testi di riferimento

http://www.mat.uniroma2.it/~guala/ASDL_2019.htm


Ricevimento studenti

http://www.mat.uniroma2.it/~guala/ASDL_2019.htm


Modalità di esame

http://www.mat.uniroma2.it/~guala/ASDL_2019.htm