- 1 Introduzione alla programmazione degli elaboratori 1
1.1 Definizionidibasedell’informatica ................................. 1 1.2 Cennidistoriadell’informatica ................................... 1 1.3 Elementidiarchitetturadeglielaboratori ............................. 3 1.4 Elementidisistemioperativi .................................... 5 1.5 Elementidilinguaggidiprogrammazioneecompilatori. . . . . . . . . . . . . . . . . . . . . . 5 1.6 Unametodologiadisvilupposoftware“inthesmall” ....................... 7
- 2 Programmazione procedurale: il linguaggio ANSI C 9
2.1 CennidistoriadelC......................................... 9 2.2 Formatodiunprogrammaconunasingolafunzione ....................... 10 2.3 Inclusionedilibreria ......................................... 11 2.4 Funzionemain............................................ 11 2.5 Identificatori ............................................. 11 2.6 Tipididatipredefiniti:int,double,char............................. 12 2.7 Funzionidilibreriaperl’input/outputinterattivo......................... 12 2.8 Funzionidilibreriaperl’input/outputtramitefile ........................ 14
3.1 Definizionedicostantesimbolica .................................. 17 3.2 Dichiarazionedivariabile ...................................... 17 3.3 Operatoriaritmetici ......................................... 17 3.4 Operatorirelazionali ......................................... 18 3.5 Operatorilogici............................................ 18 3.6 Operatorecondizionale........................................ 19 3.7 Operatoridiassegnamento...................................... 19 3.8 Operatoridiincremento/decremento ................................ 19 3.9 Operatorevirgola........................................... 20 3.10Tipodelleespressioni......................................... 20 3.11Precedenzaeassociativit`adeglioperatori ............................. 21
4 Istruzioni 25
4.1 Istruzionediassegnamento ..................................... 25 4.2 Istruzionecomposta ......................................... 25 4.3 Istruzionidiselezione:if,switch................................. 25 4.4 Istruzionidiripetizione:while,for,do-while .......................... 30 4.5 Istruzionegoto............................................ 34 4.6 Teoremafondamentaledellaprogrammazionestrutturata . . . . . . . . . . . . . . . . . . . . 35
iv INDICE
- 5 Procedure 37
5.1 Formatodiunprogrammaconpiu`funzionisusingolofile . . . . . . . . . . . . . . . . . . . . 37 5.2 Dichiarazionedifunzione ...................................... 37 5.3 Definizionedifunzioneeparametriformali ............................ 38 5.4 Invocazionedifunzioneeparametrie↵ettivi............................ 38 5.5 Istruzionereturn........................................... 38 5.6 Parametrierisultatodellafunzionemain.............................. 39 5.7 Passaggiodiparametripervaloreeperindirizzo ......................... 39 5.8 Funzioniricorsive........................................... 44 5.9 Modellodiesecuzionesequenzialebasatosupila ......................... 47 5.10Formatodiunprogrammaconpiu`funzionisupiu`file ...................... 48 5.11Visibilit`adegliidentificatorilocalienonlocali........................... 50
- 6 Tipi di dati 51
6.1 Classificazionedeitipididatieoperatoresizeof......................... 51 6.2 Tipoint:rappresentazioneevarianti ............................... 51 6.3 Tipodouble:rappresentazioneevarianti ............................. 52 6.4 Funzionidilibreriamatematica................................... 52 6.5 Tipochar:rappresentazioneefunzionidilibreria......................... 53 6.6 Tipienumerati ............................................ 54 6.7 Conversioniditipoeoperatoredicast ............................... 55 6.8 Array:rappresentazioneeoperatorediindicizzazione....................... 56 6.9 Stringhe:rappresentazioneefunzionidilibreria.......................... 61 6.10Struttureeunioni:rappresentazioneeoperatorepunto...................... 63 6.11Puntatori
peratoriefunzionidilibreria ............................. 67
- 7 Correttezza di programmi procedurali 73
7.1 TriplediHoare............................................ 73 7.2 Determinazionedellaprecondizionepiu`debole .......................... 73 7.3 Verificadellacorrettezzadiprogrammiproceduraliiterativi . . . . . . . . . . . . . . . . . . . 75 7.4 Verificadellacorrettezzadiprogrammiproceduraliricorsivi . . . . . . . . . . . . . . . . . . . 77
- 8 Introduzione alla logica matematica 81
8.1 Cennidistoriadellalogica...................................... 81 8.2 Elementiditeoriadegliinsiemi ................................... 84 8.3 Relazioni,funzionieoperazioni ................................... 86 8.4 Principiodiinduzione ........................................ 88
- 9 Logica proposizionale 91
9.1 Sintassidellalogicaproposizionale ................................. 91 9.2 Semanticaedecidibilit`adellalogicaproposizionale ........................ 93 9.3 Conseguenzaedequivalenzanellalogicaproposizionale . . . . . . . . . . . . . . . . . . . . . . 97 9.4 Propriet`aalgebrichedeiconnettivilogici.............................. 99 9.5 Sistemideduttiviperlalogicaproposizionale ........................... 101
10.1Sintassidellalogicadeipredicati ..................................105 10.2 Semantica e indecidibilit`a della logica dei predicati . . . . . . . . . . . . . . . . . . . . . . . . 109 10.3 Conseguenzaedequivalenzanellalogicadeipredicati. . . . . . . . . . . . . . . . . . . . . . . 112 10.4Propriet`aalgebrichedeiquantificatori ...............................114 10.5Sistemideduttiviperlalogicadeipredicati ............................115
INDICE v
11 Programmazione logica: il linguaggio Prolog 117
11.1Formenormaliperformulelogiche .................................117 11.2 Teoria di Herbrand e algoritmo di refutazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11.3RisoluzionediRobinsonperlalogicaproposizionale .......................123 11.4 Unificazioneerisoluzioneperlalogicadeipredicati. . . . . . . . . . . . . . . . . . . . . . . . 127 11.5 Prolog: clausole di Horn e strategia di risoluzione SLD . . . . . . . . . . . . . . . . . . . . . . 132 11.6 Prolog: termini e predicati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 11.7 Prolog: input/output, taglio e negazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
12 Attivit`a di laboratorio in Linux 145
12.1 Cenni di storia di Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 12.2GestionedeifileinLinux ......................................145 12.3 L’editor gvim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.4 Il compilatore gcc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 12.5 L’utility di manutenzione make . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 12.6 Il debugger gdb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 12.7 ImplementazionedeiprogrammiCintrodottialezione . . . . . . . . . . . . . . . . . . . . . . 156 12.8 Il compilatore/interprete gprolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 12.9 ImplementazionedeiprogrammiPrologintrodottialezione . . . . . . . . . . . . . . . . . . . 157