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: ...

giovedý 28 marzo 2019: ...

venerdý 29 marzo 2019: ...

martedý 2 aprile 2019: ...

giovedý 4 aprile 2019: ...

venerdý 5 aprile 2019: ...

martedý 9 aprile 2019: ...

giovedý 11 aprile 2019: ...

venerdý 12 aprile 2019: ...

martedý 16 aprile 2019: ...

giovedý 18 aprile 2019: ...

venerdý 19 aprile 2019: ...

martedý 23 aprile 2019: ...

giovedý 25 aprile 2019: ...

venerdý 26 aprile 2019: ...

martedý 30 aprile 2019: ...

giovedý 2 maggio 2019: ...

venerdý 3 maggio 2019: ...

martedý 7 maggio 2019: ...

giovedý 9 maggio 2019: ...

venerdý 10 maggio 2019: ...

martedý 14 maggio 2019: ...

giovedý 16 maggio 2019: ...

venerdý 17 maggio 2019: ...

martedý 21 maggio 2019: ...

giovedý 23 maggio 2019: ...

venerdý 24 maggio 2019: ...

martedý 28 maggio 2019: ...

giovedý 30 maggio 2019: ...

venerdý 31 maggio 2019: ...

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf intermedia2017.pdf r1 manage 143.7 K 2018-04-19 - 07:15 AngeloMonti  
Edit | Attach | Watch | Print version | History: r151 < r150 < r149 < r148 < r147 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r151 - 2019-03-23 - 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