logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
  • 086065 - ALGORITMI E PRINCIPI DELL'INFORMATICA (MOD 2 - INFORMATICA 3)
Docente Comai Sara
Cfu 5.00 Tipo insegnamento Modulo Di Corso Strutturato

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - MI (358) INGEGNERIA INFORMATICAIOAAZZZZ086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
IOLAZZZZ086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA
IORAZZZZ086067 - ALGORITMI E PRINCIPI DELL'INFORMATICA

Obiettivi dell'insegnamento

Il modulo di algoritmi ha lo scopo di presentare i concetti fondamentali dell’algoritmica, ovvero quella branca dell’informatica che si occupa della definizione e la progettazione degli algoritmi, l’analisi della loro efficienza e complessità. Verranno introdotte strutture dati lineari (liste, pile, code) e non lineari (alberi, grafi) e numerosi algoritmi ad esse collegati, strutture dati avanzate (alberi B/B+, heap, tabelle hash, ecc.). Vengono forniti cenni sulle metodologie di progettazione di algoritmi (divide et impera, programmazione dinamica, metodo greedy, backtracking). il corso intende sviluppare l'attitudine ad affrontare problemi nuovi e non ben precisati e ricavarne un modello preciso e adatto all'individuazione della miglior (o adeguata) soluzione.


Risultati di apprendimento attesi

 

Descrittori di Dublino

Risultati di apprendimento attesi

Conoscenza e comprensione

A seguito del superamento dell’esame lo studente conosce:

  • I principi di base della progettazione e dell’analisi degli algoritmi e delle strutture dati.

Capacità di applicare conoscenza e comprensione

Attraverso le esercitazioni su problemi specifici, e a seguito del superamento dell’esame, lo studente acquisisce:

  • Capacità di applicare, adattare e valutare in situazioni pratiche algoritmi e strutture dati.

Autonomia di giudizio

A seguito del superamento dell’esame lo studente è in grado di:

  • Scegliere ed eventualmente ideare opportune strutture dati e algoritmi per il problema che sta considerando.

Capacità di apprendimento

  • Gli studenti saranno in grado di valutare in maniera critica algoritmi e strutture dati.
  • Gli studenti saranno in grado di creare nuovi algoritmi e nuove strutture dati.

 

 


Argomenti trattati

Programma delle lezioni e delle esercitazioni

Teoria della complessità

  • Nozioni e notazioni fondamentali per l'analisi di complessità
  • I modelli di calcolo e le relazioni tra le loro complessità computazionali

Algoritmi e strutture dati

  • Introduzione agli algoritmi e strutture dati. Analisi di complessità di algoritmi e strutture dati. 
  • Strutture dati e algoritmi fondamentali: Liste, Code e Pile, Alberi binari e generici
  • Algoritmi di ordinamento
  • Algoritmi di ricerca. Hashing e Indicizzazione
  • Grafi, loro rappresentazione e gestione

Argomenti avanzati

  • Tecniche di progettazione di algoritmi
  • Problemi NP-completi

  

 


Prerequisiti

Il programma del corso presuppone una buona conoscenza di tutti gli argomenti trattati nel corso di Fondamenti di Informatica.


Modalità di valutazione

L'esame consiste in un'unica prova scritta sull'intero programma del corso (su entrambi i moduli). 

 

Modalità di verifica

Descrizione

Risultato di apprendimento perseguito (descrittore di Dublino)

Esame scritto

  • Risoluzione di problemi numerici: calcolo della complessità
  • Risoluzione di esercizi di tipo progettuale: progettazione di algoritmi e strutture dati
  • Domande di carattere teorico a risposta aperta sugli argomenti del corso

1, 2

1, 2, 3, 5

1, 2, 5

 


Bibliografia
Risorsa bibliografica facoltativaAlan A. Bertossi, Alberto Montreso, Algoritmi e strutture di dati, Editore: CittàStudi, Anno edizione: 2014, ISBN: 978-8825173956
Risorsa bibliografica facoltativaCormen, Leiserson, Rivest, Stein, Introduction to Algorithms, Editore: Mit Pr, Anno edizione: 2009, ISBN: 978-0262033848

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
20:00
30:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
25/10/2020