Progettazione di Algoritmi a.a. 2018-2019

Diario delle lezioni e delle esercitazioni - Canale II (Monti)

martedý 26 febbraio 2019: Presentazione del corso. Algoritmi efficienti, complessitÓ polinomiale, superpolinomiale: esponenziale, superesponenziale e subesponenziale. Differenza tra complessita' dell'algoritmo e complessita' del problema. Algoritmi ottimi. Esempi: un algoritmo superesponenziale per il problema dell'ardinamento, un algoritmo polinomiale per l'ordinamento a complessita' O(n^2) senza l'utilizzo di heap e a complessita' O(nlog n) con heap. Il test di primalita' algoritmi esponenziali in tempo O(n) e tempo O(\sqrt(n)). Algoritmo O(n^3) per il prodotto di matrici nxn. Algoritmi provatamente intrattabili: la stampa di tutte le stringhe binarie di lunghezza n. ESERCIZIO: dare lo pseudocodice di un algoritmo che preso come parametro un numero n determina sebil numero e' semiprimo o meno, l'algoritmo deve avere complessita' O(\sqrt(n)), giustificare la correttezza e la complessita'. ESERCIZIO2 .....

giovedý 28 febbraio 2019: Accenni alla soluzione dell'esercizio2 assegnto alla lezione precedente. Grafi: relazione tra numero n di nodi e numero m di archi. Grafi sparsi: Alberi e grafi planari loro definizioni. Un albero ha sempre almeno una foglia e esattamente n-1 archi (prova). Formula di eulero: n-m+f=2 (prova). Un grafo planare ha al piu' 3n-6 archi (prova). Rappresentazione di grafi tramite matrici (liste di liste in python) o lista di adiacenza (dizionari in python).

venerdý 1 marzo 2019: tesi di Church-Turing nella versione forte e nella versione debole. Il pozzo universale di un grafo diretto: un algoritmo basato sulla ricerca esaustiva a tempo O(n^2) ed un algoritmo che richiede O(n) se il grafo e' rappresentato tramite matrici. La visita DFS di un grafo in tempo O(n+m).

Un algoritmo di tempo O(n+m) che, preso un grafo ed un suo nodo u restituisce, in tempo O(n+m), l'insieme dei nodi del grafo raggiungibili a partire dal nodo u. Prova della complessita' e della correttezza dell'algoritmo.

Il problema della colorabilita' dei grafi. Il teroema dei 4 colori. La bicolorabilita' e la tricolorabilita'.

martedý 5 marzo 2019: discussione sull'algoritmo O(n+m) per la bicolorazione come esempio di applicazione della tecnica greedy.

Cenni di programmazione python: l'inserimento nella lista richiede O(1) se avviene in coda altrimenti puo' costare anche O(n). Il tipo insieme in python e implementazione tramite tabelle hash in modo che il test di appartenenza, l'inserimento e la cancellazione richiedano O(1).

procedure O(n+m) per calcolare il vettore V dei visitati, il vettore P dei padri, il vettore C delle componenti connesse.

procedura che prende come parametri un nodo y ed il vettore dei padri P e calcola il cammino da x a y in O(n).

Procedura che, presi come parametri un grafo G ed un suo nodo x, in tempo O(n+m) trova i nodi della componente fortemente connessa cui appartiene x. Mostrare che questa procedura puo' essere usata per calcolare le componenti fortemente connesse del grafo G in tempo O(n(n+m)) e che ci sono grafi per cui la procedura richiede Ω(n(n+m)).

giovedý 7 marzo 2019: ricerca di cicli dei grafi in O(n+m), algoritmo per il caso dei grafi diretti ed algoritmo per il caso dei grafi non diretti.

Partizione degli archi di un grafo diretto a seguito della fisita DFS: archi dell'albero (effettivamente attraversati), archi in avanti, archi all'indietro e archi di attraversamento. Come distinguere gli archi all'indietro (ad esempio utili ad individuare cicli) da quelli di attraversamento e in avanti.

