Metodi informazionali (2017/2018)

Codice insegnamento
4S00995
Docenti
Vincenzo Manca, Giuditta Franco
Coordinatore
Vincenzo Manca
crediti
6
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Periodo
II sem. dal 1-mar-2018 al 15-giu-2018.

Orario lezioni

Vai all'orario delle lezioni

Obiettivi formativi

Il corso intende presentare le strutture discrete fondamentali enfatizzandone il ruolo nella definizione di modelli matematici di rilevanza biologica. Nella prima parte, dopo una introduzione delle strutture discrete basilari, si analizzano i sistemi numerici, le rappresentazioni dei numeri e il principio di induzione strutturale e i principali schemi combinatori. Quindi si introducono i concetti di base dei linguaggi formali e degli automi e le nozioni di decidibilità, calcolabilità, semidecidibilità.

Programma

Strutture discrete: insiemi, multinsiemi, sequenze, stringhe, operazioni, relazioni, funzioni, variabili, parentesi ed espressioni. Numeri e induzione: sistemi numerici, rappresentazioni di numeri, dimostrazioni per induzione, definizioni e induttive di importanti successioni numeriche. Induzione strutturale su stringhe, alberi e grafi. Cenni ai linguaggi logici del primo ordine (termini, formule ed interpretazioni). Elementi di combinatoria: allocazioni e partizioni, coefficienti binomiali e multinomiali. Multinsiemi, Partizioni di insiemi e interi. Linguaggi, grammatiche e automi: pattern ed espressioni regolari, gerarchia di Chomsky, automi a stati finiti. Automi di calcolo e macchina di Turing. Decidibilita', semidecidibilita' ed indecidibilita'.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Vincenzo Manca Infobiotics Springer 2013

Modalità d'esame

Esame scritto ed orale.

Per superare l'esame scritto lo studente deve essere in grado di usare correttamente il formalismo appreso durante il corso descrivendo brevemente le soluzioni ai quesiti posti dal testo di esame.

L'esame orale parte dalla verifica delle soluzioni proposte, in cui lo studente deve giustificare quanto scritto ed eventualmente chiarire i passaggi non chiari. Durante il colloquio verranno posti delle domande specifiche sul programma svolto, intese ad appurare la comprensione dei concetti fondamentali che il corso si prefigge di trasmettere.

Materiale didattico
Manca, V. - Infobiotics. Springer, 2013 (Capitoli 5, 6, 7).
Manca V. - Vademecum all'Esame di Metodi Informazionali (con lista delle definizioni e dei teoremi più 100 esercizi svolti).

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2017/2018 non sono ancora disponibili