Table of Contents Table of Contents
Previous Page  17 / 36 Next Page
Basic version Information
Show Menu
Previous Page 17 / 36 Next Page
Page Background

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