Fondamenti Teorici e Programmazione - Modulo B

Modulo B - Metodi Formali per l'Informatica - Fondamenti Teorici

Programma del corso:

1. Fondamenti di Strutture Dati
   • Insiemi
   • Relazioni e Funzioni
   • Alberi, Grafi (picchiere insiemi di valori e come sfruttarli) - es. to insieme di profili, archi reti
2. Logica
   • Formali che permettono di rappresentare dati (linguaggio molto preciso)
   • Importante: pone problema da risolvere
   • Esempio: SORT(N) = SORT(A) ≤ N AND SORT(N+1) = SORT(N +1)(N+1)
   • AND è proprietà che deve valere per entrambi
3. Linguaggi Formali e Automi
   • Funzione: trovare formalismi per definire linguaggi
   • Linguaggi formali indispensabili per programmare le macchine
   • Automi formalismi che permettono di riconoscere il calcolo
   • Deterministicizzazione e Nondeterministicizzazione

Programma corso 2014 D. Ochslieter - Modulo B

• Ragionamento formale
• Quantificatori e nomi simbidici
• Implicazione
• Equivalenza
• Dimostrazione per assurde
• Controesempi per induzione

Linguaggi di programmazione: Stringhe ed insiemi di stringhe

Grammatiche (Reggehn):

• Leser
• Ambiguità grammaticale
• Alberi di derivazione sintattica

Cenni su Calcolabilità

• Problemi che i calcolatori non possono risolvere
• Problemi intrattolabili

Parte comune ai 2 Moduli

Richiami di Matematica: Insiemi, Algebra di Boole, Relazioni, Funzioni

Introduzione all'Informatica

• Concetti di base di Armen et al. "Introduzione degli Algoritmi", Jackson Libri CAP15
• Linguaggi formali e automi, Dino Perdineschi "Elementi di Sintassi dei Linguaggi di Programmazione"

Passeword per focode: Automa

Modulo B - Metodi Formali per l'Informatica - Fondamenti Teorici

Programma del corso

1. Fondamenti di Strutture Dati

   • Insiemi
   • Relazioni e Funzioni
   • Alberi, Grafi (Piacevoli Insiemi di Dati e Loro Struttura) - es. TSI, Insieme di Profili, Uni Network

2. Logica

   • Concetti che permettono di rappresentare dati (Linguaggio Molto Preciso)
   • Informatica pone problema da risolvere
   • Es.: Sort(n) = Sort(n)₁ ≤ n _n and Sort(n-1)_n+1 = Sort(n+1)_n
   • AND e proprietà che deve valere per entrambe

3. Linguaggi Formali e Automi

   • Funzione: Trovare formalismi per definire linguaggi
   • Linguaggi formali - Indispensabili per programmare le macchine
   • Automi - Formalismi che permettono di riconoscere al calcolo
   • Deterministici e non deterministici

Programma corso 2014 Docchiutor + Hocus B

Ragionamento Formale

• Quantificatori e nomi simbolici
• Implicazione
• Equivalenza
• Dimostrazione per assurdo
• Controesempi ed induzione

Linguaggi di Programmazione: Stringhe ed Insiemi di Stringhe

Grammatiche

• Regole
• Asser
• Ambiguità grammatica
• Alberi di derivazione sintattica

Cenni su Calcolabilità

• Problema che i calcolatori non possano risolvere
• Problemi Intralabilità

Parte comune a 2 Moduli

Richiami di Matematica: Insiemi, Algebra di Boole, Relazioni, Funzioni

Introduzione all'Informatica

Concetti di Base Corren ed al. "Introduzione degli algoritmi", Jackson libri CAP 15

Linguaggi Formali e Automi, Dino Pedreschi "Elementi di Sintassi dei Linguaggi di Programma"

Passeuvroi x Toole: Automa

Ricevimenti: Mercoledì 16-18

TEORIA DEGLI INSIEMI

(FONDAMENTI DI STRUTTURE DATI)

INSIEME: COLLEZIONE DI ELEMENTI DISTINGUIBILI (PIÙ DI DUE ELEMENTI)

APPARTENENZA: x ∈ S

• x ∉ S

• SI LEGGE: x elemento di S, x ∉ S, x appartiene a S
• x ← variabile: elemento o associazioni valore o simbolo
• S ← variabile: insieme di {x} o collezione

RAPPRESENTAZIONE ESTENSIONALE (IN EXTENSO)

DESCRIVO INSIEME ATTRAVERSO ESPLICITO ELENCO DEI SOLI ELEMENTI SCRITTI

TRA PARENTESI GRAFFE, (VALE SOLO PER INSIEMI FINITI)

• Es: S = {1, 2, 3}

Elemen