COMPUTER PROGRAMMING, ALGORITHMS AND DATA STRUCTURES
Stampa
Anno immatricolazione
2021/2022
Anno offerta
2021/2022
Normativa
DM270
SSD
INF/01 (INFORMATICA)
Dipartimento
DIPARTIMENTO DI MATEMATICA 'FELICE CASORATI'
Corso di studio
ARTIFICIAL INTELLIGENCE
Curriculum
PERCORSO COMUNE
Anno di corso
Periodo didattico
Annualità Singola (04/10/2021 - 17/06/2022)
Crediti
12
Ore
110 ore di attività frontale
Lingua insegnamento
INGLESE
Tipo esame
SCRITTO E ORALE CONGIUNTI
Docente
FERRARI STEFANO (titolare) - 6 CFU
DONDI PIERCARLO - 6 CFU
Prerequisiti
None
Obiettivi formativi
The course introduces the student to programming in Python and solving computational problems using algorithms. The main notions of imperative programming (variables, expressions, loops, functions, recursion, input / output) and the fundamental elements of object-oriented programming are provided. The course also illustrates the analysis and design of algorithms (asymptotic analysis, dynamic programming, greedy algorithms), presents the most important data structures (arrays, lists, trees, graphs) and the algorithms that work on them.
Programma e contenuti
Module 1: Computer Programming

Computer science overview
- logic circuits
- computer architecture
- operating system
- computer network
- information systems

Imperative programming
- top-down / bottom-up programming
- values, variables, expressions
- I/O instructions
- constructs, selection, loop
- functions, recursion
- I/O file
- libraries

Object-oriented programming
- fields and methods
- data types (arrays, lists)

++++++++++++++++++++++++

Module 2: Algorithms and Data Structures

Introduction
- concept of algorithm and structured data
- notion of cost (time / space)

Complexity measure
- asymptotic notations for cost functions
- methods of analysis (worst case, average, best case)

Analysis of recursive algorithms
- abstract data types (stacks, queues, trees)
- tree visit algorithms

Sorting algorithms
- SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort
- cost of the order (comparison / exchanges)
- lower bound

Search algorithms
- type of dictionary data
- binary search trees
- hash table

Algortmi on graphs
- visit
- greedy techniques
- coverage
- shortest path
Metodi didattici
Frontal lessons and laboratories
Testi di riferimento
Think Python: How to Think Like a Computer Scientist by Allen B. Downey
Beijing: O'reilly Media

Problem Solving With Algorithims and Data Structures Using Python, 2nd edition, By Brad Miller and David Ranum
Franklin Beedle & Assoc

(Optional) Introduction to Algorithms, 3rd edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
The MIT Press
Modalità verifica apprendimento
Written test
Altre informazioni
Obiettivi Agenda 2030 per lo sviluppo sostenibile