Definizione del problema dell'ordinamento topologico. Prova che un grafo diretto ciclico non ha un ordinamento topologico.

Possibili esercizi d'esame:

1) Come distinguere archi in avanti da quelli di attraversamento e all'indietro? Progettare un algoritmo che presi come parametro un grafo diretto G e un suo nodo x in tempo O(n+m) restituisce il numero di archi in avanti incontrati nel corso della visita di G che parte da x.

2) Come distinguere archi di attraversamento da quelli in avanti e all'indietro? Progettare un algoritmo che presi come parametro un grafo diretto G e un suo nodo x in tempo O(n+m) restituisce il numero di archi di attravrsamento incontrati nel corso della visita di G che parte da x.

venerdý 8 marzo 2019:

  • Definizione di componente fortemente connessa per grafi diretti; Grafo SCC(G) delle componenti fortemente connesse; SCC(G) Ŕ un DAG.
  • Revisione della visita in profonditÓ con tempi di ingresso e completamento per i nodi; tempo di ingresso (min) e completamento (max) per un insieme di nodi.
  • Lemma Se c'Ŕ un arco tra C e C' (componenti connesse in SCC(G)) allora il tempo di completamento di C Ŕ sempre maggiore di quello di C'.
  • Algoritmo per le componenti connesse, con due visite, la seconda sul grafo trasposto.
  • Algoritmo di Tarjan (con un'unica visita e uso dell'attributo lowlink sui nodi).

  • Piccole ProprietÓ della DFS:
    • trovare un grafo e una DFS, in cui u.d<v.d e c'Ŕ un cammino tra u e v, ma v non Ŕ discendente di u nell'albero di visita;
    • discutere perchÚ nodi con archi uscenti ed entranti possono stare in un albero con un solo nodo nella foresta ottenuta dalla visita;
  • Esercizi Proposti:
    • Costruire il grafo trasposto in O(E+V) rappresentato con le liste di adiacenza.
    • in un DAG, calcolare il numero di cammini tra due nodi dati.
    • Riflettere su come implementare effettivamente i due algoritmi visti: estrarre efficientemente i nodi in ordine inverso di tempo di completamento.

martedý 12 marzo 2019:

  • un grafo diretto aciclico (DAG) con n nodi ha al pi¨ n(n-1)/2 archi.
  • un DAG ha almeno un nodo sorgente
  • algoritmo greedy basato sulle sorgenti per la ricerca di un eventuale sort topologico. Correttezza e implementazione in O(n+m).
  • algoritmo greedy per la ricerca di un sort topologico in un grafo privo di cicli basato sulla visita DFS del grafo.
  • Visita BFS di un grafo: implementazione della visita in tempo O(n+m) e dimostrazione che tutti i vertici raggiungibili dal nodo di partenza x vengono effettivamente visitati.
  • nozioni elementari di python: il modulo collections e la "deque" che permette di inserire o cancellare a sinistra della coda in tempo O(1) (con i metodi leftpop() e leftappend()). Implementazione della coda tramite lista con estrazione logica a sinistra in O(1)
