Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmi - Coggle Diagram

- - - - inserendo tot elemeneti
        
        specifico rotazioni
        
        specifico che nodo era sbilanciato
    - - inserendo tot elementi
        
        indico posizione inserimento
    - - secondo criterio AVL?
      - perfettamente bilanciato?
      - ha altezza minima?
    - - b elementi inserendo questi
      - uso double hashing per risoluzione collisioni
        
        basta fare hashing con prima funzione. Se non sufficiente faccio hashing con seconda e poi concateno sommando. Se c'è ancora conflitto moltiplico f2 per le volte che lo sto facendo e trovo modulo della grandezza della tabella in modo da farla rientrare in quei parametri.
      - come gestirebbero collisioni se closed hashing?
        
        Combinano calcoli per trovare una nuova cella libera all'interno della tabella di hash
      - come gestirebbero collisioni se l'altro hashing?
        
        utilizza array nelle celle, c'è il rischio che questi array diventino molto lunghi e quindi sconvenienti
      - se usassi linear probing al posto di quadratic probing, permetterebbe riduzione numero collisioni in questo esempio? E in generale?
        
        In generale linear probing ha il problema del clumping o accumuli. Zone della tabella tendono a riempirsi non uniformemente, causando zone della tabella ad essere impopolate e altre troppo affollate
    - - variante: con mantenimento AVL
  - - - albero coprente a costo minimo (MST)
        grafi non orientati, ma pesati e connessi
        
        Kruscal (greedy)
        
        ogni nodo è albero a se stante
        
        ad ogni passo scelgo arco con costo minore che collega 2 alberi separati, alla fine ogni nodo appartiene allo stesso albero
        
        costo
        
        O(|E| log |V|)
        
        Prim (greedy)
        
        considero sorgente come albero composto da un solo nodo
        
        ad ogni passo aggiungo all'albero il nodo con l'arco a costo minore valutando tra tutti gli archi non ancora scelti e che partono da nodi già aggiunti
        
        Uso Prim quando ho tanti edge, Kruskal quando ne ho pochi
      - cammino minimo ogni nodo dal nodo x (ShortestPath)
        
        grafo pesato
        
        Bellman-Ford (non greedy, usa rilassamento)
        
        costo O(|V|*|E|)
        
        Faccio passata su tutti i nodi e vedo se la scoperta precedente di qualche path mi aiuta a rilassare ulteriori path
        
        Mi fermo quando non sto più rilassando, oppure quando iterazione > n-1 nodi, perchè vuol dire che c'è un ciclo di edge negativi che mi fa rispondere "si" al rilassamento all'infinito
        
        Djikstra (solo pesi positivi, greedy)
        
        costo complessità
        
        O(|E| log |V|) se con liste adiacenza
        
        da O(|V2|) con matrice adiacenza
        
        Selezionare ricorsivamente il prossimo nodo non visitato, aggiornando il costo di ogni altro nodo, finchè non si ha raggiunto obiettivo
        
        Djikstra è più efficiente quindi lo uso di default. Se ci sono pesi negativi uso Bellman-Ford
        
        grafo non pesato
        
        Cammino minimo è cammino con numero minore di archi
        
        BFS (breadth first search)
        
        Cerco a macchia d'olio
        
        DFS (depth first search)
        
        Cerco verticalmente poi torno a vedere rami inesplorati
        
        BFS nel caso peggiore performa come DFS, quindi uso BFS la maggior parte del tempo
    - - devo farlo manualmente, considerare le eventuali altre opzioni
  - - - Considero coppia di elementi
      - Confronto valori, se fuori ordine li scambio
      - Faccio finchè arrivo alla dx dell'array
      - itero fino che ho l'array ordinato
    - - scelgo pivot
        
        una scelta randomica consente di minimizzare di incappare nel caso peggiore O(n^2)
        
        scelta del valore centrale va bene nella maggior parte di casi
      - sposto alla fine dell'array
      - trovo elementoDaSinistra più grande di pivot
      - trovo elementoDaDestra più piccolo di pivot
      - se non si "incrociano" posso scambiare i due valori. finchè non ce ne sono più da scambiare
      - quindi riposiziono pivot scambiandolo con l'ultimo elementoDaSinistra
      - ripeto il processo spezzando l'array a dx e sx del pivot che ho appena riinserito, ripetendo l'operazione fino che tutti i sottoarray sono ordinati e posso ricombinarli a formare il principale
    - - build-max-heap
        
        costruisce max-heap da array non ordinato
        
        passaggi
        
        rappresentiamo array in albero binario (NON BST, semplicemente posiziono elementi in root, poi figlio sx e poi figlio dx, e così via fino a finire elementi)
        
        facciamo risalire numero maggiore alla radice
        
        posizioniamo radice alla fine dell'array, swappandolo con l'elemento in coda all'array e lo consideriamo ordinato, scambiandolo con il primo elemento dell'array e eliminandolo dall'albero.
        
        ora continuiamo il processo fino che è tutto in ordine
        
        costo O(n)
      - heapify
        
        assumiamo che parte dell'array sia già ordinato
        
        costo O(logn) o n-1 volte
    - - considero i primi due numeri
        
        se non sono ordinati li scambio
      - includo il terzo numero, e lo riordino se non è in ordine. Così via finchè tutto è ordinato
    - - prendo il primo numero, lo swappo con il numero più piccolo di esso, finchè non è tutto ordinato
    - - divido array fino alle sue componenti unitarie.
      - unisco per coppie sortando, ricompongo pezzi array sortandoli finchè non mi riconduco ad array principale
  - - - Creo albero, con coefficente di T come numero di rami che ogni foglia ha e sostituendo valore T(n) all'eq
      - Generalizzo per il livello i
      - Moltiplico costo nodo per numero nodi a livello generico
      - Calcolo numero di livelli (incognita = 1, in questo modo diventa frazione e posso usare logaritmi)
      - Calcolo costo complessivo con sommatoria di logaritmo
