Fondamenti dell'informatica

Fondamenti di informatica

Indice

Cos’è 12 Insiemi 12 Cosa sono 12 Notazioni principali 12 Rappresentazione di un insieme 13 Rappresentazione estensionale 13 Rappresentazione intenzionale 13 Confronto tra gli insiemi 14 Uguaglianza 14 Inclusione 14 Proprietà di uguaglianza e inclusione 14 Riflessività 14 Transitività 14 Simmetria 14 Antisimmetria 14 Diagrammi di Eulero-Venn 15 Operazioni su insiemi 15 Unione 15 Intersezione 16 Differenza 16 Complemento 16 Uguaglianze e leggi 16 Dimostrazioni 17 Dimostrazione grafica 17 Dimostrazione discorsiva 17 Dimostrazione per sostituzione 18 Controesempio 19 Leggi per operatori su insiemi 19 Leggi per Unione e intersezione 19 Leggi che collegano Unione, intersezione e complemento 20 Legge per \ 20 Leggi importanti 20 Cardinalità di insiemi finiti 20 Insiemi di insiemi 21 Numeri naturali come insiemi 21 Insieme delle parti 21 Famiglie di insiemi 22 Partizioni 23 Paradosso di Russell 23 Prodotto cartesiano 23 Connettivi logici 24 I quantificatori 24 Relazioni 24 Rappresentazione grafica di relazioni 25 Tipi di relazione 25 Relazione completa 25 Relazioni su un insieme 25 Relazione identità 25 Relazioni su un insieme: prodotto cartesiano 26 Operazioni insiemistiche su relazioni 27 Leggi insiemistiche su relazioni 27 Composizione di relazioni 27 Leggi per composizione 29 Associatività: dimostrazione discorsiva 30 Relazione opposta 30 Leggi per relazione opposta 31 Leggi di distributività 31 Distributività: dimostrazione discorsiva 32 Proprietà di relazioni 32 4 proprietà 32 Relazioni totali 32 Relazioni univalenti 33 Relazioni surgettive 34 Relazioni iniettive 35 Quattro proprietà di relazioni 36 Risultati di dualità 36 Teorema di caratterizzazione 37 Dimostrazione R è totale se e solo se IdA R;Rop 37 ⊆ Lemmi e dimostrazione alternativa di IdA R; Rop R è totale 37 ⊆ ⇒ Dimostrazione R è surgettiva se e solo se IdB Rop; R 37 ⊆ Chiusura per composizione 37 Dimostrazione per sostituzione primo punto 38 Funzioni 38 Rappresentare funzioni 39 Funzioni in Analisi e informatica 40 Definizione di proprietà 40 Composizione di funzioni 41 Funzioni parziali, iniettive e suriettive 41 Biiezioni 41 Risultati di chiusura 42 Teorema di caratterizzazione per le biiezioni 42 Insiemi in biiezione 43 Proprietà di 44 ≅ Funzione caratteristica di un insieme 44 Sottoinsieme di una funzione 45 Relazioni con SQL 45 Triple, quadruple, n-uple 47 N-upla - Sequenze di lunghezza fissata 47 A* - Sequenze di lunghezza arbitraria 48 Induzione matematica 48 Insiemi infiniti e definizioni per induzione 48 Tre usi complementari dell’induzione 49 Definizione induttiva di un insieme A 49 Definizione induttiva di una funzione f : A → B 50 Il principio di induzione sui naturali 52 Dimostrazione per induzione formula di Gauss 53 Dimostrazione per induzione sequenze di lunghezza fissata 53 Fattoriale 53 Altri principi di induzione… 53 Sommatorie, produttorie, unioni e intersezioni n-arie 54 Sommatoria da 1 54 Definizione induttiva 55 Sommatoria da k 56 Definizione induttiva 56 Produttoria da k 57 Definizione induttiva 57 Unione n-aria 57 Definizione induttiva 57 Intersezione n-aria 57 Definizione induttiva 58 De Morgan n-ario 58 Dimostrazione induttiva 58 La sequenza di Fibonacci 58 Dimostrazione per induzione con sequenza di Fibonacci 59 Induzione forte 59 Relazioni su un insieme 60 Definizione 60 Notazione grafica 61 Proprietà 62 Riflessività 62 Simmetria 62 Transitività 63 Anti-simmetria 64 Teorema di caratterizzazione 65 Riflessività - Definizione teorema di caratterizzazione 66 Simmetria - Definizione teorema di caratterizzazione 66 Transitività - Definizione teorema di caratterizzazione 66 Antisimmetria - Definizione teorema di caratterizzazione 66 Chiusure 66 Chiusura riflessiva 67 Chiusura simmetrica 67 Chiusura transitiva 67 Composizione n-aria di relazione 70 Definizione chiusura transitiva 71 Chiusura riflessiva e transitiva - Stella di Kleene 72 Leggi stella di Kleene 72 Perché si chiamano chiusure? 73 Proposizione riflessiva 73 Proposizione simmetrica 73 Proposizione transitiva 73 Proposizione transitiva e riflessiva 73 Relazioni di equivalenza 74 Classe di equivalenza 74 Teorema di biiezione 74 Relazioni di ordinamento parziale 75 Relazioni di ordinamento 76 Grafi 77 Grafi orientati 77 Vicinato e grado dei nodi 78 Nodi adiacenti 78 Vicinato in uscita 79 Vicinato in ingresso 79 Grado di uscita 80 Grado di ingresso 80 Grafi come relazioni e proprietà TUSI 81 Handshaking Lemma per grafi orientati 81 Dimostrazione per induzione su |E| N 82 ∈ Rappresentazioni alternative grafi 82 Rappresentazione con matrici di adiacenza 82 Rappresentazione con liste di adiacenza 83 Grafi etichettati e pesati 84 Cammino, walk, trail, path, cicli, … 84 3 tipi di cammini 85 Dimostrazione per induzione walk e potenze di relazioni 87 Da walk a trail, da trail a path 87 3 tipi di cicli 88 Connettività 88 Grafo fortemente connesso 88 Componente fortemente connessa 89 Componenti connesse e partizioni 90 Altre proprietà 91 Grafi orientati aciclici (DAGs - Directed Acyclic Graphs) 91 Ordinamento topologico di un DAG 93 Esistenza ordinamento topologico 93 Dimostrazione per induzione 93 Grafi non orientati 93 Grafo orientato associato a un grafo non orientato 94 Vicinato, grado dei nodi e handshaking lemma 95 Rappresentazione grafi non orientati 95 Cammino, walk, trail, path, cicli, … 95 Walk, trail e path in grafi non orientati 96 Cicli 96 Connettività 96 Cammini e cicli Euleriani 97 Teorema di Eulero 98 Dimostrazione Solo se 98 Dimostrazione Se 98 Cicli e path hamiltoniani 99 Il problema del commesso viaggiatore 100 Alberi 101 Terminologia 102 Proprietà 102 Alberi radicati 104 Terminologia 105 Alberi ordinali e cardinali 108 Distanze 109 Cos’è una distanza? 109 Distanza su grafo non orientato 110 Distanza ricorsivamente 110 Distanza su grafi orientati 111 Diametro, altezza, profondità 112 Diametro 112 Profondità 112 Altezza di un nodo 112 Altezza dell’albero 113 Isomorfismo di grafi 113 Grafi notevoli 115 Calcolo combinatorio 115 Cardinalità 116 Lemma X 116 Dimostrazione per assurdo 117 Cardinalità di operazioni su insiemi 117 Intersezione, divisione e unito 117 Principio di Inclusione-Esclusione 118 Unione di tre insiemi 118 Principio 118 Cardinalità del prodotto cartesiano 119 Cardinalità del prodotto cartesiano generalizzata 119 Corollario |An| = |A|n 120 Cardinalità delle relazioni 120 Proprietà TUSI 120 Il principio delle buche e dei piccioni (pigeonhole principle) 121 Dimostrazione 121 La regola di biiezione 121 Opposto della regola di biiezione 121 Cardinalità dell’insieme delle parti - Funzione tra A e Bool - L’insieme delle relazioni 122 Permutazioni, disposizioni e combinazioni 122 Permutazioni 122 Cosa sono? 122 Dimostrazione definizione alternativa 122 Contare le permutazioni 123 Dimostrazione valenza |A| = |B| allora |Perm(A)| = |Perm(B)| 123 Cardinalità delle biiezioni tra due insiemi - Utilizzo permutazioni 124 Dimostrazione cardinalità delle biiezioni tra due insiemi 124 Permutazioni con ripetizioni di una sequenza 124 Contare le permutazioni con ripetizioni 125 Disposizioni 126 Cosa sono? 126 Contare le disposizioni 126 Altri modi per contare le disposizioni / Giustificazioni della formula 126 Combinazioni 127 Cosa sono? 127 Contare le combinazioni 128 Altri modi per contare le combinazioni/ Giustificazioni della formula 128 Cardinalità sfruttando regola di biiezione 129 Approfondimento 129 Contare su alberi, grafi e archi, path, ecc. 130 Contare sugli alberi 130 Numero nodi e altezza albero radicato 130 Massima distanza possibile tra due nodi x, y 131 Contare sugli alberi binari 131 Piccola revisione sugli alberi binari 131 Numero nodi, foglie e nodi interni 132 Altezza minima di un albero binario 133 Nodo unario / nodi interni 134 Contare sui grafi 134 Grafi non orientati 134 Metodo 1 135 Metodo 2 136 Confronto tra i due metodi - Triangolo di Tartaglia 136 Tramite matrice di adiacenza 137 Grafi orientati 138 Tramite matrice di adiacenza 138 Numero grafi non isomorfi 138 Complemento di un grafo non orientato 139 La relazione complemento 140 Complemento esteso classi di isomorfismo 140 Contare numeri di archi, path, cicli in grafi 141 Shortest path 141 Cricca di n nodi - Contiamo path di un certo tipo esistono in un grafo di un certo tipo 142 Path in una cricca Kn 142 Grafi bipartiti 143 Paths in un grafo bipartito completo Kn,n 144 Paths in un grafo bipartito completo Kn,m con n ≠ m 144 Induzione strutturale 145 Liste 145 Liste VS insiemi 145 Definizione induttivamente 146 Operazioni su liste 146 Principio di induzione su liste 148 Alcune proprietà delle operazioni su liste 148 Dimostrazione prima proprietà 148 Dimostrazione seconda proprietà 148 Dimostrazione terza proprietà 148 Alberi binari 149 Definizione induttiva 149 Rappresentazione grafica della definizione induttiva 150 Operazioni strutturali su alberi binari 150 Principio di induzione su alberi binari 151 Alberi etichettati 151 Definizione induttiva 151 Rappresentazione grafica 151 Operazioni su alberi etichettati 152 Il principio di induzione su alberi binari etichettati 153 Principio di induzione strutturale generale 153 Segnatura 154 Termine per una segnatura 154 Rappresentazione grafica di termini 155 Segnatura BT: alberi binari come termini 155 Segnatura LA: liste come termini 155 Segnatura N: i naturali come termini 156 Funzioni sui termini 156 Funzione val 156 Somma di N-termini 156 Principio di induzione strutturale 156 Correttezza del principio di induzione strutturale 157 Altri principi di induzione come casi particolari 157 Ricorsione 157 Cos’è 157 Definizioni ricorsive di funzioni 159 Relazione associata a una definizione ricorsiva 160 Come capire se una definizione è ben data o non ben data 160 Definizione non ben data 160 Definizione ben data 160 Relazione di precedenza indotta da una definizione ricorsiva 161 Relazioni ben fondate 162 Proprietà di relazioni ben fondate 162 Conclusioni 162 Perché le funzioni induttive sono ben date? 163 Tipi di ricorsione 165 Linguaggi formali 166 Introduzione 166 Linguaggio, alfabeto e stringhe 167 Definire un linguaggio 167 Definizioni 167 Alfabeto 167 Stringhe (o parole) su un alfabeto A 168 Linguaggio su A 168 Ordinamento lessicografico 168 Definire i linguaggi 169 Automi 169 La base degli automi 169 Definizione formale 170 Raggiungibilità 170 Linguaggio accettato da uno stato 172 Automi deterministici e non deterministici 172 Automa deterministico 172 Automa non deterministico 173 Verso la costruzione dei sottoinsiemi 173 Grammatiche libere da contesto 173 Definizione di grammatica 174 BNF 174 Produzione frasi 175 Albero di derivazione sintattica (parse tree) 175 Linguaggio generato da un non terminale 176 Grammatica per un dato linguaggio 177 Esempi grammatiche 178 Ambiguità di grammatiche 178 Stringhe con più alberi di derivazione 179 Definizione 179 Confronto tra automi e grammatiche 180 Estrazione di una grammatica da un automa 180 Estrarre un automa a una grammatica 180 La gerarchia di Chomsky 181 Logica 182 Che cos’è 182 Logica matematica e informatica 183 Usi della LM in informatica 183 Valori di verità 183 Proposizioni 183 Calcolo proposizionale 183 Obiettivo del calcolo proposizionale 184 Sintassi 184 Formule proposizionali 184 Sintassi delle formule proposizionali 184 Formalizziamo proposizioni strutturate 185 Semantica del calcolo proposizionale 186 Interpretazione 186 Connettivi logici come funzioni su booleani e le tavole di verità 186 Definizione induttiva 187 Modelli, equivalenza e conseguenza logica 188 Modello 188 Logicamente equivalente 188 Conseguenza logica 188 Ambiguità del calcolo proposizionale 188 Gestione dell’ambiguità 188 Tavole di verità 189 Creare le tavole di verità 189 Tautologie 190 Definizioni 190 Tautologie 190 Contraddizione 190 Formula soddisfacibile 190 Classificazione di formule finale 190 Come si vede se una formula è (o non è) soddisfacibile, una contraddizione, una tautologia? 190 Dimostrazione per sostituzione 191 Rimpiazzamento 192 Principio di sostituzione 192 Leggi 192 Dimostrazione effettiva 192 Leggi disponibili 193 Altre leggi 194 Dimostrazione complemento 195 Dimostrazione assorbimento 195 Dimostrazione contronominale 195 Dimostrazione Modus Ponens 195 Dimostrazione per simil-complemento 195 I sistemi di dimostrazione 196 Dimostrare una conseguenza logica 196 Sistemi di dimostrazioni (proof systems) 196 Definizione 197 Dimostrazione tramite proof system R di una formula Q in Δ da un insieme di premesse 197 Correttezza e completezza di un proof system 197 Internalizzare concetti semantici con tautologie 198 Dimostrazione 199 Proof system per calcolo proposizionale 199 Correttezza del proof system per il calcolo proposizionale 199 Dimostrazione per induzione sulla lunghezza della dimostrazione 199 Dimostrazione per sostituzione e dimostrazione completa del completamento 200 Tautologie come premesse 200 Dimostrazione 200 Tecniche di dimostrazione 200 Dimostrazione diretta e con ipotesi non tautologiche 201 Dimostrazione per assurdo 201 Dimostrazione per contrapposizione 201 La logica dei predicati 202 Introduzione 202 Quantificatori 202 Sintassi 203 Alfabeti del primo ordine 203 Sintassi della logica dei predicati 203 Ambiguità 204 Formalizzazione di frasi 205 Semantica 207 Variabili 207 Campo d’azione 207 Variabile legata o libera 207 Formula chiusa e aperta 208 Esempi formule quantificate 208 Interpretazioni: dare significato ai simboli 209 Assegnamenti 210 Modelli, equivalenza e conseguenza logica 210 Modello 210 Logicamente equivalente 210 Conseguenza logica 211 Semantica dei termini 211 Semantica delle formule 211 Atomiche e dei predicati 211 Altre 212 Formule valide 213 Classificazione di formule della logica dei predicati 213 Dimostrazione per sostituzione di formule valide 213 Leggi per quantificatori 213 Dimostrazione distributività 214 Dimostrazione di formule non valide 214 Formalizzazione di concetti precedenti 215 Dimostrazione inclusione stretta 215 Dimostrazione A B 215 ⊄

