2012
2012
Sei collegato come utente non registrato
Il percorso ha la certificazione
Corso di Laurea: Informatica
-
Percorso: Matematica discreta e Informatica teorica
| Informazioni generali | ||||
| Università | ROMA "La Sapienza" | Responsabile del Percorso | Paola Velardi | |
|---|---|---|---|---|
| Livello del Cdl | MAGISTRALE | velardi@di.uniroma1.it | ||
| Docenti che insegnano nel corso*: | 27 | Afferisce al primo corso di laurea iscritto | Si | |
| (*) Questo è il numero di docenti appartenenti ai settori scientifico-disciplinari INF/01 o ING-INF/05 che svolgono il loro carico didattico istituzionale presso questo corso di laurea | E' un percorso interdisciplinare | No | ||
| Commento | ||||
| Legenda delle Aree | |||||
| A: | Fondamenti | G: | Basi di dati | altro INF: | Crediti di INFORMATICA non classificati nelle aree |
|---|---|---|---|---|---|
| B: | Algoritmi | H: | Computazione su rete | INF: | Crediti di INFORMATICA non classificabili a priori |
| C: | Programmazione | I: | Ingegneria del software | MAT: | Crediti di MATEMATICA |
| D: | Linguaggi | L: | Interazione, grafica e multimedialità | altro: | Crediti NON dell'INFORMATICA nè della MATEMATICA |
| E: | Architetture | M: | Rappresentazione della conoscenza | NC: | Crediti Non Classificabili a priori |
| F: | Sistemi operativi | A_M: | Una qualunque delle aree da A a M | ||
| Insegnamenti e ripartizione CFU per area | CFU | A | B | C | D | E | F | G | H | I | L | M | A_M | altro INF | INF | MAT | altro | NC |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Algoritmi e strutture dati | 6 | 6 | ||||||||||||||||
| Calcolabilità e complessità | 6 | 6 | ||||||||||||||||
| Compilatori | 6 | 6 | ||||||||||||||||
| Complessità | 6 | 6 | ||||||||||||||||
| Insegnamenti a scelta dello studente | 12 | 12 | ||||||||||||||||
| Insegnamenti a scelta vincolata non di Informatica | 6 | 6 | ||||||||||||||||
| Inswegnamenti a scelta vincolata di Informatica | 6 | 6 | ||||||||||||||||
| Metodi formali per il software | 6 | 6 | ||||||||||||||||
| Sistemi distribuiti | 6 | 5 | 1 | |||||||||||||||
| Teoria dei grafi | 6 | 2 | 4 | |||||||||||||||
| Teoria dell'informazione | 6 | 6 | ||||||||||||||||
| Teoria della computazione | 6 | 6 | ||||||||||||||||
| Attività Extracurriculari | 0 | 0 | ||||||||||||||||
| Lingue Straniere | 0 | 0 | ||||||||||||||||
| Prova Finale | 36 | 36 | ||||||||||||||||
| Tirocinio | 6 | 6 | ||||||||||||||||
| TOTALE | 120 | 26 | 10 | 0 | 6 | 0 | 5 | 0 | 1 | 6 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 60 |
Riepilogo dell'insegnamento: Algoritmi e strutture dati
| Nome | Algoritmi e strutture dati | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area B - Algoritmi
Sillabo dell'insegnamento
- B - Algoritmi
- *
SDF - Strutture di Dati Fondamentali
Alberi etchettati e loro applicazioni nella tomografia delle reti e per indicizzare documenti XML. - *
A - Algoritmi fondamentali
Nearest neighbor search e sue applicazioni in pattern recognition e image retrieval. -
SDA - Strutture di Dati Avanzate
Splay tree come strutture dati utili nell'implementazione di caches e negli algoritmi di garbage collection. - *
SDF - Strutture di Dati Fondamentali
Suffix tree e loro uso in ricerca avanzata di stringhe, biologia computazionale e compressione dati. - *
A - Algoritmi fondamentali
Min Cut e sue applicazioni per il branch-and-bound. -
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Analisi ammortizzata; calcolo dei differenti approcci alla complessità ammortizzata relativo a problemi elementari.
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Calcolabilità e complessità
| Nome | Calcolabilità e complessità | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
- *
CAL - Calcolabilita'
Macchine di Turing - *
ALF - Automi e Linguaggi Formali
Automi a stati finiti - *
ALF - Automi e Linguaggi Formali
Automi a pila e grammatiche acontestuali. -
COM - Complessita'
Classi di complessità - *
CAL - Calcolabilita'
Decidibilità -
COM - Complessita'
Problemi trattabili e problemi non provatamente intrattabili: P e NP.
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Compilatori
| Nome | Compilatori | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area D - Linguaggi
Sillabo dell'insegnamento
- D - Linguaggi
- *
LF - Linguaggi Formali
Scansione del testo e riconoscimento automatico dei lessemi, basato su grammatiche regolari ed espressioni regolari. - *
TTCI - Tecniche di Traduzione: Compilatori e Interpreti
Analisi Semantica - *
TTCI - Tecniche di Traduzione: Compilatori e Interpreti
Analisi sintattica - *
TTCI - Tecniche di Traduzione: Compilatori e Interpreti
Generazione del codice oggetto: analisi e ottimizzazione - *
MATR - Macchine Astratte e Tecniche per la Realizzazione dei linguaggi di programmazione
Generazione del metacodice - *
TTCI - Tecniche di Traduzione: Compilatori e Interpreti
Riconoscimento dei programmi: metodi deduttivi (tecniche top-down) e induttivi (tecniche bottom-up).
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Complessità
| Nome | Complessità | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
-
COM - Complessita'
Nozioni di base -
COM - Complessita'
La complessità dei problemi di ottimizzazione -
COM - Complessita'
Algoritmi e classi probabilistiche -
COM - Complessita'
La gerarchia polinomiale -
COM - Complessita'
Il teorema PCP -
COM - Complessita'
Approssimazione randomizzata
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Insegnamenti a scelta dello studente
| Nome | Insegnamenti a scelta dello studente | CFU | 12 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | --libero-- |
12 cfu così ripartiti nelle aree:
- 12 CFU nell'area NC - Crediti Non Classificabili a priori
Sillabo dell'insegnamento
Non è presente il sillabo poiché non vi sono crediti allocati in aree per cui è previsto.
Riepilogo dell'insegnamento: Insegnamenti a scelta vincolata non di Informatica
| Nome | Insegnamenti a scelta vincolata non di Informatica | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | --libero-- |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area NC - Crediti Non Classificabili a priori
Sillabo dell'insegnamento
Non è presente il sillabo poiché non vi sono crediti allocati in aree per cui è previsto.
Riepilogo dell'insegnamento: Inswegnamenti a scelta vincolata di Informatica
| Nome | Inswegnamenti a scelta vincolata di Informatica | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A_M - Una qualunque delle aree da A a M
Sillabo dell'insegnamento
Non è presente il sillabo poiché non vi sono crediti allocati in aree per cui è previsto.
Riepilogo dell'insegnamento: Metodi formali per il software
| Nome | Metodi formali per il software | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area I - Ingegneria del software
Sillabo dell'insegnamento
- I - Ingegneria del software
- *
LMS - Linguaggi di Modellazione del Software
Metodi di Modellazione di Sistemi Software - *
AR - Analisi dei Requisiti
Metodi di Specifica dei Requisiti di Sistemi Software - *
PSC - Progettazione del Software e Codifica
Metodi di Analisi e Sintesi di Sistemi Software - *
AR - Analisi dei Requisiti
Definizione e la validazione dei requisiti - *
LMS - Linguaggi di Modellazione del Software
Algebre di processo, Timed/Hybrid Automata, Statecharts, Reti di Petri - *
PSS - Processi di Sviluppo del Software
Static analysis, testing, model checking, sintesi automatica, trasformazione di programmi e modelli
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Sistemi distribuiti
| Nome | Sistemi distribuiti | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 5 CFU nell'area F - Sistemi operativi
- 1 CFU nell'area H - Computazione su rete
Sillabo dell'insegnamento
- F - Sistemi operativi
- *
GSP - Gestione e Sincronizzazione dei Processi
Shared memory e la gerarchia wait-free - *
GSP - Gestione e Sincronizzazione dei Processi
Mutua esclusione e deadlock detection - *
GSP - Gestione e Sincronizzazione dei Processi
Logical time - *
GSP - Gestione e Sincronizzazione dei Processi
Consensus - *
GSP - Gestione e Sincronizzazione dei Processi
Failure detectors - H - Computazione su rete
- *
ARTC - Architettura delle Reti di Calcolatori
Sistemi P2P
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Teoria dei grafi
| Nome | Teoria dei grafi | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 2 CFU nell'area A - Fondamenti
- 4 CFU nell'area B - Algoritmi
Sillabo dell'insegnamento
- A - Fondamenti
-
TIC - Teoria dell'Informazione e Codici
Introduzione alla teorai di Ramsey ed esistenza dei numeri di Ramsey -
TIC - Teoria dell'Informazione e Codici
Teoria dei grafi estrema - B - Algoritmi
- *
ASC - Algoritmi su Strutture Combinatorie
Strutture in grafi: Matching in grafi bipartiti (Teorema di Konig e Hall) - *
SDF - Strutture di Dati Fondamentali
Cicli su grafi - *
A - Algoritmi fondamentali
Max/flow min cut e algoritmi. - *
ASC - Algoritmi su Strutture Combinatorie
Decomposizione di grafi:
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Teoria dell'informazione
| Nome | Teoria dell'informazione | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
-
TIC - Teoria dell'Informazione e Codici
Conteggio di sequenze e entropia -
TIC - Teoria dell'Informazione e Codici
Codici di sorgente -
TIC - Teoria dell'Informazione e Codici
Problemi stocastici. -
TIC - Teoria dell'Informazione e Codici
Problemi non?stocastici -
TIC - Teoria dell'Informazione e Codici
Struttura temporale di sorgenti -
SLP - Semantica dei Linguaggi di Programmazione
Misure dell'informazione e le loro propriet`a analitiche
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
Riepilogo dell'insegnamento: Teoria della computazione
| Nome | Teoria della computazione | CFU | 6 |
|---|---|---|---|
| Ore di didattica frontale per CFU | 10 | Settore Scientifico Disciplinare | INF/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
- *
CAL - Calcolabilita'
Introduzione, definizioni ed esempi di computazioni efficienti in differenti modelli di computazioni - *
CAL - Calcolabilita'
Circuiti booleani ed algebrici, -
L - Logica
Dimostrazioni Naturali -
COM - Complessita'
Problemi combinatori per lo studio dei limiti di un modello - *
CAL - Calcolabilita'
Modelli di computazione -
COM - Complessita'
Misure di Complessità
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
