Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Education
Fondamenti dell'Informatica

Codice insegnamento: E3101Q102

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 basilari della logica (proposizionale e predicativa).

Testo di riferimento:
Luigia Carlucci Aiello, Fiora Pirri, Strutture, logica, linguaggi, (Pearson, 2005).

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. 

Prerequisiti:
Conoscenze matematiche di base apprese durante la scuola superiore.

Metodi didattici
Lezioni frontali ed esercitazioni

Altre informazioni:
Uso della piattaforma Moodle 

Programma esteso:

Strutture relazionali e induttive:

  • 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)
  • 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)
  • Algebra di Boole (semigruppi, monoidi e gruppi, congruenze e quozienti, omomorfismi e isomorfismi, algebra booleana)
  • Introduzione all’induzione (principi d’induzione matematica, induzione e ricorsione su insiemi, stringhe, formule ben formate)

Linguaggi logici

  • Linguaggio proposizionale (linguaggio e semantica, apparato deduttivo, sintassi e semantica della logica proposizionale, equivalenza logica, modelli, decidibilità, completezza di insiemi di connettivi)
  • Sistemi deduttivi proposizionali (completezza e correttezza, calcolo della deduzione naturale, tableau proposizionali, forma normale a clausole, risoluzione proposizionale)
  • Linguaggi predicativi (sintassi della logica predicativa, variabili libere e legate, interpretazioni e modelli, equivalenza semantica, connettivi e operatori insiemistici, teorie del primo ordine)
  • Sistemi deduttivi predicativi (sostituzioni, tautologie e sostituzione uniforme, skolemizzazione, completezza e correttezza nel calcolo predicativo, calcolo della deduzione naturale, unificazioni, tableau predicativi, risoluzione predicativa)

Modalità di verifica dell'apprendimento:
Esame finale

Tipo esame:
Scritto ed eventuale orale separati

Tipo valutazione:
Voto finale

 

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 11/11/2013