Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
Fondamenti dell'Informatica

Codice ins.

Insegnamento

CFU ins.

Tipo ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

E3101Q102

Fondamenti dell'Informatica

8

OBB

1

1

INF/01

BANDINI Stefania

 

Foundations of Computer Science

 

 

 

 

 

 

Docente turno A-L: Bandini Stefania
Docente turno M-Z: Moscato Ugo

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)
  • 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, completezza e correttezza nel calcolo predicativo, accenni di calcolo della deduzione naturale)


Modalità di verifica dell'apprendimento:
Esame finale

Tipo esame:
Scritto ed eventuale orale separati

Tipo valutazione:
Voto finale

Contents:

This course is addressed to the introduction to the formal mathematical basis of theoretical computer science, namely, basic mathematical notions  (set theory, relations and functions), abstract conceptualization instruments (graphs, trees and algebraic structures), and basics of logics (propositional and predicative).

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

Educational goals:
The main aim of the course is to introduce formal, theoretical and technical foundations of computer science. The main issues to be presented have the goal to give students the necessary abstraction level to understand the theoretical and computational basis of computer science through the learning of the basic formal notions to tackle required higher levels of complexity required by the discipline.

Requisites:
Basic mathematical knowledge from High School programs.

 Didactic method:
Active lectures and exercises  

Other information:
e.learning: Moodle

Extended program:
Relational and inductive structures:

  • Sets (extensional and intensinal definitions, sub-sets and power sets, join, intersection, complementation, difference and symmetric difference, partitions, Cartesian product, sequences, pairs and ordered n-tuples, relations, functions and operations, inverted function, function composition, set cardinality, diagonalization, multi-sets, quotient sets, notions of combinatorics)
  • Relational structures, graphs and sorting (relations properties, Boolean matrixes and related operations, graphs, relations of equivalence, composition of relations, transitive closure, ordinal and grids, monotonic functions on ordered sets, fixed-point theorem)
  • Boole algebra (semigroups, monoids and groups, congruences and quotients, homomorphisms and isomorphisms, Boolean algebra)
  • Introduction to induction (principles of mathematical induction, induction and recursion on sets, strings, well-formed formul

    Logical languages:
  • Propositional language (language and semantics, deduction, syntax and semantics of propositional logics, logical equivalence, models, decidability, completeness of set of connectives)
  • Propositional deductive systems (completeness and correctness, natural deduction, propositional tableau)
  • Predicative languages (syntax of predicative logics, free and bound variables, interpretations and models, semantic equivalence, connectives and set operator, first order theories)
  • Predicative deductive systems (substitution, tautologies and uniform substitution, completeness and correctness in the predicate calculus)

Evaluation:
Final mark

Kind of Evaluation:
Written and oral test (in case, separated)

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 11/11/2013