Salta al contenuto principale della pagina

ALGORITMI E STRUTTURE DATI

CODICE 80298
ANNO ACCADEMICO 2022/2023
CFU
  • 12 cfu al 1° anno di 8759 INFORMATICA (L-31) - GENOVA
  • SETTORE SCIENTIFICO DISCIPLINARE INF/01
    LINGUA Italiano
    SEDE
  • GENOVA
  • PERIODO 2° Semestre
    PROPEDEUTICITA
    Propedeuticità in uscita
    Questo insegnamento è propedeutico per gli insegnamenti:
    • INFORMATICA 8759 (coorte 2022/2023)
    • ANALISI E PROGETTAZIONE DI ALGORITMI 80306
    MATERIALE DIDATTICO AULAWEB

    PRESENTAZIONE

    Il corso di Algoritmi e Strutture Dati ha come scopo l'ampliamento delle conoscenze e delle capacità inerenti la programmazione in piccolo mediante linguaggi imperativi; esso fornisce le basi per progettare algoritmi efficienti e per sviluppare strutture dati che permettano un’organizzazione efficace delle informazioni.

    OBIETTIVI E CONTENUTI

    OBIETTIVI FORMATIVI

    Ampliare le conoscenze e le capacità inerenti la programmazione in piccolo mediante linguaggi imperativi, fornendo le basi per progettare algoritmi corretti ed efficienti,  e sviluppare strutture dati che permettano un’organizzazione efficace ed efficiente delle informazioni.

    OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

    Al termine dell'insegnamento, lo studente sarà in grado di:

    - calcolare la complessità di algoritmi notevoli (ordinamento, aggiunta, ricerca e modifica di elementi in una struttura dati) in modo da individuare l'algoritmo più efficiente

    - progettare l'interfaccia di un tipo di dato

    - implementare il tipo di dato con strutture dati diverse che comprendono strutture indicizzate e collegate

    - apprezzare la differenza nella efficienza delle funzioni previste dal tipo di dato al variare della struttura dati utilizzata

    MODALITA' DIDATTICHE

    Tradizionale: Corso organizzato in lezioni frontali ed esercitazioni pratiche che si iniziano in laboratorio e si completano come compito per casa.

    PROGRAMMA/CONTENUTO

    Modelli di calcolo e metodologie di analisi degli algoritmi: criteri di costo, notazione asintotica, metodi di analisi, analisi di complessità  degli algoritmi ricorsivi. Esempi di sviluppo ed analisi di algoritmi.
    Algoritmi di ordinamento: insertion sort, selection sort, bubble sort, mergesort, quicksort (con analisi di complessità)
    Strutture dati elementari: array e liste, tipo di dato pila e coda, tipo di dato dizionario ed implementazione mediante liste, alberi, alberi binari, rappresentazioni indicizzate e collegate per alberi binari e non, alberi quasi completi, visite di alberi in profondità ed in ampiezza.
    Alberi  di ricerca: Alberi binari di ricerca, alberi di ricerca come implementazione del tipo di dato dizionario, cenni ad alberi bilanciati.
    Code con priorità: tipo di dato, implementazione mediante liste, heap, implementazione di code con priorità mediante heap binari.
    Tabelle di hash: implementazione con liste di collisione e con indirizzamento aperto.
    Grafi: definizioni, strutture dati, primitive per l'interrogazione e l'aggiornamento di grafi visite di grafi in profondità ed in ampiezza, esempi di applicazione degli algoritmi di visita di un grafo.
    Laboratorio: esercitazioni in C++ relative agli argomenti del corso

    TESTI/BIBLIOGRAFIA

    Tutti gli argomenti previsti dal programma vengono trattati approfonditamente a lezione. Per la comprensione degli argomenti e la preparazione dell'esame è quindi indispensabile disporre delle slide preparate dai docenti e rese disponibili con ampio anticipo, e degli appunti presi durante le lezioni in aula.

    Il codice C++ reso disponibile dai docenti è parte integrante del materiale didattico a disposizione degli studenti.

    DOCENTI E COMMISSIONI

    Commissione d'esame

    VIVIANA MASCARDI (Presidente)

    MATTEO DELL'AMICO

    DANIELE D'AGOSTINO (Presidente Supplente)

    LEZIONI

    Orari delle lezioni

    L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

    ESAMI

    MODALITA' D'ESAME

    Modalità d'esame

    L'esame consiste in una prova scritta e in una prova di laboratorio. Le due prove sono indipendenti tra loro: è possibile prenotarsi e svolgere solo la prova scritta in un appello e prenotarsi e svolgere la prova di laboratorio in un appello successivo, e viceversa. Non è necessario superare una delle due prove per poter sostenere l'altra. La prova scritta prevede una parte iniziale "di sbarramento" che preclude l'accesso sia allo scritto, sia al laboratorio, e può essere superata in uno dei cinque appelli disponibili.

    I voti parziali conseguiti durante un anno accademico "scadono" allo scadere dell'anno: in altre parole, dopo le cinque sessioni d'appello relative all'insegnamento, tutti i voti vengono riazzerati.


    Modalità di valutazione

    Il voto finale si ottiene come somma del voto dello scritto + voto del laboratorio + voto delle esercitazioni valutate svolte durante l'anno. Tale somma viene arrotondata all'intero più vicino. 

    MODALITA' DI ACCERTAMENTO

    Le varie parti d'esame sono state accuratamente progettate dei docenti in modo da verificare se lo studente è in grado di

    - calcolare la complessità di algoritmi notevoli (ordinamento, aggiunta, ricerca e modifica di elementi in una struttura dati) in modo da individuare l'algoritmo più efficiente

    - progettare l'interfaccia di un tipo di dato

    - implementare il tipo di dato con strutture dati diverse che comprendono strutture indicizzate e collegate

    - apprezzare la differenza nella efficienza delle funzioni previste dal tipo di dato al variare della struttura dati utilizzata

    I dettagli sulle modalità di preparazione per l’esame e sul grado di approfondimento di ogni argomento verranno dati nel corso delle lezioni, chiarendo di volta in volta la tipologia di esercizi che verranno proposti in sede d'esame per accertare l'acquisizione delle competenze previste sull'argomento trattato. Saranno resi disponibili esempi di testi d'esame degli anni precedenti per permettere agli studenti di comprendere esattamente come viene accertata l'acquisizione delle competenze previste.

    Calendario appelli

    Data Ora Luogo Tipologia Note
    13/06/2023 09:00 GENOVA Scritto
    14/06/2023 09:00 GENOVA Laboratorio
    25/07/2023 09:00 GENOVA Scritto
    26/07/2023 09:00 GENOVA Laboratorio
    05/09/2023 09:00 GENOVA Scritto
    06/09/2023 09:00 GENOVA Laboratorio
    10/01/2024 09:00 GENOVA Scritto
    11/01/2024 09:00 GENOVA Laboratorio
    08/02/2024 09:00 GENOVA Scritto
    09/02/2024 09:00 GENOVA Laboratorio