🎓Matteo Galletta

Dimostrazioni

Feb 03, 20242 min read

universitystudyingsubject-2101

2024-02-03

Algoritmi

Di seguito degli appunti per ripassare molto velocemente i passaggi delle varie dimostrazioni.

Heap

Proprietà Invariante

Build Max-Heap

Thm: “la complessità di BuildMaxHeap è “
Proof:

  • si ricorda che: un heap di elementi ha altezza e al più nodi radici di sotto-alberi di altezza .
  • si scrive , ovvero come somma del costo di ogni livello.
  • Si sostituisce, si semplifica, e si riconduce alla serie notevole

Hash Maps

Metodo concatenazione

Ricerca Senza Successo

Thm: “Il tempo atteso di ricerca senza successo di un elemento in un hash map con metodo di concatenazione è “
Proof:

  • è il tempo di calcolare
  • è il tempo necessario per scorrere tutti gli elementi.
Ricerca Con Successo

Thm: “Il tempo atteso di ricerca con successo di un elemento in un hash map con metodo di concatenazione è “
Proof:

  • Si definisce
  • Si definisce
  • Si definisce
  • Si cerca di calcolare , sostituendo , semplificando, portando fuori.

Metodo indirizzamento aperto

si assume che (e non - cioè la hash map non è piena)

Ricerca Senza Successo

Thm: “Il numero atteso di prove in una ricerca senza successo di un elemento in un hash map a indirizzamento aperto è “
Proof:

  • Si definisce e
  • Si definisce
  • Si calcola
  • Si calcola , dividendo la serie in due, prendendo la serie resto.
Ricerca Con Successo

Thm: “Il numero atteso di prove in una ricerca con successo di un elemento in un hash map a indirizzamento aperto è “
Proof:

  • Si giustifica “se è l’-esimo elemento a essere stato inserito…”
  • Si fa la media di tutte le chiavi
  • Si porta fuori dalla serie, si scrive in funzione di k, si sostituisce con l’integrale, si raccoglie

Red Black Trees

Altezza massima

Thm: “Un RBT ha altezza al più “
Proof:

  • si dimostra il Lemma “Il sotto-albero radicato a contiene almeno nodi interni”
    • si usa l’induzione
  • todo

Programmazione Dinamica

Sottostruttura ottima

Si dimostra che un problema gode della proprietà della sottostruttura ottima dimostrando che ipotizzando che non utilizzi un sottoproblema non ottimo si arriva a una contraddizione.

  • Rod-Cut
  • Parentesizzazione Matrici
  • LCS

Programmazione Greedy