Gli algoritmi e le strutture dati sono concetti che permeano tutta l’Informatica. Essi costituiscono quindi un bagaglio di conoscenze, competenze e abilità indispensabile non solo per tutti gli insegnamenti successivi del Corso di Laurea, ma anche per quelli dei Corsi di Laurea Magistrale in Ingegneria Informatica e in Data Science and Engineering e per l’attività professionale. Sono inoltre fondanti in tutte le attività di problem-solving informatico. I concetti, indipendenti dal linguaggio di programmazione, hanno validità generale. Nell’insegnamento essi vengono concretizzati mediante il linguaggio C che ben si presta ad una visione di dettaglio. In questo contesto l’insegnamento ha come obiettivo di fornire adeguate conoscenze di algoritmi e strutture dati per la soluzione di problemi complessi. Vengono presentate le soluzioni algoritmiche "classiche" dei problemi e la teoria che sta alla loro base. Vengono inoltre proposti modelli per la risoluzione di problemi che comportano l’esplorazione di uno spazio delle soluzioni. Il linguaggio C è lo strumento utilizzato per mettere in pratica il problem-solving. La sua conoscenza, rispetto a quanto appreso nell’insegnamento di Tecniche di Programmazione, viene estesa comprendendo svariati aspetti avanzati, quali l’allocazione dinamica della memoria, la modularità e la realizzazione di Tipi di Dato Astratti. La metodologia didattica alla base dell’insegnamento è lo “schema-based learning”. Uno “schema” è uno strumento della memoria che permette di organizzare esperienze simili in modo che la persona possa acquisire le seguenti abilità: • facilmente riconoscere esperienze simili o dissimili (identificazione) • accedere facilmente ad una base che contiene gli elementi essenziali delle esperienze simili (elaborazione) • derivare conclusioni, effettuare stime e sviluppare algoritmi (pianificazione) • usare strumenti, procedure o regole (risoluzione). Lo “schema-based learning” de-enfatizza la quantità di informazioni fattuali acquisite, in quanto lo scopo non è quello di avere studenti in possesso di grandi quantità di nozioni passive, bensì di renderli risolutori attivi di problemi affrontati top-down, anziché bottom-up. Nel contesto dell’insegnamento: • l’identificazione consiste nella comprensione del problema e nella sua classificazione, grazie alle conoscenze di algoritmi e modelli, in uno degli schemi proposti • l’elaborazione consiste nell’adattare lo schema al problema in esame, completandolo e dettagliandolo • la pianificazione consiste nella scelta del paradigma risolutivo e delle strutture dati sottostanti • la risoluzione consiste nella scrittura, nel testing e nella valutazione del codice C. Come ulteriore aspetto metodologico, si affronta la modularità in termini di strutture dati. Al di là di una modularità basata su accorpamento e suddivisione di istruzioni in sotto-programmi (funzioni C) si affronta il problema di una modularità in termini di strutture dati che, pur basata su ADT, è propedeutica ad aspetti di architettura del software e di programmazione ad oggetti. La metodologia è esemplificata su problemi complessi svolti nel corso delle esercitazioni di laboratorio, il cui scopo è di accentuare negli studenti il passaggio dalle capacità analitiche a quelle progettuali.

Al termine dell’insegnamento gli studenti avranno acquisito: • in termini di conoscenza: o i meccanismi di allocazione della memoria e utilizzo dei puntatori in C o le strutture dati complesse, i Tipi di Dato Astratto (liste, code, pile, heap, alberi, tabelle di hash e grafi) e i relativi algoritmi o le strategie elementari di programmazione modulare in C o i paradigmi di programmazione ricorsiva, dinamica e greedy • in termini di abilità: o la capacità di risolvere problemi complessi in ambito informatico mediante progetto di strutture dati e algoritmi utilizzando tecniche di programmazione ricorsiva, dinamica e greedy o la capacità di valutare la complessità di algoritmi e migliorarne l'efficienza in termini di tempo di esecuzione e/o uso di memoria o la capacità utilizzare strumenti di ausilio alla programmazione • in termini di competenze: o l’utilizzo di conoscenze, abilità e metodologie per lo sviluppo di software in C atto a risolvere problemi che si incontrano in ambito informatico o il miglioramento dell’autonomia di giudizio grazie all’attività progettuale di problem-solving, dove è richiesto di comprendere le specifiche del problema e di completarle, nonché di esplorare diverse possibili strategia di risoluzione, valutandone le complessità o il miglioramento delle capacità comunicative grazie alla soluzione degli esercizi di laboratorio che, quando soggetti a valutazione, richiedono la stesura di una relazione sulle scelte algoritmiche, la scrittura di codice leggibile, la capacità di sostenere in un contraddittorio le proprie scelte algoritmiche ed implementative.

Vista la natura incrementale di questo insegnamento rispetto a quelli del I anno “Informatica” e “Tecniche di Programmazione”, vi sono prerequisiti stringenti in termini di conoscenze e di abilità di programmazione in C, in particolare: • conoscenze o architettura elementare dei sistemi di elaborazione (modello di Von Neumann) o algebra Booleana e funzioni logiche o analisi della complessità o sintassi, tipi di dato e costrutti base del linguaggio C o tipo di dato puntatore o algoritmi di ordinamento quadratici e lineari • abilità: o capacità di sviluppare semplici programmi in C, utilizzando costrutti condizionali e iterativi, dati scalari o aggregati, I/O standard, file testo e funzioni o capacità di soluzione di problemi (algoritmici) elementari. ll problem solving, in quanto attività con caratteristiche “progettuali e creative”, si distingue da “compiti prevalentemente esecutivi e limitati all’utilizzo di stumenti e/o tecniche apprese. Vanno quindi considerati quali prerequisiti per un efficace approccio al problem solving le abilità di ragionamento induttivo e deduttivo, di logica e di concettualizzazione di modelli astratti dei problemi.

Durante l’insegnamento verranno trattati i seguenti argomenti, con la relativa durata in ore: • Ripasso del linguaggio C (3h) • Strutture dati statiche e dinamiche e loro realizzazione in C (12h) o allocazione di memoria statica, su stack, e dinamica o strutture linkate o strategie per scegliere la struttura dati o introduzione a strutture dati per blockchain • Modularità e realizzazione modulare di algoritmi e strutture dati (8h) o il modello implementazione-interfaccia-client o la realizzazione di un programma C con più sorgenti e header file o utilizzo elementare di strumenti di sviluppo e debug: es. make, gdb, cvs • Ricorsione e programmi ricorsivi (9h) o il concetto di ricorsione o funzioni matematiche ricorsive o procedure ricorsive semplici o backtrack e implementazione della ricorsione o ordinamenti ricorsivi (mergesort, quicksort, heapsort) o equazioni alle ricorrenze • Dati astratti, collezioni di dati e ADT (8h) o esempi modulari di strutture composte quali vettori di liste, multiliste o liste, stack, code FIFO, code generalizzate, code a priorità, heap • Paradigmi algoritmici (10h) o divide et impera o il paradigma della programmazione dinamica o il paradigma greedy • Problem solving (10h) o strategie di analisi e di definizione di strutture dati e algoritmi o problemi di ricerca e di ottimizzazione o tecniche di esplorazione dello spazio delle possibilità basate su calcolo combinatorio e ricorsione • Strutture dati per tabelle di simboli (7h) o Alberi Binari di Ricerca o Tabelle di hash • Teoria dei grafi (13h) o rappresentazione dei grafi o visite in profondità e ampiezza e loro applicazioni o cammini minimi o alberi ricoprenti minimi.

Le lezioni (65h) sono comprensive di esercitazioni integrate. Nel corso delle lezioni verranno impartite le conoscenze elencate nel programma dell’insegnamento, debitamente esemplificate. I laboratori (15h) sono coordinati con le lezioni per consolidare le nozioni apprese e sviluppare le abilità individuali di problem-solving. Alcuni dei laboratori possono essere valutati e dare adito ad un bonus di al massimo 2/30 incluso nella valutazione finale. Possono essere proposte a gruppi particolarmente qualificati e motivati attività addizionali quali challenge, approfondimenti su argomenti specifici etc.

Testi di riferimento: • Deitel & Deitel, ‘Corso completo di programmazione C’, Apogeo, 2010 • P. Camurati, S. Quer, ‘Algoritmi e Programmazione: richiami di teoria con esercizi svolti’, CLUT, IV edizione, 2017 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Ricorsione e problem-solving: strategie algoritmiche in linguaggio C’, Apogeo, 2022 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Puntatori e strutture dati dinamiche: allocazione della memoria e modularità in linguaggio C’, Apogeo, 2016 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Algoritmi in pratica: da specifiche a codice C', Apogeo, 2018 Altri testi suggeriti: • R. Sedgewick, ‘Algoritmi in C’, IV edizione, Pearson, 2015 • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, ‘Introduzione agli Algoritmi e alle Strutture Dati’, III edizione, Mc-Graw Hill, 2010 • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, ‘Introduction to Algorithms’, fourth edition, The MIT Press, 2022 (in inglese) • P. Crescenzi, G. Gambosi, R. Grossi, ‘Strutture di dati e algoritmi’, Pearson Addison-Wesley 2006 • R. Sedgewick, K. Wayne, ‘Algorithms Part I & II’, www.coursera.org (in inglese) • A. Bertossi, A. Montresor, ‘Algoritmi e strutture di dati’, Città Studi edizioni, 2014 Materiale didattico a disposizione su Web: • trasparenze proiettate in aula • esercizi e soluzioni • laboratori risolti e commentati • testi di esami degli insegnamenti Algoritmi e Strutture Dati e Algoritmi e Programmazione