giovedý 14 marzo 2019:
  • La visita BFS per ricavare il vettore dei padri e il vettore delle distanze. Prova per induzione che i cammini trovati nel corso della visita sono cammini minimi.
  • ESERCIZIO "modificare" la procedura DFS in modo che nel corso della visita venga calcolato il vettore T dei tempi di visita (T[u] contiene zero se il nodo non e' visitato , i se e' l'iesimo nodo nel corso della visita ad essere stato visitato)
  • Definizione di un ponte per un grafo connesso non diretto. Esempi di grafi senza ponti e con il numero massimo di ponti. Problema:Dato un grafo non diretto e connesso trovare l'insieme dei suoi ponti. Algoritmo di ricerca esaustiva di tempo O(m^2), algoritmo di tempo O(nm) basato sugli archi attraversati nel corso di una visita DFS o BFS. Algoritmo di tempo O(m) basato sull'esecuzione di un un'ica visita. ESERCIZIO: implementare quest'ultimo algoritmo in python.

venerdý 15 marzo 2019:

  • Problema del diametro di un albero. Definizione.
  • Lemma In un albero radicato, almeno uno dei nodi che realizzano la massima distanza Ŕ una foglia al massimo livello;
  • Algoritmo con due BFS, la seconda che comincia da una foglia al livello massimo;
  • Lemma G connesso, BFS(G,s) = DFS(G,s) se e solo se G Ŕ un albero;
  • Algoritmo con una sola DFS che calcola contemporaneamente profonditÓ e diametro di ciascun sottoalbero.

  • Esercizio da Completare
    • Verificare se un grafo orientato G sia singolarmente connesso.
      G Ŕ singolarmente connesso se per ogni coppia di nodi u, v se v Ŕ raggiungibile da u allora c'Ŕ un unico cammino da u a v.

  • Piccole ProprietÓ della BFS:
    • trovare un grafo G che ha un sottoalbero di cammini minimi radicato in s che non pu˛ essere ottenuto da una visita BFS(G,s).

martedý 19 marzo 2019:

  • Grafi pesati e loro rappresentazione.
  • Il problema della ricerca dei cammini di costo minimo per grafi con pesi non negativi.
  • Un algoritmi greedy: L'algoritmo di Dijkstra.
  • Prova di correttezza dell'algoritmo di Dijkstra in grafi con pesi non negativi e controesempio nel caso di pesi negativi (anche in assenza di cicli negativi)
  • Due possibili impementazione: una di tempo O(n^2) e l'altra di tempo O(mlog n). Quale e' preferibile?
  • Implementazione dettagliata in python della versione a tempo O(n^2)

giovedý 21 marzo 2019:

  • la struttura dati heap, inserimenti e cancellazioni in un heap di n elementi in tempo O(log n)
  • il modulo heapq in python e le funzioni heappop() e heappush()
  • esempio applicazione: l'implementazione dell'algoritmo di ordinamento heapsort
  • implementazione dettagliata dell'algoritmo di dijkstra tramite heap con tempo di calcolo O(mlog n)
  • Esercizio: il problema dell'assegnamento: dato un insieme di n attivita' (ciascuna caratterizzata da un tempo di inizio ed un tempo di fine) vogliamo selezionare il sottoinsieme massimo di attivita' tempo disgiunte. Esempi di algoritmi greedy sscorretti per il problema: seleziona sempre l'attivita' che dura meno oppure seleziona sempre l'attivita' che inizia prima.

venerdý 22 marzo 2019:

  • Minimizzare archi rossi in un grafo non orientato con archi rosso-neri: soluzione basata su componenti connesse e BFS su grafo delle componenti.
  • Minimizzare archi rossi in un grafo orientato con archi rosso-neri: riduzione a un problema di cammini minimi con archi rossi di peso 1 e neri di peso 0.
  • Coda di prioritÓ per Dijkstra nel caso di pesi interi e limitati da una costante W, adatto (ma non solo) al problema precedente (costo O(m+nW)).
  • Verifica in tempo O(m+n) che una soluzione dei cammini minimi sia corretta.
  • Cammini minimi su un DAG: uso dell'ordine topologico al posto dell'estrazione del nodo a distanza minima (costo O(m+n)) .
  • Aiutiamo il professore con Python. Funzione per contare i cammini tra due nodi in un DAG.
    • Versione puramente ricorsiva ed esempio di grafo su cui Ŕ esponenziale;
    • versione lineare con memorizzazione dei conteggi giÓ fatti;

martedý 26 marzo 2019: Esempi di algoritmi greedy:

  • selezione di attivitÓ: algoritmo che considera le attivitÓ per tempo di fine crescente. Prova di correttezza e sua implementazione in tempo O(n log n)
  • partizione di attivitÓ: algoritmo che considera le attivitÓ per tempo di inizio crescente. Prova di correttezza e sue imlementazioni in O(n^2) e in O( nlog n) (con l'utilizzo dell'heap)
  • Esercizio: progettare un algoritmo che in tempo O(n) preso come parametro un vettore dei padri della versione radicata di un albero T e un intero k, restituisce l'insieme dei nodi che in T hanno grado k.

giovedý 28 marzo 2019:

  • alberi di copertura di costo minimo. Un albero dei cammini minimi non e' un albero di copertura di costo minimo.
  • Algoritmo di kruskal prova di correttezza e sue possibili implementazioni.
  • La struttura dati Union and Find per insiemi disgiunti: implementazione con Union in O(n) e Find in O(1) e implementazione con Union in O(1) e Find in O(log n).

venerdý 29 marzo 2019:

  • Esercizi a richiesta:
    • Almeno uno tra G e il suo complementare Ŕ connesso;
    • Esempio di esecuzione dell'algoritmo di Tarjan;
    • Eliminazione dei cicli in un grafo orientato rimuovendo un numero minimo di archi. Discussione sulle difficoltÓ in una soluzione generale del problema (Feedback Arc Set, NP-completo).
  • ProprietÓ generali degli alberi di copertura:
    • archi leggeri su tagli; casi di unicitÓ dell'albero di supporto, etc.

martedý 2 aprile 2019:

  • paradigma del divide et impera
  • soluzione di ricorrenze del tipo T(n)=aT(n/b)+O(n^c)
  • soluzione di ricorrenze del tipo T(n)= T(an)+T(bn)+O(n) con a+b<n
  • il problema della selezione: data una lista di n interi distinti ed un intero k con 1<=k<=n restituire l'elemento che si ritroverebbe al k-mo posto nella lista una volt ordinata. Algoritmo banale a complessita' O(n log n) algoritmo basato dul divide et impera a complessita' O(n^2) algoritmo randomizzato a complessita' media O(n). Algoritmo deterministico di complessita' O(n) al caso pessimo. Correttezza e complessita' di tutti questi algoritmi.
giovedý 4 aprile 2019:
  • il problema della ricerca della coppia di punti piu' vicina: algoritmi a complessita' O(n^2) , O(n log^2 n) e O(n log n), loro implementazione e loro correttezza.
  • ESERCIZIO: data una lista ordinata di interi ed un intero x progettare un algoritmo che in tempo O(log n) restituisca il numero di occorrenze di x nella lista.

venerdý 5 aprile 2019:

  • Esercizi a richiesta pool 2:
    • albero BFS radicata in u come vettori di padri. Dire se togliere un arco (v,w) modifica le distanze da u;
    • orientare gli archi in modo da non creare cicli;
    • trovare se esiste un nodo principale in un grafo diretto; trovare il numero minimo di nodi che permette di raggiungere tutti gli altri;
  • Esercizi a richiesta pool 3:
    • algoritmo di Dijkstra e archi di peso negativo;
    • trovare il cammino superminimo;
    • massimizzare gli archi felici: funziona la strategia greedy?
  • Esempio di Divide et Impera Scorretto: alberi minimi di copertura.

martedý 9 aprile 2019:

  • differenza tra euristica e algoritmo d'approssimazione.
  • problemi di ottimizzazione
  • definizione di rapporto di approssimazione
  • il problema della copertura tramite nodi.
  • algoritmi con diversi rapporti di approssimazione, prova delle limitazioni al rapporto e complessita' dell'algoritmo risultante:
    • rapporto limitato da n-1
    • rapporto limitato da log n
    • rapporto limitato da 2
  • ESERCIZIO: Il problema della ricerca della copertura minima tramite vertici nel caso di un grafo connesso aciclico e' risolvibile in modo efficiente:
    • progettate un algoritmo che prende come parametro un grafo G aciclico e connesso di n nodi e in tempo O(n) determina il numero di nodi necessari per ottenere una minima copertura tramite nodi.

giovedý 11 aprile 2019:

  • Il vettore dei gradi di un grafo: condizioni necessarie ma non sufficienti perche' un vettore di interi sia il vettore dei gradi di un grafo, condizioni necessarie ma non sufficienti sulla somma dei valori perche' sia un vettore dei gradi di un albero.
  • il problema dei cammini superminimi in un grafo pesato con pesi interi e strettamente positivi.
  • ESERCIZI preparatori all'esonero presi da vecchie prove d'esame.
venerdý 12 aprile 2019: Esonero

martedý 16 aprile 2019:

  • correzione esercizi esonero
  • dal divide et impera alla programmazione dinamica con l'esempio dei numeri di fibonacci:
    • il fenomeno dell'overlapping di sottoproblemi
    • la memoizzazione tramite l'uso di tabelle
    • l'approccio top-down e l'approccio bottom up
giovedý 18 aprile 2019: Vacanze di Pasqua

venerdý 19 aprile 2019: Vacanze di Pasqua

martedý 23 aprile 2019: Vacanze di Pasqua

giovedý 25 aprile 2019: Festa della Liberazione

venerdý 26 aprile 2019: Ponte

martedý 30 aprile 2019: Ponte

giovedý 2 maggio 2019: Esercizi di programmazione dinamica risolvibili con tabelle in una dimensione. I primi 6 del seguente pdf lez14Tracce.pdf

venerdý 3 maggio 2019:

  • Esercizi su programmazione dinamica (i restanti 3 dalle tracce precedenti):
    • Strategie vincenti nel gioco dei gettoni. Versione memoizzata e ricostruzione della strategia vincente.
    • Scomposizione di un numero come somma di quadrati. Versione memoizzata e ricostruzione della soluzione.
    • Dimostrazione che la soluzione ottima si costruisce da soluzioni ottime di istanze pi¨ piccole (proprietÓ di sottostruttura).
    • Esempio di problema che non ha la proprietÓ di sottostruttura: cammini semplici di lunghezza massima in un grafo.
    • ComplessitÓ del calcolo dei numeri di Fibonacci.

martedý 7 maggio 2019: Esercizi di programmazione dinamica risolvibili con tabelle in due dimensioni.

In particolare:

  • data una matrice binaria n x n verificare in O(n^2) se esiste un cammino che va dalla cella in alto a sinistra alla cella in basso a destra. Nel cammino ci si pu˛ spostare tra celle adiacenti e solo in orizzontale verso destra e in verticale verso il basso.
  • Data una matrice n x n contenente i numeri da 1 a n^2 trovare in O(n^2) la lunghezza massima tra quelle dei possibili cammini incrementali. Un cammino si dice incrementale se parte da una cella, si sposta di volta in volta in una delle al pi¨ 4 celle adiacenti in orizzontale o verticale e tocca soltanto celle contenenti numeri consecutivi.
  • Problema dello zaino. Dato uno zaino di capacitÓ C ed n oggetti caratterizzati da n pesi ed n valori trovare in O(nC) un sottoinsieme degli oggetti che abbia peso limitata da C e valore massimo. Il peso di sun sottoinsieme di oggetti e' dato dalla somma dei pesi degli oggetti mentre il valore di un sottoinsieme di oggetti Ŕ dato dalla somma del valore degli oggetti. Algoritmi pseudopolinomiali
  • Problema della pi¨ lunga sottosequenza comune. Date due sequenze X (composta da n catratteri) e Y (composta da m caratteri), trovare in O(nm) la sottosequenza comune a X e Y di lunghezza massima.
Le tracce sono nel seguente pdf lez15tracce.pdf

giovedý 9 maggio 2019:

  • Algoritmo di Bellman-Ford per la ricerca di cammini di costo minimo in grafi pesati con pesi anche negativi ma privi di cicli negativi. Implementazione dell'algoritmo in tempo O(n^2+nm).
  • Algoritmo per testare O(n^2+nm) se un grafo pesato con pesi anche negativi ha cicli negativi.
  • ESERCIZIO. Risolvere in O(nC) il problema della zaino nel caso in cui siano disponibili piu' copie di uno stxesso oggetto.

venerdý 10 maggio 2019:

  • Il problema del cammino pi¨ lungo in un DAG.
    • Dimostrazione della proprietÓ di sottostruttura ottima.
    • Cenni sull'implementazione ricorsiva memoizzata.
    • Versione bottom-up.
  • Il problema della massima sottosequenza palindroma.
    • Dimostrazione della proprietÓ di sottostruttura ottima.
    • Cenni sull'implementazione ricorsiva memoizzata.
    • A gentile richiesta del pubblico: versione bottom-up in C.

martedý 14 maggio 2019:

  • Nozioni elementari di matematica utile agli informatici:
    • Numero di nodi interni e numero di foglie in alberi t_ari completi di altezza h.
    • Numero di nodi interni e numero di foglie in alberi di di permutazione di altezza n.
  • Problemi di enumerazione: dalla ricerca esaustiva al backtraking.
  • Algoritmo ottimo per la stampa in Θ(n2^n) tempo di tutte le stringhe binarie di lunghezza n con implementazione in python
  • Algoritmo ottimo per la stampa in Θ(n^2 2^(n^2)) di tutte le matrici binarie quadrate di lato n. con due diverse implementazioni in python.
  • Il backtraking e le funzioni di taglio per ottenere algoritmi di enumerazione con complessita' proporzionale al numero di oggetti da enumerare:
    • stampare in tempo O(nS(n,k)) le S(n,k) stringhe binarie lunghe n con esattamente k uni
    • stampare in tempo O(n^2S(n)) le S(n) matrici quadrate binarie di lato n in cui non compaiono mai 1 adiacenti (in orizzontale, verticale o diagonale)
giovedý 16 maggio 2019: Ancora sul backtraking:
  • algoritmo esaustivo ottimo (di tempo O(n!n)) per generare tutte le permutazioni lunghe n ed algoritmo di backtraking di tempo O(S(n)n^2) per stampare tutte le S(n) permutazioni che contengono gli elementi pari nelle posizioni pari.
  • algoritmo basato sul backtraking per problemi decisionali:
    • dato un grafo deteminare se ha o meno una $3$-colorazione
    • dato un grafo determinare se e' o meno hamiltoniano
  • il backtraking per risolvere anche problemi di ottimizzazione (il problema dello zaino)

venerdý 17 maggio 2019:

  • Alcuni problemi risolvibili con backtracking:
    • Verificare se una sequenza Ŕ il mescolamento ordinato di altre due sequenze.
    • Verificare se un numero Ŕ semiperfetto, cioŔ uguale alla somma di un sottoinsieme dei suoi divisori propri.
    • Il problema del giro di Cavallo.
    • Trovare una soluzione, trovare tutte le soluzioni.
    • Brevi cenni al problema delle n regine.

martedý 21 maggio 2019:

  • richiami della visibilita' delle variabili in python: variabili locali, variabili nonlocali e variabili globali
  • Il problema dello zaino: algoritmo esaustivo e algoritmo di backtraking, implementazione edei vari algoritmi.
  • illustrazione della traccia di 5 problemi di ricerca e di ottimizzazione che puo' essere utile approcciare e cercare di risolvere per esercitarsi con la tecnica del backtracking: lez19tracce.pdf
giovedý 23 maggio 2019: esercizi.
  • Illustrazione dell'algoritmo proposto da alcuni studenti per il problema del sudoku (primo degli esercizi del file lez9trazze.pdf)
  • Progettare un algoritmo esaustivo che prende come parametro un intero n e in tempo O(n3^n) stampa tutte le stringhe lunghe n sull'alfabeto {'0','1','2'}
  • Progettare un algoritmo di backtraking che prende come parametro un intero n e stampa tutte le stringhe lunghe n sull'alfabeto {'0','1','2'} che non contengono nÚ la sottostringa '02' nÚ la sottostringa '20'. L'algoritmo deve avere complessitÓ O(nS(n)) dove S(n) Ŕ il numero di stringhe da stampare.
  • Progettare un algoritmo di backtraking che prende come parametro un intero n e conta le stringhe lunghe n sull'alfabeto {'0','1','2'} che non contengono come sottostringa nÚ '02' nÚ '20'. L'algoritmo deve avere complessitÓ O(nS(n)) dove S(n) Ŕ il numero di stringhe da contare.
  • Progettare un algoritmo di backtraking che prende come parametro un intero n e conta le stringhe lunghe n sull'alfabeto {'0','1','2'} che non contengono come sottostringa nÚ '02' nÚ '20'. L'algoritmo deve avere complessitÓ O(n)

venerdý 24 maggio 2019: Esercizi ad ampio spettro in vista dell'esame:

  • Divide et Impera: il problema del minimo intero mancante;
  • Algoritmi Greedy: il problema della scelta ottima dei distributori in un viaggio.
  • Grafi: determinare la persona con pi¨ amici e amici di amici nel grafo delle amicizie di un social network;
  • Backtrack: Analisi del problema dei francobolli.

martedý 28 maggio 2019: Esercizi:

  • dato un grafo diretto di n nodi ed m archi ed un suo nodo s progettare un algoritmo che in tempo O(n) restituisce un ciclo raggiungibile da s se questo esiste, None altrimenti.
  • Il problema del mescolamento: date tre stringhe le prime due di lunghezza n e l'ultima di lunghezza due n trovar eil mescolamento delle due prime stringhe nella terza, se esiste, None altrimenti.
    • l'algoritmo greedy di tempo O(n) che funziona solo nel caso in cui le prime due stringhe non hanno simboli in comune.
    • cenni sull'algoritmo di backtraking di complessitÓ 2^O(n) gia visto in una delle scorse lezioni
    • algoritmo di complessita' O(n^2) basato sulla programmazione dinamica.
giovedý 30 maggio 2019: ESERCIZI
  • Programmazione dinamica: date n monete "truccate" , un intero k<=n e conoscendo p_1,\ldots p_n, dove p_i, con 1<=i<=n e' la probabilita' che il lancio della i-esima moneta dia Testa, vogliamo calcolare la probabilita che un lancio delle n monete produca esattamente k teste. Progettare un algoritmo che risolve il problema in tempo O(nk).
  • backtracking: progettare un algoritmo che prende come parametro un intero n e restituisce il numero di stringhe sull'alfabeto ternario {a,b,c} con la proprietÓ che il numero di adella stringa Ŕ limitato dal numero di b della stringa e il numero di b della stringa Ŕ limitato dal numero di c della stringa. L'algoritmo deve avere complessitÓ O(nS(n)) dove S(n) Ŕ il numero di stringhe che bisogna contare.

venerdý 31 maggio 2019: Esercizi in vista dell'esame:

  • Programmazione Dinamica: il problema delle partizioni;
  • Programmazione Dinamica: Segmentare una stringa in modo ottimo (problema 15.9 Cormen);
  • Backtrack: Analisi di un problema di puzzle.

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf intermedia2017.pdf r1 manage 143.7 K 2018-04-19 - 07:15 AngeloMonti  
PDFpdf lez14Tracce.pdf r1 manage 540.2 K 2019-05-02 - 15:24 AngeloMonti esercizi
PDFpdf lez15tracce.pdf r1 manage 384.4 K 2019-05-07 - 15:27 AngeloMonti  
PDFpdf lez19tracce.pdf r1 manage 927.0 K 2019-05-21 - 15:59 AngeloMonti  
Edit | Attach | Watch | Print version | History: r177 < r176 < r175 < r174 < r173 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r177 - 2019-06-03 - IvanoSalvo





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback