Appunti di Strutture dati e algoritmi

Algoritmi e complessità

• 195.3.1 Analisi di quick sort
• 195.3.2 Valutazione complessità
• 205.4 Analisi finale
• Liste
• 236.1 L'ADT (Abstract Data Type) Lista
• 236.2 Rappresentazione concreta di lista
• 246.2.1 Statica
• 246.2.2 Rappresentazione collegata
• 246.2.3 Implementazione a vettori
• 256.3 Rappresentazione collegata mediante i puntatori
• 256.3.1 Funzione IsMember
• 256.3.2 Funzione Length
• 256.3.3 Funzione Append
• 286.4 Pila - Stack

• Coda - Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
• Alberi 297.1
• Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297.1.1
• Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . 297.1.2
• Proprietà delle relazioni . . . . . . . . . . . . . . . .
  • 347.4.1 Rappresentazione di un albero binario
  • 347.4.2 Costruzione delle primitive
  • 377.5 Alberi binari di ricerca
  • 377.5.1 Inserimento di un nuovo elemento
  • 387.5.2 Verifica della presenza di un elemento tramite ricerca binaria
  • 398.5.3 Eliminazione di un nodo
  • 408 Heap
  • 408.1 Coda di priorità
  • 408.2 Applicazioni della coda di priorità
  • 408.3 Struttura dati Heap
  • 418.3.1 Proprietà
  • 418.3.2 Operazioni fondamentali
  • 428.3.3 MoveUp
  • 428.3.4 MoveDown
  • 428.3.5 FindMin
  • 428.3.6 Insert
  • 428.3.7 Delete e DeleteMin
  • 428.3.8 Increase
  • 428.3.9 Decrease
  • 438.4 Heap binaria
  • 438.4.1 Implementazione delle procedure di supporto
  • 438.4.2 Costruzione heap binaria
  • 438.4.3 Coda di priorità
  • 438.4.4 Algorimo HeapSort
  • 529 Dizionari
  • 469.1 Definizione
  • 469.2 Implementazione con una lista
  • 469.2.1 Implementazione con lista ordinata
  Implementazione con BST . . . . . . . . . . . . . . . . . . . . . . 479.4 Implementazione con Heap . . . . . . . . . . . . . . . . . . . . . 4731 Ricorsione1.1 DefinizioneNella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono attraverso calcolabili funzioni di base e regole costruttive che usano la funzione stessa. La base teorica è il principio di induzione:
  • una proprietà vale per un certo numero naturale n₀, in altre parole è vera;P(n₀)
  • supponendo che P(n) sia vera, ne consegue che P(n + 1) è vera. Quindi possiamo dire che P(n) ⇒ P(n + 1).
  allora la proprietà vale ∀n ≥ n₀.Dato un programma, una funzione si può definire ricorsiva se invoca sé stessa direttamente o indirettamente (rispettivamente ericorsione diretta ricorsioneLa ricorsione si definisce quando vi è una sola chiamata indiretta).

  linearericorsiva all'interno della definizione della funzione stessa, viceversa si definiscericorsione nel caso in cui le chiamate ricorsive siano più di una.

  non lineare1.2 Caso base della ricorsione

  Una soluzione ricorsiva si pone come obiettivo quello di rappresentare il problema in termini di se stesso riducendo ad ogni ricorsione lo spazio delle soluzioni, fino a quando non si verificano una o più condizioni (o casi) che terminano il processo ricorsivo. Se queste condizioni vengono definite in maniera errata o affatto si genera una sequenza di chiamate ricorsive infinite che causerà problemi di stack overflow.

  Consideriamo il problema di calcolare il fattoriale dei primi numeri naturali.

  Nella specifica ricorsiva il problema può essere visto come il prodotto di due fattori: dove è noto e il fattoriale dei primi * * * * * · · · * -(1 2 3 4 5 (n 1)), n numeri è un

  Fattorialen{( == 1){// Caso basereturn 1;}// Ricorsionereturn * ( - 1);}}1.3 Validazione dell’inputOltre ad individuare i casi base è anche importante validare i valori di input.Riprendendo l’esempio del fattoriale di per definizione di fattoriale possiamon:calcolarlo solo per i numeri naturali (ovvero i numeri interi positivi), quindi solose Il caso va incluso all’interno del caso base (0! Pern >= 0. n = 0 = 1).gestire queste eventualità dobbiamo implementare una funzione ausiliaria (nonricorsiva) che si occupa della validazione dell’input e che una volta verificatoche questo sia corretto, chiama la funzione ricorsiva. Le funzioni non possonoavere lo stesso nome, quindi quello che faremo è aggiungere il suffisso allaReceffettiva implementazione

  ricorsiva:static unsigned long long FattorialeRec(int n) {
      // Caso base
      if (n == 0 || n == 1) {
          return 1;
      }
      // Ricorsione
      return FattorialeRec(n - 1) * n;
  }
  
  unsigned long long Fattoriale(int n) {
      // Validazione dell'input
      if (n < 0) {
          return 0;
      }
      // Implementazione ricorsiva
      return FattorialeRec(n);
  }
  
  Il valore di ritorno della funzione viene dichiarato cosicché
  FattorialeRec static
  rimanga accessibile solo a quel blocco (così non corriamo il rischio che il valore
  venga ritornato nella nostra funzione ).
  
  main
  1.4 Ricorsione diretta e indiretta
  Data una funzione ricorsiva questa si definisce se invoca la funzione
  diretta FooA
  direttamente all'interno del suo corpo.
  
  FooA
  //Ricorsione diretta
  int FooA(){
      //Fai qualcosa ...
      FooA();
      //Fai qualcosa ...
  }
  
  La funzione viene invece definita se invoca una seconda funzione
  indiretta FooB
  la qua a sua volta invoca, direttamente o indirettamente:
  FooA
  
  //Ricorsione indiretta
  int FooA(){
      //Fai qualcosa ...
      FooB();
      //Fai qualcosa ...
  }
  
  int FooB(){
      //Fai qualcosa
  

  ...FooA();//Fai qualcosa ...}

  1.5 Ricorsione di coda

  Una funzione ricorsiva si definisce (o ricorsione di coda) quando la chiamata ricorsiva è l'ultima istruzione eseguita dalla funzione prima di terminare; chiaramente solo la ricorsione lineare può essere tail. L'implementazione di FattorialeRec non è in quanto al termine della chiamata ricorsiva deve essere eseguito il prodotto tra il risultato ed n: FattorialeRec(n - 1)* n

  Una funzione ricorsiva computa "all'indietro": al passo i-esimo non è disponibile nulla e il risultato viene sintetizzato mentre le chiamate si chiudono. È quindi necessario conservare lo stato della computazione prima di fare la chiamata ricorsiva, perché servirà il ritorno. Per farlo occorre aggiungere un parametro ausiliario alla chiamata a funzione che tenga traccia del prodotto fino al passo corrente.

  static unsigned long long FattorialeRec(int n, int p)

  {// Caso base if (n == 0 || n == 1) { return p + 1; } // Ricorsione return FattorialeRec(n - 1, p * n); } unsigned long long Fattoriale(int n) { // Validazione dell'input if (n < 0) { return 0; } // Implementazione ricorsiva return FattorialeRec(n, 1); } È importante conoscere questo aspetto della ricorsione in quanto le funzioni tail possono essere facilmente ottimizzate dal compilatore: questo tipo di ottimizzazione è chiamata "tail call optimization" e permette di evitare l'accumulo di chiamate ricorsive nello stack, migliorando l'efficienza dell'algoritmo.