Slides; Libro di testo; Esercizi; Esercizi risolti; Esercitazioni di laboratorio; Esercitazioni di laboratorio risolte; Video lezioni tratte da anni precedenti; Strumenti di collaborazione tra studenti;

Modalità di esame: Prova orale obbligatoria; Prova scritta in aula tramite PC con l'utilizzo della piattaforma di ateneo;

Exam: Compulsory oral exam; Computer-based written test in class using POLITO platform;

... Struttura dell’esame L’esame, di durata massima 2h30, si compone di: • esame scritto suddiviso in 2 parti in sequenza: teoria (50 minuti) e programmazione (max 100 minuti) • esame orale obbligatorio. Esame scritto • teoria: svolgimento di esercizi relativi all’applicazione di algoritmi a semplici problemi (max 12 punti) • programmazione: 2 modalità alternative: o orientata al progetto: progettazione e realizzazione di un programma in grado di risolvere un problema (max 18 punti) o orientata alla padronanza del C avanzato (puntatori, allocazione dinamica, ricorsione), delle strutture dati e degli algoritmi fondamentali (max 12 punti) La preparazione richiesta per entrambe le parti è la stessa. Esame orale • accertamento delle conoscenze acquisite in termini di comprensione dei concetti e di loro esposizione, scrittura di codice C atto alla risoluzione di problemi di complessità compatibile con la durata dell’esame. Modalità di svolgimento dell’esame scritto L’esame scritto sarà a risposta aperta o chiusa. Le 2 parti (teoria e programmazione) saranno svolte in sequenza. L'esame scritto sarà svolto in aula su PC personale con piattaforma di ateneo e Lockdown Browser. In caso di problemi tecnici sarà svolto su carta. Materiale consultabile durante lo scritto: I docenti indicheranno di volta in volta le modalità di consultazione, eventualmente online, di riferimenti per il linguaggio C, come pure l'utilizzo di interfacce (file header) per librerie personali. NON è possibile consultare altri testi, appunti, dispense, etc. NON è possibile utilizzare supporti di tipo elettronico oltre al PC (cellulari, palmari, portatili, etc.) Comportamento in caso di problemi tecnici per esame scritto in presenza Nel caso insorgano problemi in fase di esame lo studente avverte immediatamente i docenti che vigilano. Comunicazione con i docenti durante l’esame scritto in presenza sono presenti docenti che vigilano cui lo studente si può rivolgere. Al termine dello scritto di programmazione, lo studente riceve tramite la piattaforma di ateneo un file .pdf con il suo elaborato. In seguito deve caricare sul Portale entro tre giorni dalla data dello scritto: • una relazione (max 3 pagine) sulla soluzione adottata (strutture dati, algoritmo, etc.) • una copia del programma corretto, con evidenziate le modifiche rispetto al programma consegnato. Qualora lo studente non carichi il materiale indicato entro la data prevista, la prova scritta non viene corretta. Criterio di ammissione all'orale: votoTeoria ≥ soglia1 && votoC ≥ soglia2 && votoTeoria + votoC ≥ 15/30 soglia1 e soglia2 definite di volta in volta in funzione della difficoltà degli esercizi. L'esame orale si svolge indicativamente 7-10 giorni dopo lo scritto. Il calendario viene reso disponibile in contemporanea alla pubblicazione degli esiti dell'esame scritto. Modalità di svolgimento dell’esame orale L’esame orale si svolge di norma mediante l’uso di Virtual Classroom, disponibile sulla pagina dell’insegnamento. Quando invitato dai docenti, lo studente dovrà entrare nella Virtual Classroom e identificarsi mediante documento che verrà confrontato con la foto disponibile nell’elenco studenti dell’insegnamento. Un estraneo alla Commissione d’esame sarà presente e/o l’esame sarà registrato. Lo studente deve dichiarare che non sta usando alcuno strumento di ausilio e che nella stanza non vi è alcuna persona di supporto. Valutazione finale La valutazione è complessiva ed integra, non media, i risultati nelle singole parti di cui consta l’esame. Eventuali bonus per laboratori valutati non sono additivi, bensì inclusi nella valutazione complessiva.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.