Sviluppo di algoritmi di base e implementazione usando il linguaggio Python.
Rappresentazione delle informazioni: liste lineari, alberi, grafi. Algoritmi di ricerca e di ordinamento. Complessità degli algoritmi.
Sistemi di gestione di basi di dati: modello logico relazionale, operatori dell’algebra relazionale Introduzione alla teoria della normalizzazione. Il linguaggio SQL e la sua implementazione MySQL.
- P. Atzeni, S. Ceri, P. Fraternali, S. Paraboschi, R. Torlone, Basi di dati, McGraw-Hill, 2018, quinta edizione.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduzione agli algoritmi e strutture dati”, McGraw-Hill.
- Think Python: How to Think Like a Computer Scientist by Allen B. Downey Beijing: O'reilly Media . Traduzione disponibile: http://www.andreamarino.it/python/thinkcspy/toc.html#t-o-c
Obiettivi Formativi
Al termine dell'insegnamento lo studente:
- sa tradurre un algoritmo nel linguaggio Python;
- conosce le strutture dati fondamentali, ne ha compreso l'utilizzo, le possibili implementazioni e le operazioni fondamentali ed è in grado di valutare la complessità computazionale di tali operazioni;
- conosce gli algoritmi di ricerca su memoria interna, gli algoritmi di ordinamento e gli algoritmi di base sui grafi;
- ha compreso il funzionamento di tali algoritmi e lo sa riprodurre;
- sa calcolare la complessità computazionale dei suddetti algoritmi nel caso ottimo e nel caso medio;
- sa analizzare un problema;
- sa individuare e/o progettare le strutture dati e l'algoritmo più idonei a risolvere il problema ed al suo contesto applicativo;
- sa stimare il costo computazionale della soluzione proposta;
- sa implementare la soluzione in modo corretto ed efficiente;
- sa motivare le scelte fatte argomentandole ed utilizzando un linguaggio tecnico corretto;
- acquisisce conoscenze sul modello relazionale, l'algebra relazionale e i concetti di base del linguaggio SQL;
- acquisisce le competenze fondamentali per la progettazione di una base di dati relazionale e per l'utilizzo della stessa tramite un reale sistema per la gestione di basi di dati;
- sa tradurre uno schema relazionale, nonché le relative interrogazioni, in linguaggio SQL;
- ha la capacità di valutare criticamente basi di dati già progettate e/o implementate, ed eventualmente proporre modifiche atte a migliorarne la struttura.
Prerequisiti
No
Metodi Didattici
CFU: 9
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attività formative di tipo individuale: 153
Numero di ore relative alle attività in aula: 72
Altre Informazioni
Frequenza delle lezioni: raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Software - Spyder all'interno di Anaconda, PythonTutor o repl.it.
Orario di ricevimento: previo appuntamento via e-mail:
andrea.marino@unifi.it
donatella.merlini@unifi.it
mariacecilia.verri@unifi.it
Modalità di verifica apprendimento
L'esame consiste di tre parti, di uguale importanza per la formulazione del giudizio finale.
Per quanto riguarda la programmazione è previsto lo svolgimento di un progetto. Lo scopo del progetto è verificare la capacità di sviluppare in autonomia algoritmi e applicarli in pratica su un dataset dato in modo asincrono usando il linguaggio Python.
Per quanto riguarda gli algoritmi e le strutture dati, è prevista una discussione del progetto svolto per la sezione di Programmazione, volta a verificare la capacità di analisi del problema affrontato e della sua complessità e la scelta delle strutture dati utilizzate. Il colloquio ha come scopo la valutazione della conoscenza degli argomenti presentati, l'acquisizione del linguaggio tecnico adeguato al contesto, la capacità di mettere in relazione fra loro argomenti diversi del programma.
Infine è prevista la realizzazione di una base di dati relazionale secondo le modalità descritte sul sito del corso: dovranno essere consegnati una relazione con la descrizione delle fasi di progettazione concettule e logica della basi di dati e uno script con la sua implementazione in MySQL. Lo studente presenterà il progetto e saranno valutati i contenuti della relazione, gli aspetti DDL e DML dello script e la capacità di argomentare, spiegare e difendere, durante la presentazione, la scelte teorche e pratiche utilizzate.
Programma del corso
Introduzione ai linguaggi di programmazione e Python: dati semplici; iterazioni; moduli Python; le funzioni; la selezione; ricorsione; stringhe; liste;
dizionari; file; classi e oggetti; Numpy e Pandas.
Introduzione agli algoritmi. Analisi di complessità degli algoritmi: operazione fondamentale e dimensione del problema, notazione O grande, complessità nel caso peggiore e nel caso medio, complessità in tempo e in spazio, relazioni fondamentali di ricorrenza. Strutture dati astratte: pile, code, code con priorità, alberi. Algoritmi di ricerca: ricerca binaria, alberi binari di ricerca, trie, ricerca casuale. Algoritmi di ordinamento: algoritmi elementari, Quicksort, Mergesort, Heap sort. Grafi: Rappresentazione dei grafi, algoritmi di visita.
Sistemi di gestione di basi di dati: modello logico relazionale, schemi e istanze, vincoli intrarelazionali e interrelazionali. Algebra relazionale: operatori insiemistici, ridenominazione, selezione, proiezione, join naturale, prodotto cartesiano, theta join. Introduzione alla teoria della normalizzazione: dipendenze funzionali, decomposizione di schemi e forme normali 3NF e BCNF. Il linguaggio SQL e la sua implementazione MySQL: creazioni di schemi, vincoli e istanze. Interrogazioni semplici, con join, interrogazioni annidate, con operatori aggregati e funzioni di selezione. Creazione di viste.