ECTS - University of Pisa
Scheda programma d'esame
PROGRAMMING AND ALGORITHM DESIGN
NADIA PISANTI
Academic year2020/21
CourseCOMPUTER SCIENCE
Code735AA
Credits15
PeriodSemester 1 & 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
PROGRAMMAZIONE E ALGORITMICAINF/01LEZIONI120
ANNA BERNASCONI unimap
NADIA PISANTI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) e di programmazione 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.
Knowledge

The goal of the course is to introduce (basic) data structures and algorithmic and programming techniques that allow the student to solve problems on sequences, lists, trees and graphs with efficient (in time and in space) methods. Moreover, we will also discuss analythic methods for performances evalutaions of algorithms, as well as computability limitations.
Modalità di verifica delle conoscenze

Le conoscenze dello studente saranno verificate sulla base della sua capapcità di discutere e utilizzare i concetti e le tecniche più importanti presentati nel corso.

 
Assessment criteria of knowledge

The student's knowledge will be verified by means of hir or her hability to discuss and use the methods and the techniques introduced in the course.
Capacità

Capacità fondamentali nel progetto di algoritmi e strutture dati, e nella valutazione degli algoritmi.

 
Skills

Fundamental skills in the design of algorithms and data structures, in programming tecniques, and in algorithms evaluation.
Modalità di verifica delle capacità

Esame scritto ed eventuale orale
Assessment criteria of skills

Mandatory written exam and optional oral exam
Comportamenti

Gli studenti saranno in grado di valutare le performance di algoritmi di base prima della loro implementazione, di progettare algoritmi efficienti per la risoluzione di problemi, e di conoscere problemi difficili per cui le scelte algoritmiche di progetto possono influenzare pesantemente il risultato.
Behaviors

Students will learn how to evaluate the performances of algorithms independently from their implementation, how to design efficient method to solve computational problems.
Modalità di verifica dei comportamenti

Esercitazioni di autovalutazione
Assessment criteria of behaviors

Self-evaluation assignmnts
Prerequisiti (conoscenze iniziali)

Fondamenti di matematica discreta, incluse sommatorie, logaritmi, serie numeriche.
Prerequisites

Basic Discrete Mathematics, including sums, logarithms, numerical series.
Corequisiti

Principio di induzione, dimostrazioni per induzione e per assurdo. Grafi.
Co-requisites

(Principle of) induction, proofs by induction and by contradiction
Programma (contenuti dell'insegnamento)
  • Struttura di un calcolatore e ambienti di sviluppo. Analisi asintotica del costo computazionale. Rappresentazione delle informazioni. Problemi computazionali e algoritmi di risoluzione.
  • Controllo delle operazioni e del flusso all’interno di un programma. Problem solving su array. 
  • Blocco e struttura dei programmi. Funzioni, passaggio dei parametri. Ricorsione,
  • Algoritmi per ordinamento e ricerca.
  • Strutture di dati dinamiche. Liste. Code e pile. Tabelle hash e dizionari.
  • Divide et impera, programmazione dinamica, algoritmi greedy.  
  • Algoritmi per alberi e grafi.
  • Cenni di calcolabilità e di classi di complessità.
Syllabus
  • Computer Structure and development environments. Asyntotic analysis of computational costs. Information representations. Computational Problems and Algorithms.
  • Operations and flux control and within a program. Problem solving on arrays.
  • Blocks and programs structures. Functions, parameters passing. Recursion.
  • Algorithms for sorting and searching.
  • Dynamic Data Structures. Lists, Queues, Stacks. Hash Tables and Dictionaries.
  • Divide et impera, dynamic programming, greedy algorithms.
  • Algorithms on trees and on graphs.
  • Basic calcolability and complexity classes.
Bibliografia e materiale didattico

Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Altri riferimenti verrano indicati e pubblicati sulla pagina web del corso.

 
Bibliography

Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

I. Mastroeni, C. Priami. Semantica operazionale. Strumenti e applicazioni. CEDAM, 1999. 
Indicazioni per non frequentanti

Pr l'anno accademico 2020/2021, le leziopni saranno tenute on-line
Non-attending students info

In academic year 2020-2021 lectures will be on-line
Modalità d'esame

Prova Scritta ed eventuale orale
Assessment methods

Mandatory written exam and optional oral exam
Pagina web del corso

https://classroom.google.com/u/0/c/MTU5MjI1OTAxNDA5
Class web page

https://classroom.google.com/u/0/c/MTU5MjI1OTAxNDA5
Updated: 02/02/2021 16:58