A partire dal 9 marzo Le lezioni si svolgeranno telematicamente nelle ore previste dall'orario.

Per partecipare accedere all'URL:

http://unipi.it/corsionline ed eseguire le istruzioni della guida per partecipare alle lezioni su Teams di Microsoft.

Il ricevimento studenti sarà fatto via mail, oppure via Skype su appuntamento.

Le lezioni di laboratorio si svolgeranno on line (streaming), a partire da martedì 10 marzo alle ore 11 sulla piattaforma Meet di Google.

Attenzione: le lezioni non saranno registrate. Seguitele rispettando gli orari del corso.

Gli studenti del corso di laurea in Informatica sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo link

Gli studenti del corso di laurea in Data Science sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo link

Gruppo Telegram con gli assistenti di laboratorio: link

Docenti Teoria/Esercitazioni: Linda Pagli e Giuseppe Prencipe (corso A)

Docenti Laboratorio: Anna Bernasconi, Franco Maria Nardini, Rossano Venturini

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Semestre: secondo.

Ricevimento studenti: Pagli: su appuntamento, scrivere a [email protected]

Ricevimento studenti Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento)

Ricevimento studenti Bernasconi: Mercoledì, dalle 9 alle 11, sulla piattaforma Meet di Google. Ricevo inoltre via Skype su appuntamento. Tramite mail avverrà lo scambio dei contatti skype e l'accordo sul giorno e sull'orario.

Registro delle lezioni: si tratta del registro ufficiale che riporta quanto indicato nel seguito.

• A.A. 2018/2019
• A.A. 2017/2018
• A.A. 2016/2017
• A.A. 2015/2016
• A.A. 2014/2015
• A.A. 2013/2014
• A.A. 2012/2013

NEWS: Starting from Tuesday March 3rd, the Python Lab slot dedicated to Data Science Master Degree students is anticipated at 11:00-13:00 (still in class-room I). Therefore Data Science students should head to that time slot, while first year students are now allowed to attend the C Lab class at 14:00 even in classroom I.

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.

MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE

L'esame degli appelli estivi consistono in due prove obbligatorie:

• Una prova di Laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi. La prova avra’ luogo sulla consueta piattaforma d’esame accessibile via browser, e sara’ validata da un colloquio orale immediatamente successivo. Tale prova è da intendersi come un test di idoneità.
• Una prova orale sul programma del corso la cui valutazione finale è in trentesimi, atta a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente.
• La prova orale puo' essere sostenuta solo dopo aver superato la prova di Laboratorio.
• Le prove possono essere sostenute in appelli diversi.
• Se la prova orale non viene superata, occorre ripetere soltanto quella.

Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria. Attenzione: la scadenza per iscriversi non sara’ molto a ridosso delle prove d’esame, controllate l'apposito portale.

DATA SCIENCE STUDENTS: PLEASE CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS

Prossime date per la prova di Laboratorio:

Prossime date per la prova orale:

Gli orali della I sessione autunnale si svolgeranno il 3 Settembre, a partire dalle ore 14:00:

https://agende.unipi.it/ssc-vme-ekp

Per la discussione orale, si utilizza il canale Teams che è stato utilizzato per lo svolgimento delle lezioni.

Prossime date per la prova di laboratorio linguaggio Python per studenti della LM in Data Science:

http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/AlgoLezioniVideo2020

• [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.
• [DFI] C. Demetrescu, I. Finocchi, G. Italiano. Algoritmi e strutture dati. McGraw-Hill, Seconda edizione, 2008. Solo pagine 161-165.
• [FL] P. Ferragina, F. Luccio. Il Pensiero Computazionale: dagli algoritmi al coding. Il Mulino, 2017. Solo pagine 64-65, Capitolo 7 e Capitolo 10.

Per il laboratorio, un testo fra:

• [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.
• [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004.

• Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
• Strumenti per la programmazione: Un editore testuale (tipo Emacs), e il compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.
• Materiale didattico di supporto per il laboratorio
• Altro materiale di supporto per il laboratorio preparato da uno studente
• Sistema di Autovalutazione: http://algo1920.dijkstra.di.unipi.it/

1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
4. Divide-et-impera, Relazioni di ricorrenza, Teorema “dell'esperto”.
5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
7. Ordinamento di interi: Counting sort, Radix Sort.
8. Ordinamento di stringhe: qsort-based.
9. Sottosequenza di somma massima.
10. Programmazione dinamica: LCS, Partizione e Zaino
11. Algoritmi randomizzati: Quicksort.
12. Generazione di combinazioni e permutazioni
13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
14. Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
15. Alberi: rappresentazione e visite.
16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
18. Grafi III: Minimum Spanning Tree e Shortest Path.