17 / 36
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