Informatica CdL in Matematica A.A. 2013/2014 Parte 3 Roberto Zunino L'uso della ricorsione in informatica Ricorsione    L'informatica è piena di nozioni definite ricorsivamente (o induttivamente) Ne vedremo alcune in questo corso Intanto, vogliamo imparare come ragionare su oggetti definiti in modo ricorsivo Esempi di Definizioni Ricorsive Esempio Esempio Esempio Esempio 7 4 5 4 2 Esempio Esempio Verso una Formalizzazione Verso una Formalizzazione Regole di Inferenza Regole di Inferenza Regole di Inferenza Regole di Inferenza Regole di Inferenza Notazione Esempio di Formalizzazione Esempio di Formalizzazione Esempio di Formalizzazione Esempio di Formalizzazione Punti fissi Teoremi di punto fisso Regole di Inferenza: Proprietà Fondamentali Monotonia Continuità (secondo Scott) Perché si chiama “continuità” Continuità: dimostrazione Continuità: dimostrazione Continuità e Finitezza Continuità e Monotonia Teoremi di Punto Fisso Knaster-Tarski Knaster-Tarski: dimostrazione Knaster-Tarski: dimostrazione Knaster-Tarski: conseguenza Principio di Induzione Principio di Induzione: Esempio Principio di Induzione: Esempio Principio di Induzione: Esempio Principio di Induzione: Esempio Operativamente Esempio operativo Esempio operativo Esempio operativo Esercizio Ancora sui punti fissi Iterate di una Funzione Th. del Punto Fisso di Kleene Th. Kleene: dimostrazione Th. Kleene: dimostrazione(2) Th. Kleene: dimostrazione(3) Th. Kleene: Esempi Th. Kleene: Esempi Derivazioni Derivazioni Derivazioni Derivazioni Derivazioni