2021/2022

2021/2022

DM270

INF/01 (INFORMATICA)

DIPARTIMENTO DI MATEMATICA 'FELICE CASORATI'

ARTIFICIAL INTELLIGENCE

PERCORSO COMUNE

1°

Annualità Singola (04/10/2021 - 17/06/2022)

12

110 ore di attività frontale

INGLESE

SCRITTO E ORALE CONGIUNTI

FERRARI STEFANO (titolare) - 6 CFU
DONDI PIERCARLO - 6 CFU

None

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.

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

Frontal lessons and laboratories

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

Written test