Strumenti personali
Logotipo di UniBa

Sezioni

Salta ai contenuti. | Salta alla navigazione

Tu sei qui:HomeDocentiEsposito FlorianaAttività Didattica

Attività Didattica

Insegnamento di "Ingegneria della Conoscenza e Sistemi Esperti" Laurea triennale in Informatica a.a.2017-2018 1° semestre Insegnamento di "Algoritmi e Struttue Dati" corso B Laurea triennale in Informatica a.a.2017-2018 1° semestre

Orario di ricevimento durante il periodo delle lezioni

martedì 9.00-11.00

giovedì 9.00-11.00

Per la verifica dei progetti confermare sempre gli incontri via e.mail


 


Materiali didattici

Consultare la piattaforma

http://informatica2.di.uniba.it e iscriversi ai corsi


A. A. 2017/2018

CORSO DI LAUREA IN INFORMATICA (Legge 270)

Programma di Algoritmi e Strutture Dati (b)
CORSO DI LAUREA IN        Informatica (Triennale DM 270)

Nø ORE LEZIONI FRONTALI    56            Nø CREDITI    7 T1
Nø ORE ESERCITAZIONI    --            Nø CREDITI    -
Nø ORE LABORATORIO    30            Nø CREDITI    2 T2
Nø ORE STUDIO INDIVIDUALE    139            
TOTALE CREDITI    9

PRE-REQUISITI
* Principi della programmazione strutturata e della programmazione modulare;
* conoscenza e pratica di almeno un linguaggio di Programmazione imperativa;
* concetto di tipo e Strutture dati predefinite;
* principi dell'astrazione funzionale (funzioni e procedure) e meccanismi di passaggio dei parametri;
* compilazione separata.


OBIETTIVI FORMATIVI
Viene presentata una metodologia di progetto formale basata sulla astrazione dei dati e sono introdotte tecniche di programmazione orientata ad oggetti. Oltre alla capacita' di rappresentare in modo formale diversi tipi di problemi, saranno acquisiti i rudimenti della programmazione per classi attraverso la realizzazione di dati astratti in ambienti di programmazione orientati ad oggetti. Saranno acquisiti i principi della algoritmica, presentati in funzione del modo di utilizzo dello spazio di ricerca: le caratteristiche dei paradigmi selettivo e generativo verranno evidenziate attraverso diversi algoritmi fondamentali.
________________________________________________________________________

OBIETTIVI PROFESSIONALIZZANTI
Capacita' di integrare le tecniche di astrazione funzionale con quelle di astrazione dati nella progettazione di programmi per la soluzione di un problema, individuando le strutture dati piu' opportune, il metodo solutivo e la tecnica algoritmica appropriata, le tecniche di realizzazione più efficienti in un linguaggio di programmazione di riferimento, valutandone i costi ed i benefici in termini di complessita' di calcolo. Essere in grado di implementare diverse realizzazioni degli operatori relativi a strutture dati non primitive in un linguaggio imperativo e in uno orientato ad oggetti.
________________________________________________________________________

