Algoritmi e Strutture Dati

Algoritmi e Strutture Dati

Appunti

Algoritmi e Strutture dati. Lezione n°1

Introduzione:

• Al Khuwarizmi: Algoritmi (matematico persiano)
• Knutth: calcolo della complessità degli algoritmi

Principio di "inclusione aritmetica" a p.esim:

∑_n = ∑ⁿ = (n (n + 1)) / 2 K=1         2

somma intera da 1 ad n

Logaritmi:

Proprietà: b = base, x ed y numeri

• log_b (x ∙ y) = log_b x + log_b y
• log_b (x / y) = log_b x - log_b y
• log_b (xⁿ) = n log_b x
• log_b (b) = 1
• log_b (1) = 0
• log_b (bⁿ) = n

Proprietà del cambiamento di base dei Logaritmi:

con a > 0 e a ≠ 1

• log_b x = log_a x
• log_b a

(log_a b va al denominatore) posto che il reciproco è una costante: 1/k è una costante, e lo posso definire con la lettera C:

• log_a b = C
• anche essere un elevante
• alla fine del calcolo

deleteMax per code di priorita in heap binario

prendo l'elemento piu a destra dell'ultimo livello e lo scambio con la radice (che se ne va)

scelgo la chiave massima tra quelle dei tre figli

N.B.

Altrimenti non rimarrebbe l'integrita dell'heap binario

Risultato finale:

La complessità dunque e log₂ n una volta e occorre una simile a proviera trovare la livello 2

n da tempestare per risultato che isficamente

• Promemoria domande nella complessità di una operazione nell'heap binario
• firstMAX (pq)=elem
• l₂ det: maggior l'elemento nella radice dell'T
• L'elemento m trova in posizione s
• Complesso temporale O(1)

Insert(e_i, k_i, pq)=pq

• si inserisce la coppia chiave-valore come ultimo elemento dello heap.
• Ora bisogna verificare m è nella posizione giusta (ogni nodo deve avere una chiave maggiore da quella dei miei figli).

Ammetti insert(e_i, k_i, pq)

• crea un nuovo nodo v nello heap pq, inserendolo in posizione m_s dell'array [v contiene (k_i, e_i)]
• muovi Alto(v, pq)

Procedura muoviAlto(v, pq)

• While (v ≠ radice(pq) and t=(chiave(v))>chiave(padre(v)), allora scambia v e padre(v) in pq nell'array H

Esempio: insert((Giona-lions), 7-26, pq)

Risultato Finale:

Albero di Ricoprimento del Grafo G

Visita in profondità:

• Procedura visita DFS Ricorsiva
  • marca e visita il vertice v
  • for each (arco (v, w)) do
    • if (w non è marcato) then
    • per ogni vertice adiacente a w
    • questo w non deve essere marcato
    • aggiungi l’arco (v, w) all'albero T
    • visita DFS Ricorsiva (w, T)
• Algoritmo visita DFS (vertice s) -> albero
  • T ← albero vuoto / rimuovi tutti i vertici non marcati
  • visita DFS Ricorsiva (s, T)
  • return T

Dovrà anche modificare la struttura delle R(M) in aggiungendo il dato che deve tenere conto del vertici da cui proviene e all'etichetta corrispondente della lista di adiacenza.

struct halfEdgeVertex {

int label label;

};

Non ci sono più posizioni Vertices < Vertex.pipe, raggiungibile da c Vertices < 1/2 posizione di vertice informatica Weight weights;

List(Vertex => label) multi EdgeVertex * next;

Es.: Esempio:

Manchester Nottingham Norwich London

Liste di Adiacenza

ASD LEZIONE n.25

Al p.v.a. di essere un array, da un puntatore le liste di adiacenza è una lista collegata. Questo ci consuma meno bites ma più difficile ad accedere perché dobbiamo scorrere le liste mentre prima bastava fare a [ ] e accedavamo ad un vertice.

Gli archi possono avere dei "pes... Esempio: RAPPRESENTANDO

Manchester -> Nottingham, 7 Nottingham -> London, 420

Strutture dati per grafi più diffuse

• Liste di Adiacenza:
  • Ogni vertice memorizza inc. in un array oppure in una lista
• Le matrici di Adiacenza

Liste di Adiacenza occupano spazio

Ogni nodo acc. al nodo i

In un grafo non orientato un arco è rappresentato due volte.

In un grafo Orientato

Ogni arco è descritto da:

1. Un elemento nella lista di adiacenza se il grafo è orientato
2. Due elementi se il grafo non è orientato

(2 x m blocchi) [n + 2m blocchi ... totale]

Grafi orientati: connesso

• Definizione: Un grafo orientato G è fortemente connesso se e solo se esiste un cammino da ogni vertice v di G ad ogni vertice w di G con v ≠ w.

Un grafo orientato, fortemente connesso

Un grafo orientato, non fortemente connesso (esempio: cammino da B, C, D a A)

Albero libero:

• Definizione: Un albero libero è un grafo non orientato, connesso e senza cicli.

• Osservazione: Un albero libero si ottiene da un albero radicato in quanto un albero libero non sente la radice.

Comb. se aggiungiamo un arco

È un albero connesso minimale in cui se si toglie la connessione

Teorema:

Se rimuoviamo un arco da un albero libero perdo la connessione su quest'ultimo.

Teorema:

Se n è il numero di vertici di un albero libero H, allora H ha esattamente n-1 archi.

Errore:

deleteElemR(const Label L, Tree &T) {

• parte l'rumore sicure rumore chiamato
• non si deve sbagliare ridurre
• con righelli molto cancellazione sulla radice
• se l'etichetta c'è la stessa
• se non sono in quel ramo allora devo
• rimuovere una funzione anch'essa
• deleteElemAux allora tra sicuramente;
• che ne vo con trovare quella delle
• cancellazione della radice che ho
• trattato prima

return deleteElemAux(L, T);

}

Errore deleteElemAux(const Label L, Tree &T) {

• caso 1: se t'è vuot non c'è nulla da
• cancellare : return FAIL
• caso 2: se t'fra un figlio con etichetta L
• lo rimuovo tenendo conto di
• "aggiuntare" i produttori di dove
• era che prenunciato questo nostra
• rispetto ai fratelli (primo figlio e l'ultima)
• return OK
• caso 3: se siamo arrivati qui i nodi che ho
• trovato non avevano quell’etichetta
• ma loro successori osservar mi.
• ancora offerta ho rimanuto rimuovi
• vol deleteElemAux ma fighe che
• che è ancora esplatava
• return OK se trovato, FAIL altrimenti.