Tecniche algoritmiche

In questa nota andiamo a parlare in modo sommario (si impara probabilmente molto meglio con la pratica) di generali tipologie di approcci che esistono per affrontare problemi di tipo algoritmico.

Divide et impera

Introduzione

Abbiamo già visto L’utilizzo di questa tecnica per quick e merge sort in Algoritmi di ordinamento

Questa tecnica si focalizza in tre passi fondamentali:

1. Dividere il problema in sotto-problemi
2. Risolvere il sotto-problema
3. Mergiare le soluzioni di questi sotto-problemi.

Questa è più una tecnica che si impara di più con la pratica, andremo a fare un problema che utilizza questa tecnica

La torre di Hanoi

• Enunciato

  

• Soluzione con ricorsione

  

Moltiplicazione fra interi

Questo potrebbe sembrare semplice. In realtà per numeri più grandi del limite dei registri (le macchine moderne sono tutte a registri, secondo il modello di Estensioni di Turing e altre macchine#Macchine a registri). Quindi possiamo provare algoritmi che funzionano bene per lunghezza infinita.

Si utilizza una tecnica divide ed impera per moltiplicare assieme i due numeri. Quindi divido il numero in parte superiore e parte inferiore…

• Prima applicazione

  

  Ma si potrà notare che questo metodo non porta a migliroamenti

• Moltiplicazione più efficiente

  

Sottovettore di valore massimo

Questo è un problema classico che ho già riscontrato in maximum subarray sum.

Algoritmo banale

Va a guardare tutte le sottosequenze possibili, che sono O(N2) perché è uguale al numero di coppie di indici (ordinate) che si possono prendere.

Algoritmo Divide et Impera

Si nota che la massima sottosequenza è o nella parte destra o sinistra, oppure in mezzo, quindi si conside

<img src="/images/notes/image/universita/ex-notion/Tecniche algoritmiche/Untitled 5.png" alt="image/universita/ex-notion/Tecniche algoritmiche/Untitled 5">

Greedy

Greedy è buono quando si può Dimostrare (e se non lo dimostri perdi un sacco di tempo a implementare una soluzione che non è nemmeno giusta) e si basa sui sotto-problemi ottimali.

Problema del resto

In cui basta scegliere la moneta migliore ogni volta (perché sicuramente(con piccolo ragionamento) ci vorranno meno monete rispetto a usare altre)

Un osservazione è che può fallire in sistemi non CANONICI.

Job scheduling

Si avrà che basta ordinare secondo la lunghezza minore (perché si guadagna sempre in questo caso)

Huffman coding

Questo problema è stato trattato meglio in Kolmogorov complexity legati a cose come Entropy. Si crea un albero di codifica che sia il meno profondo possibile, in questo modo ho un modo più formale per giustificare il fatto di avere la minima codifica.

• Pseudocodice per l’albero di huffman.

  Huffman(real f[1..n], char c[1..n]) → Tree
  Q ← new MinPriorityQueue()
  integer i;
  for i ← 1 to n do
  	z ← new TreeNode(f[i], c[i]);
  	Q.insert(f[i], z);
  endfor
  for i ← 1 to n – 1 do
  	z1 ← Q.findMin(); Q.deleteMin();
  	z2 ← Q.findMin(); Q.deleteMin();
  	z ← new TreeNode(z1.f + z2.f, '');
  	z.left ← z1;
  	z.right ← z2;
  	Q.insert(z1.f + z2.f, z);
  endfor
  return Q.findMin();
  

Programmazione dinamica

Abbiamo risolto fibonacci, Maximum subarray sum con la programmazione dinamica, entrambi in O(n). Ora andiamo a parlare del problema più importante per la programmazione dinamica, il problema dello zaino

Knapsack problem

TODO

Distanza di levenstein

TODO

Seam Carving

TODO