CONTENUTI
1.    Algoritmi e programmi
Presentazione del corso. Il ruolo delle tecniche di astrazione nel progetto di programmi. Dall'algoritmo al programma; la valutazione dell'algoritmo.
2.    Algebre di dati
Dati e rappresentazioni, requisiti delle astrazioni di dati, costrutti. Astrazioni di dati e dati primitivi. Algebre di dati: specifica sintattica e semantica. La realizzazione.
3.    Strutture lineari di dati
Liste: specifiche, realizzazioni attraverso rappresentazioni sequenziali e collegate. Pile: specifiche e realizzazioni alternative, pile e procedure ricorsive. Code: specifiche e realizzazioni alternative. Scelta, implementazione e verifica di algoritmi per la ricerca, l'ordinamento e la fusione delle strutture dati proposte.
4.     Analisi della Complessità di calcolo
Generalità. Tempo di calcolo. Ordini di grandezza e complessità. Modelli di costo per la complessita' in tempo e in spazio. Definizione delle funzioni di costo.
5.    Insiemi e Dizionari
Insiemi: specifiche e confronto tra realizzazioni alternative. Dizionari: specifiche e confronto di realizzazioni alternative (Hash chiuso e aperto, vettori e liste ordinate).
6.    Strutture non lineari di dati: Alberi binari ed n-ari.
Generalita'. Gli alberi radicati e alberi ordinati, proprieta'. Alberi binari: specifiche,
definizione ricorsiva, la corrispondenza con le liste, rappresentazioni e realizzazioni. Alberi binari di ricerca,
alberi bilanciati. Alberi n-ari: specifiche, definizione ricorsiva, rappresentazioni e realizzazioni alternative. Algoritmi su alberi binari ed n-ari: visita, inserimento di un valore e ricerca di un valore.
7    Code con priorita'
Generalita'. Specifiche, rappresentazioni e realizzazioni alternative.
8.    Strutture non lineari di dati: Grafi
Il tipo astratto GRAFO: specifiche sintattiche e semantiche. Rappresentazioni  mediante matrici di adiacenza e di incidenza, vettori di adiacenza, liste di adiacenza, e rappresentazioni collegate: realizzazioni alternative. Algoritmi su grafi: visita di un grafo, cammini minimi e generazione del minimo albero di copertura.
9.    Le tecniche algoritmiche
Classificazione dei problemi: problemi di ricerca, di decisione, di ottimizzazione. Lo spazio di ricerca: definizione e proprieta'. Le tecniche algoritmiche: il paradigma selettivo e il paradigma generativo. Tecnica dell'enumerazione, del backtracking, la tecnica greedy, la tecnica divide-et-impera. Problemi e metodi solutivi: string matching (Knuth-Morris-Pratt),  partizionamento di insiemi, problema delle N Regine, problema dello zaino, problema del commesso viaggiatore, problema della colorazione, ricerca del percorso piu' breve in un grafo (Dijkstra),  minimo albero di copertura (Kruskal), selezione di attivita'.

________________________________________________________________________

TESTO/I ADOTTATO/I
 A. Bertossi, A. Montresor, Algoritmi e Strutture Dati, CittàStudi, 2010
 B. Stroustrup, C++ - Linguaggio, libreria standard, principi di programmazione,III
ed. Addison-Wesley

TESTO/I CONSIGLIATO/I
M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf, Fondamenti della progettazione dei
programmi - Principi, tecniche e loro applicazioni in C++, Citta' Studi Edizioni
E. Lodi, G. Pacini, Introduzione alle strutture di dati, Bollati Boringhieri
________________________________________________________________________


PROPEDEUTICITA' OBBLIGATORIE
Programmazione, Laboratorio di Informatica


Modalità di esame
L'esame consiste di una prova di laboratorio e di una prova scritta. La prova di laboratorio, riguarda l'analisi, la progettazione della strategia solutiva e la corrispondente realizzazione in C++ di un problema.
LE PROVE DI LABORATORIO SVOLTE CON ESITO POSITIVO HANNO UNA VALIDITÀ DI 90 GIORNI.
Lo studente è tenuto a presentarsi all'esame orale con gli esercizi/programmi svolti durante l'anno relativi alla realizzazione di strutture dati e prove di algoritmi.





________________________________________________________________________

CORSO DI LAUREA IN INFORMATICA (Legge 270)

PROGRAMMA di  Ingegneria della conoscenza e Sistemi Esperti

N° ORE LEZIONI FRONTALI:   32     N° CREDITI: 4

N° ORE ESERCITAZIONI:                15   N° CREDITI: 1

N° ORE LABORATORIO/PROGETTO:   25          N° CREDITI: 1

N° ORE STUDIO INDIVIDUALE:      103   

TOTALE CREDITI:  6

___________________________________________________________

 PRE-REQUISITI:

Conoscenza dei paradigmi di programmazione, conoscenza delle strutture dati dinamiche e delle nozioni di algoritmica (tecniche selettive e tecniche generative)

___________________________________________________________

 OBIETTIVI FORMATIVI

Conoscenza dei principi della programmazione euristica, conoscenza del paradigma di programmazione a regole