- - - - stack
        
        tipo particolare di lista dove operazioni inserimento e cancellazioni avvengono solo ad un'estremità (top)
        
        Last In First Out
        
        operazioni
        
        Push (x, S) inserisce x in stack S
        
        Pop(S) rimuove elemento on top
        
        Top(S) restituisce elemento on top
        
        Makenull(S) svuota lo stack
        
        Empty(S): restituisce TRUE solo se stack è vuoto
        
        implementazioni
        
        Array
        
        con variabile aggiuntiva "top" che tiene in memoria posizione ultimo elemento inserito in stack.
        
        costo ogni operazione: O(1)
        
        operazioni
        
        top = 0 svuota lo stack
        
        top == 0 controlla se stack vuoto
        
        Puntatori
        
        costo uguale a array
        
        puntatori puntano in ordine inverso gli elementi dello stack, ovvero ogni elemento punta all'elemento inserito prima di lui.
        
        il top è il puntatore che punta a qualcosa ma che non ha il successore (niente lo punta)
      - queue
        
        tipo particolare di lista dove operazioni inserimento si fanno in coda, mentre le rimozioni in testa
        
        operazioni
        
        enqueue(x, Q) inserisce x in coda Q come ultimo elemento
        
        dequeue(Q) rimuove elemento in testa alla coda
        
        front(Q) restituisce primo elemento (in testa)
        
        makenull(Q) svuota coda Q
        
        empty(Q) restituisce TRUE solo quando Q è vuota
        
        implementazioni
        
        array
        
        come una lista, in ogni cella c'è un elemento e possiamo sempre sapere cosa c'è prima/dopo
        
        se array circolare, serve variabile booleana per tenere traccia di testa/coda soprattutto per i casi di tutto pieno/vuoto
        
        costo operazione: O(1), posizioni note, non devo mai scorrere tutta la coda
        
        puntatori
        
        2 puntatori che tengono traccia di testa/coda
        
        costo operazione O(1)
        
        First In First Out
    - - cammino minimo
      - albero coprente costo minimo
    - - grado di un nodo (grafi orientati e non)
      - orientato
        
        quando il cammino può essere percorso unilateralmente
      - non orientato
        
        connesso, con n nodi. Quanti archi? Min e max giustificando
        
        quando il cammino può essere percorso avanti e indietro
      - definizion
        
        coppia (V,E) con V nodi/vertici e E archi/edge
        
        può essere
        
        connesso
        
        non è orientato e esiste un cammino che connette ogni coppia di nodi mutualmente raggiungibili
        
        fortemente connesso
        
        orentato, per ogni coppia di vertici si può raggiungere ognuno dei due dall'altro
      - implementazioni
        
        matrice adiacenza
        
        array bidimensionali (funziona come tabella)
        
        per archi non pesati si usa 0 1 nelle celle per presenza o no dell'arco
        
        per archi pesati si usa il peso dell'arco, nel caso di non presenza si usa infinito?
        
        svantaggio
        
        richiede di occupare spazio V^2 anche con pochi archi.
        
        costo
        
        O(V^2), molto inottimizzato
        
        particolarità
        
        per grafi non orientati matrice risulta simmetrica
        
        liste di adiacenza
        
        array monodimensionale dimensione V
        
        all'interno di ogni cella c'è una lista che contiene nodi indici raggiungibili direttamente (adiacenti) a nodo.
        
        lunghezza uguale al numero archi per grafi orientati, e 2*numero archi per grafi non orientati
        
        vantaggio
        
        costo computazionale minore nello scorrere lista rispetto matrice, ma se grafo denso archi e liste sono lunghe
        
        caso uso
        
        quando grafo non denso uso liste, quando denso uso matrice
      - viste
        
        algoritmi
        
        BSF (Breadth Search First)
        
        parte da nodo speciffico indicato in algoritmo. Esplora tutti gli altri nodi in ordine di distanza in termine di archi dalla sorgente (macchia d'olio)
        
        Possiamo stabilire distanze di ogni nnodo da sorgente e costruire albero, che cambierà in base al nodo di partenza
        
        costo
        
        O(|V|+|E|)
        
        DFS (Depth First Search)
        
        partendo da sorgente, va in profondità. segue adiacenza sorgente fino che non può più proseguire
        
        questo lo fa finchè ogni nodo è stato visitato
        
        classificazione archi
        
        tree edge: archi fforesta DFS
        
        se ci sono solo questi = grafo non orientato
        
        back edge: arco che connnette nodo a antenato v in foresta DFS
        
        se si sono vuol dire che ci sono loop
        
        1 more item...
        
        forward edge: arco che connette nodo a un suo discendente
        
        cross edge: archi che collegano 2 alberi diversi
    - - algoritmo:
        
        input: sequenza valori
        
        output: sequenza valori ordinata
      - tipologie
        
        in base a spazio occupato
        
        algoritmi complessi con complessità O(n*logn)
        
        merge sort
        
        heap sort
        
        quick sort
        
        algoritmi semplici con conplessità quadratica O(n^2)
        
        insertion sort
        
        selection sort
        
        bubble sort
        
        in base a complessità
        
        interni
        
        non occupano spazio aggiuntivo a struttura dati (gli basta la ram)
        
        esterni
        
        sfruttano spazio di memoria aggiuntivo esterno a struttura dati per essere eseguiti (ad esempio se hannno bisogno di array). hanno bisogno di memoria di massa
        
        classificazione generica
        
        basati su confronto
        
        costo minimo è O(n * logn), per quelli più semplici è O(n^2)
        
        non basati su confronto
        
        riordinano valori senza confronto, quindi caso medio battono algoritmi basati su confronto (costo lineare O(n)). Efficienti ma poco flessibiili
        
        costo caso ottimo O(n), caso peggiore O(n^2)
    - - implementazione
        
        bit-vector
        
        liste linkate
        
        tabelle di hash
        
        array lunghezza fissa
        
        funzionamento
        
        ad ogni elemento viene associata una chiave univoca
        
        hashing: applicando una funzione di hash alla chiave h(k) si può ottenere l'indice di posizionamento di un elemento in un bucket dell'array
        
        collisioni
        
        essendo inevitabili le funzioni di hashing devono avere un modo per gestirle, conosciamo
        
        open hashing
        
        1 more item...
        
        closed hashing
        
        1 more item...
        
        costo
        
        caso medio: O(1)
        
        vantaggi
        
        riduce spazio necessario per memorizzazione a O(|k|)
        
        non richiede assunzioni o previsioni su dimensione dell'insieme universo
        
        permette di accedere a valori in modo efficiente perchè indice viene calcolato in modo più rapido di quanto ci si metterebbe a scorrere l'intero array
        
        metodi applicabili
        
        della divisione
        
        del prodotto
  - - - Procedimento formato da sequenza finita di operazioni elementari che trasformano input in output
    - - costo ricerca elemento?
      - se inserimento causa collisione?
    - - Omega
        
        limite inferiore di T(n) al crescere di n. Per ogni valore di n a partire da un certo punto n0, il valore T(n) è sempre maggiore o uguale a una costante moltiplicata per la funziona
        
        lower bound
      - Theta
        
        indica il limite di T(n) al crescere di n. Ciò significa che per ogni valore di n a partire da un certo punto n0, il valore di T(n) è sempre compreso tra una costante c1 e una c2 moltiplicate per g(n)
        
        average bound
      - O Grande
        
        massimo limite superiore di T(n) al crescere di n per ogni valore di n a partire da un certo punto n0. Il valore è sempre minore o uguale a una costante moltiplicata per g(n)
        
        upper bound
      - proprietà
        
        transitività
        
        riflessività
        
        simmetria
      - operazioni possibili
        
        somma
        
        prodotto
    - - altezza
        
        numero di livelli di un albero dalla radice alle foglie
        
        numero di grado albero + 1
      - bilanciato perfetto
        
        (lower bound di log n) + 1
      - composto da 100 nodi, quanti archi? Giustifica.
        
        99 archi? credo la regola sia numero nodi - 1
      - Binario (BST)
        
        AVL
        
        come funziona ricerca valore minimo con n nodi?
        
        descrivere condizione bilanciamento. albero d'esempio
        
        er ogni nodo x l’altezza del suo sottoalbero sinistro non può differire per più di 1 dal quella del sottoalbero destro. La proprietà di bilanciamento deve valere per ogni nodo dell’albero
        
        minimo/massimo nodi?
        
        minimo 1 max inf?
        
        metodo per trovare valore minimo
        
        scorro l'intera altezza sul ramo più a sx possibile
        
        tempo costante quindi costo=O(log n)
        
        costo
        
        vista in-order
        
        O(N) con N numero nodi
        
        da 63 nodi, calcolo massimo foglie
        
        con altezza H = 3, calcolo max/min nodi
      - Definizione grado
        
        di un nodo
        
        numero di figli che ha
        
        di un albero
        
        grado del nodo che ha grado massimo
      - definizione
        
        collezione elementi detti nodi, uno dei quali radice. Sono tra di loro in relazione padre-figlio.
      - operazioni possibili
        
        parent
        
        restituisce genitore
        
        leftmost_child
        
        figlio più a sx
        
        right sibling
        
        fratello a dx
        
        label
        
        ritorna etichetta nodo
        
        create
        
        albero con un certo numero di nodi in un certo rapporto
        
        root
        
        ritorna nodo radice dell'albero
        
        makenull
        
        rende albero nullo
      - implementazioni
        
        array
        
        vantaggi
        
        semplice trovare genitore di un elemetno perchè usiamo elemento: costo O(1)
        
        figlio sinistro-fratello destro
        
        lista di figli
      - vista
        
        raggiungimento sistematico di ogni suo nodo
        
        algoritmi
        
        in profondità
        
        pre order
        
        prima radice, poi figli sinistri finchè posso, per poi tornare a tutti i figli dx che non ho visto
        
        in order
        
        parto dalle foglie, figlio sx, padre, figlio dx
        
        post order
        
        scendo in fondo all'albero, prima figli (sx-dx) poi padre
        
        in ampiezza
        
        percorso l'albero un livello alla volta
    - - Counting sort
        
        O(n+k), rischia costo quadratico se k = n
      - Regola somma (complessità asintotica) con esempio applicazione
        
        se algoritmo è composto da diverse parti (esecuzione in sequenza), la complessità si valuta considerando la parte più complessa perchè domina sulle altre
      - Regola prodotto con esempio applicazione
        
        se algoritmo composto da diverse parti eseguite in parallelo, la complessità sarà la moltiplicazioni tra queste parti
      - Costo inserimento lista ordinata o non ordinata (giustifica)
      - Data lista trovare massimo, costo e caso ordinato
        
        caso ordinato è O(1) perchè basta che prendo la fine dell'array o del puntatore
        
        caso non ordinato è n-1 volte ovvero O(logn) perchè devo confrontare ogni valore con quello di riferimento
      - Descrivere heap, caratteristiche e implementazione comune
      - Merge sort
        
        complessità theta(n*logn) caso medio
        
        complessità O(1) nel caso migliore
      - di algoritmo ordinamento basato su confronti
        
        O(n*logn)
      - costo vista ampiezzza grafo G(V, E)
    - - non orientato
        
        connesso, 6 archi, quanti nodi? Max min
        
        dipende se un grafo è
        
        semplice (no loops)
        
        non ha limite superiore, il minimo sono 5 (n-1) nodi
        
        completo (fortemente connesso)
        
        n*(n-1)/2 il numero massimo, il minimo è 9 (calcolato a mente)
    - - Implementaizone operaziozni intersez, unione, differenza
    - - definizione generale e a cosa serve. Con esempio
  - - - disegna albero ricorrenza
      - passaggi calcolo complessità computazionale (graficamente con albero)
    - - utilizzo specchietto per i casi. Sono in difficoltà con i logaritmi
    - - credo basti calcolare complessità computazionale, ma poi metterla in forma di f(n) + c, differenziare con un sistema se c'è un if