Corso di laurea in Informatica

L’insegnamento getta le basi di un approccio formale all’informatica, e costituisce il fondamento metodologico di tutto il successivo percorso formativo. I macro-argomenti dell’insegnamento: 

• rappresentazione dei dati e loro codifica digitale e circuiti digitali;  
• introduzione alle tecniche di dimostrazione e alla logica proposizionale e dei quantificatori; 
• elementi di teoria dei linguaggi regolari e automi a stati finiti, 

contengono un insieme di conoscenze e competenze richieste da tutti i successivi insegnamenti di settore informatico. Quindi l’insegnamento ha un carattere propedeutico e multidisciplinare.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE

Al termine dell’insegnamento saranno state acquisite:

- conoscenza delle tecniche di rappresentazione digitale dell’informazione

- conoscenza dei circuiti digitali

- conoscenza delle tavole di verità per i connettivi proposizionali, della deduzione naturale per la logica delle proposizioni e dei quantificatori

- conoscenza delle principali equivalenze relative ai connettivi proposizionali e ai quantificatori (leggi di de Morgan, dualità dei quantificatori)

- conoscenza delle principali costruzioni e dei principali teoremi sui linguaggi formali

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE

Al termine dell’insegnamento si sarà in grado di:

- codificare e decodificare numeri con e senza segno, interi, frazionari, in virgola mobile;

- simulare il comportamento di circuiti combinatori e semplici circuiti sequenziali

- analizzare e sintetizzare di circuiti logici elementari per realizzare funzioni booleane

- formalizzare enunciati nel linguaggio naturale in termini di logica elementare

- riconoscere le principali forme di dimostrazione relative ai connettivi proposizionali e ai quantificatori

- seguire in dettaglio lo svolgersi delle dimostrazioni illustrate nell'ambito del corso, e produrre in autonomia semplici dimostrazioni, anche utilizzando le regole della deduzione naturale

- associare linguaggi regolari ad automi finiti e dimostrare la non regolarità di linguaggi

AUTONOMIA DI GIUDIZIO

Saper valutare la correttezza delle applicazione delle tecniche apprese. Saper scegliere le tecniche più adeguate in situazioni nuove.

ABILITÀ COMUNICATIVE

Saper descrivere sotto forma di testo scritto e con sufficienti dettagli le applicazioni delle tecniche apprese nel corso

CAPACITÀ DI APPRENDIMENTO

Sviluppo di capacità autonome di apprendimento e di autovalutazione della propria preparazione. Capacità di intraprendere gli studi successivi della propria carriera di studente con un alto grado di autonomia.

Codifica digitale dell’informazione: bit, byte e suoi multipli. 

Cenni riepilogativi sulla notazione posizionale

Codifica dei numeri naturali e interi: binario, ottale, esadecimale, complemento a 1 e a 2

Elementi di codifica dei numeri reali: virgola mobile, notazione esponenziale

Porte logiche, tavole di verità, espressioni Booleane e forme normali

Circuiti combinatori

Cenni sui circuiti sequenziali

La rappresentazione insiemistica di relazioni e funzioni, costruzioni su insiemi: insieme potenza, prodotto cartesiano, somma disgiunta e insieme delle funzioni di dominio e codominio dati. 

Principali equivalenze relative a operazioni su insiemi e loro dimostrazione.

Tecniche di dimostrazione: dimostrazione diretta, per assurdo, per contrapposizione; dualità dei quantificatori.

Tavole di verità e nozione di conseguenza logica per la logica proposizionale.

Cenni sulla semantica dei quantificatori

Nozioni di base di linguaggi formali: alfabeto, parole su un alfabeto e operazione di concatenazione. L'insieme dei linguaggi e operazioni su linguaggi.

Automi a stati finiti e loro relazioni con i circuiti sequenziali; automi non deterministici con teorema di Rabin-Scott

Espressioni regolari e loro semantica: teorema di Kleene.

Proprietà dei linguaggi regolari, pumping lemma.

Lezioni frontali in presenza, ove possibile registrate. Le registrazioni verranno pubblicate sulla pagina Moodle del corso.

Esame scritto costituito da domande ed esercizi erogati attraverso la piattaforma Moodle, e diviso in due parti, il superamento dalla prima parte è condizione necessaria per accedere alla seconda. Il punteggio della prova scritta, espresso in 30esimi, sarà dato dalla somma dei punteggi  in 30esimi dei singoli esercizi. Il punteggio di ogni esercizio valuterà la conoscenza, la capacità di applicarla e di organizzarla in un discorso. Valuterà inoltre la capacità di ragionamento e la qualità dell’esposizione (competenza nell’impiego del lessico specialistico, efficacia, linearità). 

Alcune delle lezioni saranno dedicate a esercitazioni mirate a consolidare l’acquisizione delle competenze in uscita.