Fondamenti di Informatica

Finalità del corso

L’obiettivo principale del corso è prendere confidenza con il "pensiero algoritmico", attraverso un processo di astrazione e modellazione di problemi a cui trovare soluzioni procedurali. Centrale è lo studio e lo sviluppo di algoritmi e il ragionare sulle loro proprietà, tra cui correttezza, efficienza, ottimalità. Il corso quindi si propone di presentare i concetti di base relativi all’elaborazione automatica dell’informazione. Tali concetti sono sia analizzati da un punto di vista teorico che presentati in pratica. Scopo del corso è anche l’apprendimento di un linguaggio di programamazione per la realizzazione degli algoritmi. Il linguaggio utilizzato è il Python.

Il programma

INTRODUZIONE AL CORSO - Informatica: definizione e cenni storici - Le nozioni di problema, algoritmo e programma. L’organizzazione del calcolatore. Linguaggi di programmazione. Processi e processori. La macchina a registri illimitati URM come modello di macchina universale. Semplici algoritmi e programmi per la URM.

PARTE I - ARCHITETTURA DEI CALCOLATORI

Obiettivo: Fornire i concetti principali relativi alla rappresentazione dell’informazione, all’architettura di un calcolatore ed ai linguaggi di programmazione.

Codifica binaria dell’informazione: Sistemi numerici posizionali a base fissa. Conversioni di base. Rappresentazione di numeri negativi in modulo e segno e in complemento a due. Rappresentazione di numeri reali in virgola mobile normalizzata. Operazioni aritmetiche. Algebra di Boole e principali funzioni logiche. Codifica caratteri e immagini. Architettura dei calcolatori: Modello di von Neumann. Linguaggio macchina. Il linguaggio assemblatore. Linguaggi di alto livello. Compilatori e iterpreti.

PARTE II - PROGRAMMAZIONE

Obiettivo: introdurre i costrutti fondamentali del linguaggio di programmazione Python.

Ambiente di programmazione Python: compilatore e interprete. Struttura di un programma Python. Concetto di variabile. Operazioni elementari: lettura, scrittura, assegnazione e confronto. Tipi semplici, rappresentazione interna e operazioni. Espressioni numeriche e logiche. Diagrammi di flusso. Pseudo-codice. Struttura di controllo se-allora-altrimenti. Cicli con pre-condizione e post-condizione. Progettazione di algoritmi con controlli e cicli. Costrutti base del Python (if-else, if-elif-else, for, while).
Tipi strutturati: stringhe, liste, tuple, pile, code, insiemi, dizionari, matrici, record. Algoritmi di base su tipi strutturati (lettura, scrittura, ricerca,inserimento e cancellazione di elementi). Riferimenti a tipi strutturati. Tipo file. Primitive per la gestione sequenziale dei files.
Funzioni: concetto di sottoprogramma. Progettazione top-down. Dichiarazione di funzioni. Passaggio di parametri per valore e per riferimento; variabili globali e locali. Visibilità e ciclo di vita delle variabili. Mascheramento di variabili. Stack e record d’attivazione. Ricorsione.

PARTE III - COMPLESSITA’ E ALGORITMI

Obiettivo: introdurre alla complessità computazionale, studiare alcuni algoritmi di base e valutare la loro complessità, introdurre le strutture dati collegate (con la loro realizzazione in Python) e valutazione di alcuni algoritmi di base relativi.
Complessità dei programmi: funzioni calcolabili e non calcolabili. Efficienza dei programmi e modelli di costo. Caso migliore, caso peggiore, e caso medio. Complessità computazionale. Notazione asintotica. Delimitazioni alla complessità di un problema.
Algoritmi fondamentali: Ricerca sequenziale. Ricerca binaria. Inserimento e cancellazione in un array ordinato. Algoritmi di ordinamento: analisi della complessità nel caso migliore e nel caso peggiore. Introduzione agli alberi e loro rappresentazione. Algoritmi di visita di alberi binari.

Testo di riferimento

Concetti di informatica e fondamenti di Python, C. Horstmann, R.D. Necaise, Apogeo, 2014

Testi integrativi:

- Informatica arte e mestiere, D. Mandrioli et al., McGrawHill, 2014
- Programmazione in Python - Seconda edizione, Kenneth A, Lambert, Apogeo, 2018

Altro materiale fornito dal docente

Lucidi del corso
Dispensa del docente sulla macchina URM
Codice programmi in Python

Tutoraggio

Il corso prevede 30 ore aggiuntive di tutoraggio che saranno tenute dal Dott. Francesco Gallo . Nella sezione teaching della sua pagina personale è presente un link al materiale didattico.