ITALIANO

• Il computer: hardware and software;
• Ragionamento logico
• Principi di programmazione
• Modelli informatici;
• Sistemi Operativi;
• Reti di computer;
• Internet and WWW;
• I linguaggi di programmazione;
• Linguaggi e applicativi per condurre esperimenti scientifici.

a) Dino Mandrioli, Stefano Ceri, Licia Sbattella, Paolo Cremonesi, Gianpaolo Cugola, “Informatica arte e mestiere” 3/ed, McGraw-Hill, 2008;
b) Harel D., Feldman Y., Algoritmi. Lo spirito dell'Informatica, Springer.

L’obiettivo del corso è fornire allo studente la capacità di comprendere i principi dell'informatica e della programmazione:
* Rappresentazione dei dati
* Computazione, linguaggi e macchine astratte
* Architettura dei sistemi di elaborazione

Le capacità di applicare le conoscenze elencate riguardano lo sviluppo
del cosiddetto "pensiero computazionale":
* Scomposizione di problemi complessi
* Soluzione di problemi tramite ricorsione
* Composizione di oggetti in sistemi complessi
* Modellazione con diversi livelli di astrazione

Abilità Informatiche

Lezioni frontali articolate nei seguenti moduli didattici:
Il computer: hardware and software
Rappresentazione dell’informazione
Elementi di logica
Principi di programmazione
Metodi algoritmici
Modelli Informatici
Correttezza e computabilità
Il Sistema Operativo
Reti di calcolatori e sistemi distribuiti
I servizi Internet
Errori di linguaggio
Rappresentazione schematica di una macchina di Turing deterministica
la Teoria dell’NP-completezza
Linguaggi e applicativi per condurre esperimenti scientifici

La prova orale
- si prefigge l’obiettivo di accertare le capacità di saper descrivere l'architettura di un elaboratore elettronico
- si prefigge l’obiettivo di accertare le capacità di comprensione della rappresentazione binaria dell'informazione
- intende accertare l’apprendimento delle conoscenze di base sulla codifica e le capacità di risoluzione di semplic problemi computazionali.
Si svolgerà
- con un colloquio articolato in domande sugli argomenti:
* Il computer: hardware and software
* Rappresentazione dell’informazione
* Elementi di logica
* Principi di programmazione
* Metodi algoritmici
* Modelli Informatici
* Correttezza e computabilità
* Il Sistema Operativo
* Reti di calcolatori e sistemi distribuiti
* I servizi Internet
* Errori di linguaggio
* Rappresentazione schematica di una macchina di Turing deterministica
* la Teoria dell’NP-completezza
* Linguaggi e applicativi per condurre esperimenti scientifici
atto ad accertare il livello di conoscenze su
- rappresentazione binaria dell'informazione
- architettura di un elaboratore elettronico
- coding e problemi computazionali
raggiunto dallo studente
Sarà valutata in (trentesimi) ed avrà un peso di 50/100 nel risultato finale.
La prova scritta è propedeutica alla prova orale. Si svolgerà presso i locali del Dipartimento di Psicologia e ciascuna prova durerà 1 ora.
Consiste in n° 30 test a risposta multipla, cui verrà assegnata una votazione in trentesimi ed avrà un peso di 50/100 nel risultato finale.
Il superamento dell’esame si otterrà con un voto minimo di 18/30, che scaturisce dalla media aritmetica delle due prove.

