17 / 38
www.
edises
.it
Indice
XV
2.5.1 Algoritmi con struttura sequenziale..........................................................206
2.5.2 Algoritmi con struttura condizionale........................................................207
2.5.3 Algoritmi con struttura iterativa................................................................211
2.5.4 Le funzioni .................................................................................................217
2.5.5 Algoritmi con struttura ricorsiva ...............................................................218
2.6 Linguaggi di programmazione............................................................................. 220
2.7 Il linguaggio C ....................................................................................................... 223
2.7.1 Uso delle variabili.......................................................................................223
2.7.2 Uso degli operatori ....................................................................................224
2.7.3 Uso delle strutture di dati..........................................................................225
2.7.4 Sintassi generale e funzioni .......................................................................227
2.7.5 Codici con strutture sequenziali ...............................................................228
2.7.6 Codici con strutture condizionali e iterative ............................................230
2.8 Complessità computazionale................................................................................ 235
2.9 Verso una definizione formale di algoritmo........................................................ 240
2.9.1 Le funzioni computabili (calcolabili) .......................................................240
2.9.2 La macchina di Turing...............................................................................240
2.9.3 Esempio di macchina di Turing ................................................................242
2.9.4 Funzioni T–computabili e macchina di Turing universale......................245
2.10 Il calcolatore di Von Neumann ............................................................................ 246
2.11 Altre macchine per l’esecuzione di algoritmi ..................................................... 247
2.12 Funzioni ricorsive.................................................................................................. 248
2.12.1 Definizioni preliminari ..............................................................................248
2.12.2 Funzioni base..............................................................................................249
2.12.3 Composizione.............................................................................................249
2.12.4 Ricorsione...................................................................................................250
2.12.5 Funzioni ricorsive primitive.......................................................................250
2.12.6 Minimalizzazione .......................................................................................250
2.12.7 Funzioni ricorsive (funzioni ricorsive parziali) ........................................251
2.13 Tesi di Church ....................................................................................................... 251
2.14 Lo studio dei problemi risolvibili mediante un algoritmo ................................. 252
2.14.1 Insiemi, proprietà e problemi decidibili ..................................................252
2.14.2 Problemi semi-decidibili e insiemi effettivamente enumerabili .............254
2.14.3 Esempi di problemi decidibili e semi-decidibili.......................................257
2.14.4 Il problema della fermata di una macchina di Turing ............................259
2.14.5 La cardinalità degli algoritmi e dei problemi ..........................................260
Capitolo 3
- Insiemi, relazioni e funzioni
3.1 Concetti fondamentali .......................................................................................... 263
3.2 Relazione di inclusione......................................................................................... 264
3.3 Operazioni tra insiemi .......................................................................................... 265
3.4 Insieme delle parti ................................................................................................ 268
3.5 Coppia ordinata e prodotto cartesiano................................................................ 268
3.6 Relazione binaria................................................................................................... 269
3.7 Relazioni di equivalenza ....................................................................................... 271
3.8 Relazioni d’ordine largo ....................................................................................... 272