____________________________________________________________

 OBIETTIVI PROFESSIONALIZZANTI

Capacità di utilizzare ambienti a regole ed integrare paradigmi di programmazione alternativi  per risolvere problemi di aiuto alle decisioni, classificazione, diagnosi. Abilità a progettare interpreti per la realizzazione di sistemi di programmazione euristica.

____________________________________________________________

CONTENUTI

1. Introduzione: l’importanza della conoscenza

1.1 Introduzione: la conoscenza. Il comportamento intelligente e la conoscenza.

1.2 Agenti stimolo-risposta, agenti teleo-reattivi: i modelli.  L’Agente razionale. Il modello di Agente Intelligente.

1.3 I sistemi basati su conoscenza (KBS) come agenti intelligenti. I tipi di conoscenza.

1.4 Il modello di calcolo: i sistemi di  produzioni vs il modello di Turing. La strategia di controllo: il recognize-act cycle, il matching e la soluzione dei conflitti. Ragionamento in avanti e ragionamento all’indietro

2. Programmazione euristica

2.1 Risolvere problemi tentativamente: i principi della Programmazione Euristica. La rilevanza del linguaggio di descrizione. Ricercare la soluzione mediante strategie irrevocabili e strategie tentative. Ricerca cieca e ricerca informata.

2.2 La ricerca della soluzione come ricerca su grafo. La procedura GRAPH-SEARCH generalizzata. Ricerca informata e l’uso di euristiche: l’algoritmo A*, ammissibilità di A*, confronto tra algoritmi di ricerca ammissibili. Misure di prestazione.

2.3 Giochi. Ricerca per sistemi a due agenti avversari: gli algoritmi minmax e alpha-beta.

3. I sistemi esperti

3.1 I sistemi esperti: obiettivi, caratteristiche e architettura. Il ciclo di sviluppo di un sistema esperto.

3.2 I linguaggi per lo sviluppo di sistemi intelligenti e di agenti basati su conoscenza. L'esigenza di ambienti interpretati:  CLIPS, un ambiente per Sistemi a regole.

3.3 Ingegneria dei sistemi basati su conoscenza: la fase di acquisizione della conoscenza. Acquisire conoscenza automaticamente da esempi inferendo alberi di decisione.

3.4 Ragionare con conoscenza incerta: ragionamento statistico, inferenza col teorema di Bayes, Fattori di certezza. Cenni a logiche Fuzzy.

4. Sistemi esperti con compiti specifici

4.1 Sistemi esperti per classificazione e diagnosi: MYCIN.

4.2 Sistemi esperti per Pianificazione: generalità. STRIPS, ABSTRIPS e pianificazione  gerarchica.

4.3 Sistemi esperti con compiti di configurazione: XCON.

Testi adottati

Di base:

Elaine Rich, Kevin Knight, Shivashankar B. Nair, “Artificial Intelligence“ third edition Mc Graw Hill, 2008

S. J. Russell, P. Norvig,  “Intelligenza Artificiale“ Prentice Hall, Vol. I, 2005

 

Riferimenti:        

Nils J. Nilsson “Principles of Artificial Intelligence” Morgan Kaufmann, 1980

Peter Jackson “Introduction to Expert Systems” Addison Wesley, 1998

Mark Stefik “Knowledge Systems”, Morgan Kaufmann, 1995

Keith Darlington, “The essence of expert systems”, Prentice Hall, 2000

 

Lucidi lezioni

Programmazione a regole:  Manuali dei sistemi

___________________________________________________________

PROPEDEUTICITÀ OBBLIGATORIE

Quelle previste dal manifesto degli studi dell’anno di immatricolazione.

__________________________________________________________

PROPEDEUTICITÀ CONSIGLIATE

Algoritmi e strutture dati.

Metodi avanzati di programmazione

____________________________________________________________

MODALITA’ D’ESAME

L'esame consiste nella discussione del progetto realizzato dallo studente e nella interrogazione orale sui contenuti del programma

Azioni sul documento
Pubblicato il: 02/09/2013  Ultima modifica: 12/09/2017