Anno di corso: 1

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale

Anno di corso: 2

Anno di corso: 3

Crediti: 8
Crediti: 8
Crediti: 16
Tipo: A scelta dello studente
Crediti: 4
Tipo: Lingua/Prova Finale
Crediti: 13
Tipo: Altro

FONDAMENTI DELL'INFORMATICA

Scheda dell'insegnamento

Anno accademico di regolamento: 
2014/2015
Anno di corso: 
1
Anno accademico di erogazione: 
2014/2015
Tipo di attività: 
Obbligatorio
Crediti: 
8
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
66
Prerequisiti: 

Conoscenze matematiche di base apprese durante la scuola superiore.

Moduli

Metodi di valutazione

Modalita' di verifica dell'apprendimento: 

Esame finale
Tipo esame: scritto e orale separati

Valutazione: 
Voto Finale

Obiettivi formativi

Scopo del Corso è quello di fornire, insieme a un linguaggio formale, le basi teoriche, gli strumenti e le tecniche che rappresentano i fondamenti matematici dell’informatica. Gli argomenti che verranno trattati hanno lo scopo di mettere lo studente in grado di acquisire livelli di astrazione necessari alla comprensione delle basi teoriche e computazionali dell’informatica mediante l’apprendimento di nozioni formali indispensabili per affrontare e padroneggiare livelli di complessità superiore caratteristici dell’iter disciplinare scelto.

Contenuti

Il corso prevede l’insegnamento introduttivo agli strumenti matematico formali che sono alla base dell’informatica teorica, che comprende l’acquisizione di un linguaggio formale di base (insiemi, funzioni e relazioni), di strumenti di concettualizzazione astratti (grafi, alberi e strutture algebriche) e nozioni basilari della logica matematica (proposizionale e predicativa).

Programma esteso

1 Insiemi (definizioni estensionali e intensionali, sottoinsiemi e insiemi potenza, unione, intersezione, complementazione, differenza e differenza simmetrica, partizioni, prodotto cartesiano, sequenze, coppie e n-uple ordinate, relazioni, funzioni e operazioni, funzione inversa, composizione di funzioni, cardinalità degli insiemi, tecnica di diagonalizzazione, multinsiemi, insiemi quoziente e classi di resto modulo n, cenni di analisi combinatoria)

2 Strutture relazionali, grafi e ordinamenti (proprietà delle relazioni, tabelle e matrici booleane e relative operazioni, grafi, relazioni d’equivalenza, composizione di relazioni, strutture relazionali e ordinamenti, algebra relazionale, chiusura transitiva, ordinali e reticoli, funzioni monotone su insiemi ordinati, teorema del punto fisso)

3 Algebra di Boole (semigruppi, monoidi e gruppi, congruenze e quozienti, omomorfismi e isomorfismi, algebra booleana)

4 Introduzione all’induzione (principi d’induzione matematica, induzione e ricorsione su insiemi, stringhe, formule ben formate)

5 Logica: linguaggi proposizionali (linguaggio e semantica, apparato deduttivo, sintassi e semantica della logica proposizionale, equivalenza logica, modelli, decidibilità, completezza di insiemi di connettivi)

6 Logica: sistemi deduttivi proposizionali (tavole di verità, tableaux proposizionali, completezza e correttezza, calcolo della deduzione naturale)

7 Logica: linguaggi predicativi (sintassi della logica predicativa, variabili libere e legate, interpretazioni e modelli, equivalenza semantica, connettivi e operatori insiemistici, teorie del primo ordine)

8 Logica: sistemi deduttivi predicativi (tableaux per la logica predicativa, completezza e correttezza nel calcolo predicativo, accenni di calcolo della deduzione naturale)

Bibliografia consigliata

Luigia Carlucci Aiello, Fiora Pirri, “Strutture, logica, linguaggi” (Pearson, 2005)

Metodi didattici

Lezioni frontali ed esercitazioni. Uso della piattaforma Moodle.