ITALIANO

• Il computer: hardware and software;
• Ragionamento logico
• Principi di programmazione
• Modelli informatici;
• Reti di computer;
• Internet and WWW;
• I linguaggi di programmazione;

a) Dino Mandrioli, Stefano Ceri, Licia Sbattella, Paolo Cremonesi, Gianpaolo Cugola, “Informatica arte e mestiere” 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à
Reti di calcolatori e sistemi distribuiti
I servizi Internet
Errori di linguaggio
La Teoria dell’NP-completezza

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à
* Reti di calcolatori e sistemi distribuiti
* I servizi Internet
* Errori di linguaggio
* la Teoria dell’NP-completezza
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.

A causa della situazione epidemiologica sanitaria a Febbraio l'esame scritto sarà somministrato da remoto mediante la piattaforma MSTeams e rimarrà in tale modalità per il perdurare della situazione pandemica. Se ci sarà la possibilità o si riceveranno ulteriori indicazioni, l'esame scritto da giugno in avanti verrà svolta in presenza presso i locali del Dipartimento di Psicologia.

Le slides utilizzate durante le lezioni saranno rese disponibili online insieme ai materiali utili per approfondimento ed esercitazioni

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.,

Italian

• The computer: hardware and software;
• Logical reasoning
• Programming principles
• Computer models;
• Computer networks;
• Internet and WWW;
• Programming languages;

a) Dino Mandrioli, Stefano Ceri, Licia Sbattella, Paolo Cremonesi, Gianpaolo Cugola, “Informatica arte e mestiere” 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

Abilità Informatiche

Lectures and exercises

Written and oral exams

The slides used during the lectures will be made available online along with useful materials for further study and exercises

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.