Vai al contenuto principale
Logo Università
Logo di Corso di laurea in Informatica

Dipartimento di Informatica

Corso di laurea in Informatica

Seguici su

Logo di Corso di laurea in Informatica
Oggetto:
Oggetto:

Algoritmi e Strutture Dati

Oggetto:

Algorithms and Data Structures

Oggetto:

Anno accademico 2023/2024

Codice attività didattica
MFN0597
Docenti
Andras Horvath (Corso A)
Ugo De' Liguoro (Corso B)
Diego Magro (Turno 1)
Giorgio Audrito (Turno 2)
Gian Luca Pozzato (Turno 3)
Roberto Micalizio (Turno 4)
Corso di studio
[008707] Laurea in Informatica
Anno
2° anno
Periodo
Secondo semestre
Tipologia
Caratterizzante
Crediti/Valenza
9 CFU - Numero di ore - Number of hours: 48 (in aula) + 30 (in laboratorio)
Crediti percorso 24 CFU
2
SSD attività didattica
INF/01 - informatica
Erogazione
Tradizionale
Lingua
Italiano
Frequenza
Facoltativa
Tipologia esame
Scritto più orale obbligatorio
Prerequisiti
Si presuppone che lo studente sia a conoscenza delle basi della programmazione e dei linguaggi di programmazione C e Java; che sia in possesso delle nozioni elementari della matematica del discreto, del continuo, e della logica matematica.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): Programmazione I & Laboratorio, Programmazione II & Laboratorio, Matematica Discreta, Analisi Matematica, Logica Matematica, Sistemi Operativi (in particolare l'apprendimento del linguaggio C).
Students are expected to have basic knowledge and competence of the C and Java programming languages. Elementary knowledge of mathematics, both discrete and continuous, and of mathematical logic are also required.
Preparatory Courses (providing the expected entry skills): Program course I and II and labs; Discrete Mathematics; Mathematical Analysis, Mathematical Logic, Operating Systems.
Oggetto:

Sommario insegnamento

Oggetto:

Avvisi

DSA o Disabilità: Sostegno e Accoglienza in UniTO e supporto in sede di Esame
Oggetto:

Obiettivi formativi

L’insegnamento ha lo scopo di introdurre i concetti e le tecniche fondamentali per l’analisi e la progettazione di algoritmi, che sono alla base dello sviluppo del software. Gli obiettivi dell'insegnamento degli algoritmi fanno parte degli Obiettivi formativi specifici del CdS in Informatica (L31), in particolare sono tra quelli relativi all'area informatica di base. Gli studenti acquisiranno conoscenze circa l’analisi di correttezza e complessità computazionale degli algoritmi, sulle strutture dati per la rappresentazione dell’informazione, sulle tecniche di problem-solving mediante lo sviluppo di algoritmi efficienti. L’insegnamento è supportato da un laboratorio che ne costituisce parte integrante, finalizzato alla realizzazione e sperimentazione degli algoritmi e delle strutture dati mediante un linguaggio imperativo ed uno object-oriented

The course is an introduction to the fundamental concepts and techniques for the analysis and the design of algorithms, that is at the heart of software development. The objectives of the course are among those specific to the curriculum LM31, more precisaly in the basic area of computer science. Students will acquire knowledge about the correctness and complexity analysis of algorithms, data structures representing information and problem-solving techniques to efficiently solve computational problems. The course is supported by a laboratory that constitutes an essential part of it. It is aimed at implementing and experiencing algorithms using procedural and object-oriented programming languages.

Oggetto:

Risultati dell'apprendimento attesi

CONOSCENZA E CAPACITÀ DI COMPRENSIONE Acquisizione di conoscenze teoriche e operative relative a problemi algoritmici di base e della loro risoluzione mediante il disegno di algoritmi e di strutture dati efficienti, nonché la capacità di analizzare le soluzioni adottate sotto il profilo della loro correttezza logica e complessità computazionale.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE Acquisizione della capacità di applicare le conoscenze teoriche a problemi concreti nei vari ambiti della programmazione di sistemi informatici, tanto producendo il codice dei programmi quanto utilizzando librerie software preesistenti, con particolare attenzione al rigore metodologico, alla chiarezza e verificabilità delle soluzioni adottate nonché alla loro efficienza ed affidabilità.

AUTONOMIA DI GIUDIZIO Acquisizione di consapevole autonomia di giudizio con riferimento alla valutazione delle diverse soluzioni teoriche che si possono adottare e del loro impatto sulle applicazioni pratiche.

ABILITÀ COMUNICATIVE Acquisizione di competenze e strumenti per la comunicazione nella forma scritta e orale per documentare le soluzioni adottate in modo tecnicamente rigoroso.

CAPACITÀ DI APPRENDIMENTO Acquisizione di capacità autonome di apprendimento e di autovalutazione della propria preparazione, atte ad intraprendere gli studi successivi con un alto grado di autonomia.

 

KNOWLEDGE AND UNDERSTANDING Acquisition of theoretical and applicative skills concerning basic computational problems and their solution by designing efficient algorithms and data structures; acquisition of the ability to analyse the adopted solutions with respect to their logical correctness and computational complexity.

APPLYING KNOWLEDGE AND UNDERSTANDING Acquisition of the ability to apply theoretical knowledge to practical issues in various areas of programming computer systems, both producing new code and using preexistent libraries, with special regard to methodological rigour, clarity and verifiability of the adopted solutions and their efficiency and affordability.

MAKING JUDGEMENTS Acquisition of aware judgment autonomy concerning the evaluation of several theoretical solutions that are available and of their impact on the practical applications.

COMMUNICATION SKILLS Acquisition of oral and written communication skills and expertise as well as the ability to document the adopted solutions in a technically rigorous way.

LEARNING SKILLS Acquisition of autonomous learning capacity and self-assessment of its
preparation, in order to undertake subsequent studies with a high degree of autonomy.

 

Oggetto:

Programma

Programma

  • Problemi e algoritmi: risolubilità, correttezza, complessità.
  • Analisi computazionale e complessità asintotica
  • Algoritmi di ordinamento
    • Algoritmi elementari quadratici
    • Divide et impera: mergesort e quicksort
    • Risoluzione di relazioni di ricorrenza
    • Limiti inferiori per l’ordinamento
  • Programmazione dinamica
    • Massima sottosequenza comune
  • Strutture dati
    • Strutture concrete: array, liste, tabelle hash
    • Strutture astratte: pile, code, dizionari
    • Code di priorità, heapsort
    • Analisi ammortizzata, cenni
  • Alberi
    • Definizione e visita
    • Alberi di ricerca
    • Alberi rosso-neri
  • Grafi
    • Definizione e visita
    • Ordinamento topologico e componenti fortemente connesse
    • Algoritmi greedy: alberi di copertura minima
    • Cammini minimi: algoritmo di Dijkstra

Syllabus

  • Problems and algorithms
  • Asyntotic notation and computational complexity
  • Sorting algorithms
    • Quadratic sorting algorithms
    • Divide et impera: mergesort and quicksort
    • Solution of recurrence relations
    • Lower bounds to the sorting problem
  • Dynamic programming
    • Largest common subsequence
  • Data structures
    • Concrete structures: arrays, lists, hash tables
    • Abstract structures: stacks, queues, dictionaries
    • Prority queues, heapsort
    • Amortized analysis
  • Trees
    • Definition and visit
    • Search trees
    • Red-black trees
  • Graphs
    • Definition and visit
    • Topological sort and strongly connected components
    • Greedy algorithms: minimum spanning trees
    • Shortest paths, Dijkstra algorithm.
Oggetto:

Modalità di insegnamento

Sono previste 48 ore di lezione frontale ed esercitazioni in aula, e 24 ore di attività guidata dai docenti in laboratorio. Per le indicazioni bibliografiche, la distribuzione di note ed altro materiale didattico si farà uso della piattaforma e-learning Moodle, e per la consegna e valutazione degli elaborati delle esercitazioni sarà impiegato un repository GitLab; si richiede agli studenti l’iscrizione ad entrambe le piattaforme.

Frontal lessons and exercises will be scheduled in the amount of 48 hours, plus 24 hours of tutored activities in the laboratory. The e-learning platform Moodle will be employed for distributing bibliographies, handouts and further didactic material and a repository on the GitLab platform will be used for assignments and their grading; therefore students are required to sign in to the course page on both platforms.

Oggetto:

Modalità di verifica dell'apprendimento

L'esame di Algoritmi e strutture dati consiste in una prova scritta, somministrata mediante la piattaforma Esami, ed in una discussione orale del progetto di laboratorio. Il superamento dello scritto permette di accedere alle prove orali della sessione in cui è stato superato lo scritto. Nel caso in cui questa seconda prova non venga superata entro i termini della sessione, lo scritto dovrà essere ripetuto. Il voto sarà la media pesata dei voti ottenuti nelle due prove scritta ed orale, valutate in 30+1 esimi, essendo comunque necessario il raggiungimento della sufficienza in entrambe le prove.

The exam of the course Algorithm and data structures consists of a written test, that will be available by means of the platform Esami, and of an oral discussion of the project assigned in the laboratory. The passing of the written exam must precede the oral discussion of the laboratory project, and the latter must take place in the same oral session. In case the oral exam is not passed, the written test must be repeated in a subsequent session. The registered grade will be the weighted average of the grades of the two parts, 2/3 and 1/3 for the written and oral exams respectively. To pass the exam the grades of both tests must be greater or equal to the threshold of 18/30.

 

Testi consigliati e bibliografia



Oggetto:
Libro
Titolo:  
Introduzione agli algoritmi e strutture dati (ed. terza)
Anno pubblicazione:  
2010
Editore:  
McGraw-Hill
Autore:  
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, , Clifford Stein
Obbligatorio:  
No


Oggetto:
Libro
Titolo:  
Concetti di informatica e fondamenti di Java (quinta ed. o successive)
Anno pubblicazione:  
2010
Editore:  
Apogeo
Autore:  
Cay S. Horstmann
Obbligatorio:  
No


Oggetto:

Insegnamenti che mutuano questo insegnamento

Registrazione
  • Chiusa
    Apertura registrazione
    01/03/2023 alle ore 00:00
    Chiusura registrazione
    29/02/2024 alle ore 23:55
    Oggetto:
    Ultimo aggiornamento: 11/09/2023 08:41
    Location: https://laurea-di.campusnet.unito.it/robots.html
    Non cliccare qui!