1) Il computer: hardware and software (Capitoli 1 e 2 del libro (a)):
• Che cosa è l’informatica?
• Il concetto di Algoritmo
• I Linguaggi per la programmazione di Algoritmi
• Architetture dei sistemi Informatici
• Applicazioni dell’Informatica
• Le aree disciplinari dell’Informatica
• Elementi della macchina di von Neumann
• Codifica dei dati e delle istruzioni di un programma
• Comportamento della macchina di von Neumann
• Esecuzione dei programmi
Che cosa e’ un Computer, Generalità, Tipo di informazioni, Il computer come elaboratore dell’informazione, rappresentazione analogica e rappresentazione digitale, Rappresentazione dell’informazione, Definizioni di simbolo, stringa, alfabeto, linguaggio; Alfabeto di un computer, l’operazione di codifica, Binary Digits, La ridondanza, il bit di parità, Il codice binario, Il codice ASCII, i Sistemi numerici, Sistemi numerici posizionali, Il Sistema decimale, Altri sistemi numerici (più adatti per il computer), Conversioni da una base ad un’altra, la parola macchina, Limitazioni, Memorizzazione, Operazioni Aritmetiche, Somma binaria, Sottrazione binaria, Rappresentazione dei Numeri positivi, Rappresentazione dei numeri negativi, Rappresentazione in Complemento a due e in Modulo e Segno e Problemi, Rappresentazione dei numeri reali in Virgola Mobile; L’hardware, le porte logicheGli Elementi di base di un computer, l’Architettura di von Neumann, il Funzionamento del computer, la CPU: L’ALU, I Registri, La Memoria RAM (Random Access Memory), L’Indirizzamento della RAM, Altre memorie: ROM e Cache; Il BUS
Le unità periferiche (I/O devices), Le periferiche di input.
2) Ragionamento logico
Proposizioni, I tre principi della logica, Negazione, Congiunzione, Disgiunzione, Disgiunzione esclusiva, Implicazione, Bicondizione. Applicazioni della logica proposizionale. Operazioni Aritmetiche e Logiche: l’Algebra di Boole Funzioni booleane, gli Operatori logici AND, OR e NOT, gli Operatori universali, le Espressioni logiche, le Proprietà dell’algebra booleana.
3) Principi di programmazione (Capitolo 3 e parte del capitolo 7 del libro (a)):
• Il nucleo del linguaggio C
• Primi esempi di programmi C
• I dati strutturati in C
• La costruzione incrementale dei programmi
• Struttura completa di un programma in C
• Le funzioni
• Le procedure
Le fonti di informazione, il metodo risolutivo, le proprietà di un algoritmo, Le Fasi del processo di traduzione ed esecuzione di un programma, Il linguaggio dei grafi di flusso, I Simboli convenzionali, le Strutture di controllo del flusso; I tipi di istruzioni; Dati e strutture dati; Tipi di dati; Moduli di un programma; Esempio; Ciclo di vita del software.
4) Modelli Informatici (Dal testo (b): Cap 4, da pp. 99 a 111; Cap 5, da pp. 121 a 128; Cap 6, da pp. 157 a 169; Cap 7, da pp. 193 a 217):
• Ricerche e attraversamenti
• La ricerca esaustiva (tranne massima distanza poligonale)
• Divide et Impera
• Algoritmi greedy
• La programmazione dinamica
• Gli errori di Linguaggio
• Errori Logici
• I Computer non sbagliano
• Test e debug
• Cicli infiniti
• I miglioramenti sono necessari
• Miglioramenti a fatto compiuto
• La ricerca lineare: un esempio
• Miglioramenti dell’ordine di grandezza
• La ricerca binaria: un esempio
• Perché è sufficiente contare i confronti?
• La robustezza della notazione O grande
• Il problema del puzzle delle scimmie: un esempio
• Tempo ragionevole vs. tempo irragionevole
• Problemi di schedulazione e abbinamento
• Determinare la verità logica
• Certificati brevi e monete magiche
• NP-completezza: stare in piedi insieme o cadere insieme
• Ridurre arance a mele
• P è equivalente a NP?

Definizione di algoritmo; Funzioni effettivamente calcolabili; Algoritmi corretti ed algoritmi approssimati; Premessa, INSERTION SORT, Analizzare un algoritmo , Il Tempo di esecuzione di un algoritmo, Il Tempo di esecuzione asintotico, Il Significato (g(n)), Il Significato O(g(n)), Il Significato (g(n)), Efficienza di un algoritmo, Intrattabilità, Rappresentazione schematica di una macchina di Turing deterministica, Rappresentazione schematica di una macchina di Turing non deterministica, Problemi non decidibili e problemi decidibili, la Teoria dell’NP-completezza , Due problemi NP-completi, La classe dei problemi P ed NP.

5) Il Sistema Operativo (Capitolo 13 del libro (a)):
• Funzioni di un sistema operativo
• Gestione dei processi
• Gestione della memoria centrale
• Driver per la gestione delle periferiche
• Gestione dei file
• L’evoluzione dei sistemi operativi
Che cosa è un SO? Scopi del SO, Breve evoluzione dei SO, Sistemi batch, Spooling (Simultaneous Peripheral Operation On Line), Multiprogrammazione, Compiti dell’SO in multiprogrammazione
Sistemi interattivi e time-sharing, Compiti del SO per gestire l’interattività e il time-sharing, Componenti di un SE, Componenti di un SO
Gestione dei processi: Che cos’è un processo? Proprietà , Esempio di molteplicità, Ciclo di vita di un processo, Stati di un processo, Process Control Block (PCB), Condivisione della CPU, L’Interrupt, Scheduling delle code, Principali SO schedulers, Context Switch, Creazione di un processo e possibili scenari, Terminazione di un processo;
Sincronizzazione tra processi: Processi Cooperanti, Esempio di cooperazione: produttore-consumatore, Alcune Soluzioni, Come funziona la sincronizzazione e come si implementa; Tipi di comunicazione, Comunicazione diretta, Comunicazione indiretta, problemi, Buffering/Non-buffering, Sincrona/Asincrona,Eccezioni da gestire.
CPU Scheduling: La multiprogrammazione, CPU burst and I/O burst, Esecuzione dei processi in un sistema multiprogrammato, Time-sharing, Come si gestisce la multiprogrammazione ed il time-sharing, Preemption: Problemi e soluzioni, Politiche di scheduling, Parametri di SO, Parametri di processo, Alcune politiche di scheduling:1. First Come First Served, 2. Shortest Job First, 3. Con priorità, 4. Round Robin (RR).
Gestione della memoria: Concetti di base, La Memoria virtuale, Lo spazio degli indirizzi, Indirizzo logico (o virtuale), Indirizzo fisico, il Memory-Management Unit (MMU), Lo Swapping, Metodi di suddivisione della memoria, Allocazione contigua, partizione singola, La frammentazione, Compattazione, Paginazione Segmentazione, Esempio di segmentazione.

6) Linguaggi e applicativi per condurre esperimenti scientifici.

Italian

• The computer: hardware and software;
• Logical reasoning
• Programming principles
• Computer models;
• Operating systems;
• Computer networks;
• Internet and WWW;
• Programming languages;
• Languages and applications for conducting scientific experiments.

a) Dino Mandrioli, Stefano Ceri, Licia Sbattella, Paolo Cremonesi, Gianpaolo Cugola, “Informatica arte e mestiere” 3/ed, McGraw-Hill, 2008;
b) Harel D., Feldman Y., Algoritmi. Lo spirito dell'Informatica, Springer.

The main goal of the course is to provide students with the ability to understand the principles of informatics and programming:
* Data representation
* Computation, languages and abstract machines
* Architecture of computer systems

INTRODUCTION TO COMPUTER SCIENCE

Lectures and exercises

Esame Scritto e Orale

1) Il computer: hardware and software (Capitoli 1 e 2 del libro (a)):
• Che cosa è l’informatica?
• Il concetto di Algoritmo
• I Linguaggi per la programmazione di Algoritmi
• Architetture dei sistemi Informatici
• Applicazioni dell’Informatica
• Le aree disciplinari dell’Informatica
• Elementi della macchina di von Neumann
• Codifica dei dati e delle istruzioni di un programma
• Comportamento della macchina di von Neumann
• Esecuzione dei programmi
Che cosa e’ un Computer, Generalità, Tipo di informazioni, Il computer come elaboratore dell’informazione, rappresentazione analogica e rappresentazione digitale, Rappresentazione dell’informazione, Definizioni di simbolo, stringa, alfabeto, linguaggio; Alfabeto di un computer, l’operazione di codifica, Binary Digits, La ridondanza, il bit di parità, Il codice binario, Il codice ASCII, i Sistemi numerici, Sistemi numerici posizionali, Il Sistema decimale, Altri sistemi numerici (più adatti per il computer), Conversioni da una base ad un’altra, la parola macchina, Limitazioni, Memorizzazione, Operazioni Aritmetiche, Somma binaria, Sottrazione binaria, Rappresentazione dei Numeri positivi, Rappresentazione dei numeri negativi, Rappresentazione in Complemento a due e in Modulo e Segno e Problemi, Rappresentazione dei numeri reali in Virgola Mobile; L’hardware, le porte logicheGli Elementi di base di un computer, l’Architettura di von Neumann, il Funzionamento del computer, la CPU: L’ALU, I Registri, La Memoria RAM (Random Access Memory), L’Indirizzamento della RAM, Altre memorie: ROM e Cache; Il BUS
Le unità periferiche (I/O devices), Le periferiche di input.
2) Ragionamento logico
Proposizioni, I tre principi della logica, Negazione, Congiunzione, Disgiunzione, Disgiunzione esclusiva, Implicazione, Bicondizione. Applicazioni della logica proposizionale. Operazioni Aritmetiche e Logiche: l’Algebra di Boole Funzioni booleane, gli Operatori logici AND, OR e NOT, gli Operatori universali, le Espressioni logiche, le Proprietà dell’algebra booleana.
3) Principi di programmazione (Capitolo 3 e parte del capitolo 7 del libro (a)):
• Il nucleo del linguaggio C
• Primi esempi di programmi C
• I dati strutturati in C
• La costruzione incrementale dei programmi
• Struttura completa di un programma in C
• Le funzioni
• Le procedure
Le fonti di informazione, il metodo risolutivo, le proprietà di un algoritmo, Le Fasi del processo di traduzione ed esecuzione di un programma, Il linguaggio dei grafi di flusso, I Simboli convenzionali, le Strutture di controllo del flusso; I tipi di istruzioni; Dati e strutture dati; Tipi di dati; Moduli di un programma; Esempio; Ciclo di vita del software.
4) Modelli Informatici (Dal testo (b): Cap 4, da pp. 99 a 111; Cap 5, da pp. 121 a 128; Cap 6, da pp. 157 a 169; Cap 7, da pp. 193 a 217):
• Ricerche e attraversamenti
• La ricerca esaustiva (tranne massima distanza poligonale)
• Divide et Impera
• Algoritmi greedy
• La programmazione dinamica
• Gli errori di Linguaggio
• Errori Logici
• I Computer non sbagliano
• Test e debug
• Cicli infiniti
• I miglioramenti sono necessari
• Miglioramenti a fatto compiuto
• La ricerca lineare: un esempio
• Miglioramenti dell’ordine di grandezza
• La ricerca binaria: un esempio
• Perché è sufficiente contare i confronti?
• La robustezza della notazione O grande
• Il problema del puzzle delle scimmie: un esempio
• Tempo ragionevole vs. tempo irragionevole
• Problemi di schedulazione e abbinamento
• Determinare la verità logica
• Certificati brevi e monete magiche
• NP-completezza: stare in piedi insieme o cadere insieme
• Ridurre arance a mele
• P è equivalente a NP?

Definizione di algoritmo; Funzioni effettivamente calcolabili; Algoritmi corretti ed algoritmi approssimati; Premessa, INSERTION SORT, Analizzare un algoritmo , Il Tempo di esecuzione di un algoritmo, Il Tempo di esecuzione asintotico, Il Significato (g(n)), Il Significato O(g(n)), Il Significato (g(n)), Efficienza di un algoritmo, Intrattabilità, Rappresentazione schematica di una macchina di Turing deterministica, Rappresentazione schematica di una macchina di Turing non deterministica, Problemi non decidibili e problemi decidibili, la Teoria dell’NP-completezza , Due problemi NP-completi, La classe dei problemi P ed NP.

5) Il Sistema Operativo (Capitolo 13 del libro (a)):
• Funzioni di un sistema operativo
• Gestione dei processi
• Gestione della memoria centrale
• Driver per la gestione delle periferiche
• Gestione dei file
• L’evoluzione dei sistemi operativi
Che cosa è un SO? Scopi del SO, Breve evoluzione dei SO, Sistemi batch, Spooling (Simultaneous Peripheral Operation On Line), Multiprogrammazione, Compiti dell’SO in multiprogrammazione
Sistemi interattivi e time-sharing, Compiti del SO per gestire l’interattività e il time-sharing, Componenti di un SE, Componenti di un SO
Gestione dei processi: Che cos’è un processo? Proprietà , Esempio di molteplicità, Ciclo di vita di un processo, Stati di un processo, Process Control Block (PCB), Condivisione della CPU, L’Interrupt, Scheduling delle code, Principali SO schedulers, Context Switch, Creazione di un processo e possibili scenari, Terminazione di un processo;
Sincronizzazione tra processi: Processi Cooperanti, Esempio di cooperazione: produttore-consumatore, Alcune Soluzioni, Come funziona la sincronizzazione e come si implementa; Tipi di comunicazione, Comunicazione diretta, Comunicazione indiretta, problemi, Buffering/Non-buffering, Sincrona/Asincrona,Eccezioni da gestire.
CPU Scheduling: La multiprogrammazione, CPU burst and I/O burst, Esecuzione dei processi in un sistema multiprogrammato, Time-sharing, Come si gestisce la multiprogrammazione ed il time-sharing, Preemption: Problemi e soluzioni, Politiche di scheduling, Parametri di SO, Parametri di processo, Alcune politiche di scheduling:1. First Come First Served, 2. Shortest Job First, 3. Con priorità, 4. Round Robin (RR).
Gestione della memoria: Concetti di base, La Memoria virtuale, Lo spazio degli indirizzi, Indirizzo logico (o virtuale), Indirizzo fisico, il Memory-Management Unit (MMU), Lo Swapping, Metodi di suddivisione della memoria, Allocazione contigua, partizione singola, La frammentazione, Compattazione, Paginazione Segmentazione, Esempio di segmentazione.

6) Linguaggi e applicativi per condurre esperimenti scientifici.