Cos’è

All’interno di Fondamenti di informatica sono presenti i seguenti argomenti:

• Linguaggio matematico di base
• Insiemi
• Relazioni
• …
• Strutture discrete
• Coppie
• N-uple
• …
• Tecniche per contare
• Combinatoria
• Permutazioni
• …
• Tecniche di dimostrazione
• Simboliche
• Discorsive
• …
• Specifiche formali
• Linguaggi formali
• Logica
• Ricorsione

Insiemi

Cosa sono

Un insieme è una collezione di oggetti, chiamati elementi.

Esempio: Numeri interi, naturali, reali, …

Gli insiemi possono essere di qualsiasi tipo: oggetti, persone, entità matematiche astratte, …

Notazioni principali

• A,B,C,… denotano insiemi generali, a differenza dei casi che presentano dei nomi particolari
• a,b,c,… denotano elementi
• a ∈ A a appartiene ad A
• a ∉ A a non appartiene ad A

Esempio:

• N, i numeri naturali
• Z, i numeri interi
• Q, i numeri razionali
• R, i numeri reali
• EU, insieme esseri umani
• S, studenti unici
• SFDI, studenti corso FDI
• U, insieme universo, contiene tutti gli elementi che possono esistere

Quando si definisce un insieme ci deve essere una base dietro; ci deve essere una proprietà che permette di discriminare.

Esempio: Insieme di tutte le persone alte della stanza

Rappresentazione di un insieme

Rappresentazione estensionale

Dare una lista certa per enumerazione; degli insiemi definiti per enumerazione, ovvero si elencano gli elementi.

Esempio: Ore del giorno {0,1,2,3,4,5…,23}

Bool {true,false}

L’insieme vuoto {} ∅

Rappresentazione intenzionale

Basata su insiemi definiti per proprietà.

Esempio: X={x ∈ A | P(x)}

L’insieme X contiene tutti e soli gli elementi d