Appunti per I corsi di "Programmazione" e "Algoritmi e Strutture Dati" 1° anno Laurea in Informatica



Scaricare 290.5 Kb.
Pagina1/11
01.06.2018
Dimensione del file290.5 Kb.
  1   2   3   4   5   6   7   8   9   10   11


Appunti per i corsi di

"Programmazione" e "Algoritmi e Strutture Dati"

1° anno - Laurea in Informatica

a.a. 2001/02

(prof. Gerardo COSTA - prof. Enrico PUPPO)

2a Puntata -- Parte A

Procedure ricorsive

Tipi di dato
( Sezioni da 1 a 8 )
(Versione: Maggio 1999 -- Revisione: Febbraio 2002)

Si prega di segnalare errori, punti oscuri,....

Indice

1 Induzione Aritmetica 3

1.1 Principio di induzione aritmetica "a passi" 3

1.2 Dimostrazioni per induzione aritmetica "a passi" 4

1.3 Induzione aritmetica "generalizzata" 4

1.4 Coefficienti binomiali 5

2 Procedure e funzioni ricorsive 7

2.1 Il fattoriale 7

2.2 Coefficienti binomiali 7

2.3 Un primo esempio di procedura ricorsiva 9

2.4 Ricerca binaria 11

2.5 Merge sort 13

2.6 Ricorsione indiretta e incrociata 21

2.7 Quando usare la ricorsione 21

3 Tipi, tipi di dato, strutture dati : generalità e primi esempi. 23

3.1 Booleani 23

3.2 Interi 24

4 Funzioni parziali 25

5 Algebre eterogenee (many sorted) 26

6 Le successioni 29

6.1 Successioni ed operazioni su di esse 29

6.2 Le stringhe 31

6.3 Gli stack 32

6.4 Le code 33

7 Implementazione delle successioni 34

7.1 Implementazione con array 34

7.2 Implementazione con liste dinamiche 39

7.3 Confronto tra le due implementazioni 42

8 Tipi di dato astratti e concreti, strutture dati 44

8.1 Ricapitolando ... 44

8.2 Implementazione di un tipo di dato (solo uno schema) 44





1Induzione Aritmetica

Induzione, induzione aritmetica, principio di induzione, dimostrazioni per induzione,.....

Cerchiamo di chiarire un po' la faccenda, vedendo: il principio di induzione aritmetica (nella versione "a passi"), poi le dimostrazioni per induzione che si fondano su questo principio, infine l'induzione aritmetica "generalizzata". Più avanti vedremo le definizioni induttive.

L'argomento verrà ripreso nei corsi degli anni successivi dando al tutto un'impostazione uniforme e più rigorosa.

Indichiamo con Z l'insieme degli interi e con N l'insieme dei naturali.

1.1Principio di induzione aritmetica "a passi"


I.1. Formulazione tratta dalle dispense di Algebra.

Sia P una affermazione sui numeri interi e c un intero. Se



allora P è vera per ogni numero intero k ≥ c.

Note.

  • Spesso, invece di affermazione sui numeri interi, si dice proprietà dei numeri interi (vedere anche oltre).

  • Il passo è chiamato passo induttivo.

  • Spesso il passo induttivo si formula in modo alternativo:

per ogni n, n ≥ c: se P è vera per n, allora P è vera per n+1

(lo stesso vale, sotto, in I.2 e I.3)



I.2. Formulazione usando funzioni.

Consideriamo una funzione Pf : Z {vero, falso} e sia c un intero. Se:



  • base Pf(c) = vero

  • passo per ogni intero n, n>c Pf(n-1) = vero implica Pf(n) = vero

allora Pf(k) = vero, per ogni numero intero k ≥ c.

I.3. Formulazione usando insiemi

Sia Ps un sottinsieme di Z e sia c un intero. Se:



  • base c  Ps

  • passo per ogni intero n, n > c: n-1  Ps implica n  Ps

allora: k  Ps, per ogni numero intero k ≥ c.

I.4. Collegamenti

Il collegamento tra la versione con funzioni e quella con insiemi è semplice:



  • data Pf si considera l'insieme Ps = { x  Z | Pf(x) = vero}; allora si vede che la versione con Ps è solo una traduzione di quella con Pf;

  • nell'altro senso, dato Ps basta considerare la funzione Pf t.c. Pf(x)=vero sse x  Ps.

Quindi le formulazioni in I.2 ed I.3 sono equivalenti.

Il collegamento con la prima versione (quella in termini di affermazioni o proprietà) si ha osservando che uno dei modi più semplici di precisare il concetto di "proprietà" è quello di far ricorso ai sottinsiemi (o a funzioni come Pf). Una proprietà è completamente caratterizzata dall'insieme degli oggetti/elementi che godono della proprietà stessa; quindi, ad esempio, la proprietà di essere numero primo equivale ad appartenere all'insieme dei primi.

Quindi I.2 ed I.3 sono solamente un modo di precisare I.1.

Di fatto, tutte e tre le formulazioni sono usate, quindi è utile conoscerle e saper passare da una all'altra.


1.2Dimostrazioni per induzione aritmetica "a passi"


Abbiamo visto il principio di induzione (aritmetica "a passi"). Su questo principio si fondano le dimostrazioni per induzione (aritmetica "a passi"), che hanno lo schema seguente.

Voglio dimostrare:



Tesi tutti gli interi k ≥ c hanno la proprietà P

Allora :


  • base dimostro che c ha la proprietà P;

  • passo supponendo che n-1 abbia la proprietà P [questa è l'ipotesi induttiva]

dimostro che anche n ha la proprietà P.

In base al principio di induzione, questa dimostrazione funziona!



Esempi: altre a quelli visti (o che si vedranno) nei corsi di matematica e di informatica, qui sotto c'è un esempio collegato ai coefficienti binomiali.

1.3Induzione aritmetica "generalizzata"


Diamo l'enunciato del principio utilizzando le funzioni (le altre formulazioni e lo schema di dimostrazione si ricavano per analogia con quanto visto sopra - un utile esercizio).

Consideriamo quindi Pf : Z {vero, falso} ed un intero c.

Se:

• base Pf(c) = vero



• passo per ogni n > c : ( Pf(i) = vero per ogni i, c ≤ i < n ) implica Pf(n) = vero

allora Pf(k) = vero, per ogni numero intero k ≥ c.



Esempi: un esempio di dimostrazione per induzione generalizzata è la dimostrazione di correttezza dell’algoritmo merge sort, per ordinare un array, che vedremo.

Nota 1.

L'induzione generalizzata estende quella a passi; dal punto di vista delle dimostrazioni: ogni dimostrazione per induzione a passi è anche una dimostrazione per induzione generalizzata; non è vero il contrario.



Nota 2.

E' possibile una formulazione più compatta, che riunisce le due condizioni (base e passo) in una sola:

se: [*] per ogni n ≥ c : (Pf(i) = vero per ogni i, c ≤ i < n) implica Pf(n) = vero

allora Pf(k) = vero, per ogni numero intero k ≥ c.

Si osservi che [*] è quasi uguale al passo, ma con "n ≥ c " al posto di "n > c ".

I casi in cui n>c corrispondono al passo, mentre il caso n=c corrisponde alla base, anche perché, per n=c:



  • non esistono i t.c. c ≤ i < n; dunque: (Pf(i) = vero per ogni i, c ≤ i < n) è vero

  • "vero implica bla-bla" equivale a "bla-bla" , che in questo caso è "Pf(c)= vero".





Condividi con i tuoi amici:
  1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale