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.

Il corso fornisce nozioni relative ai fondamenti della disciplina informatica, alla gestione delle informazioni, ai principi alla base del ragionamento logico e della programmazione.
Nel dettaglio, il corso è caratterizzato dai seguenti obiettivi formativi:
- Apprendere la terminologia specifica, fatta di termini, concetti, modi di dire e immagini simboliche, propri del mondo dell’informatica e della programmazione e comprendere il senso di questo linguaggio
- Acquisire alcune delle conoscenze teoriche e pratiche più importanti nel campo dell’informatica
- Approfondire la comprensione delle conoscenze acquisite relativa alla programmazione di base attraverso il costante riferimento ad esempi pratici e alla riflessione sulle “buone pratiche”
- Sviluppare la capacità degli studenti di riflettere sulle potenzialità presenti nell’utilizzo della programmazione
- Essere in grado di comprendere la struttura linguistica, operativa e tecnologica delle principali metodologie di programmazione

RISULTATI DI APPRENDIMENTO ATTESI
Conoscenza e capacità di comprensione
Alla fine del corso gli studenti saranno in grado di:
- definire i concetti di base dell’informatica
- descrivere l'architettura logica dell'hardware di un computer
- descrivere le caratteristiche del software
- Illustrare la logica dei programmi
- Risolvere piccoli problemi di logica
- Illustrare il processo di progettazione e sviluppo di un programma
- Illustrare la complessità computazionale di un problema.

Capacità di applicare conoscenza e comprensione
Alla fine del corso gli studenti saranno in grado di:
- applicare le regole principali per la progettazione di piccoli programmi
- Utilizzare le funzionalità di base di un editor per la programmazione
- Utilizzare le funzionalità di base di un sistema operativo moderno

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 modalità di verifica dell'apprendimento:
- si prefigge l’obiettivo di accertare le capacità di saper descrivere l'architettura di una applicazione e di comprensione della rappresentazione binaria dell'informazione
- intende accertare l’apprendimento delle conoscenze di base sui principi di programmazione

La verifica dell'apprendimento si basa su due prove, una prova scritta e una prova orale.
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 seguiti da una domanda aperta, cui verrà assegnata una votazione in trentesimi che avrà un peso di 50/100 nel risultato finale.

La prova orale si svolgerà con un colloquio articolato in domande sugli argomenti:
-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
raggiunto dallo studente.
La prova orale, cui verrà assegnata una votazione in trentesimi, avrà un peso di 50/100 nel risultato finale.
Il superamento dell’esame 18/30, che scaturisce dalla media aritmetica delle due prove.

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.

EXPECTED LEARNING OUTCOMES
Knowledge and understanding skills
At the end of the course, students will be able to:
- define the basic concepts of computer science
- describe the logical architecture of computer hardware
- describe the characteristics of software
- Illustrate the logic of programs
- Solve small logic problems
- Illustrate the process of designing and developing a program
- Illustrate the computational complexity of a problem.

Ability to apply knowledge and understanding
By the end of the course, students will be able to:
- Apply the main rules for the design of small programs
- Use the basic functionality of a programming editor
- Use the basic functionality of a modern operating system

Abilità Informatiche

Lectures divided into the following teaching modules:
The computer: hardware and software
Information representation
Elements of logic
Principles of programming
Algorithmic methods
Computer models
Correctness and computability
Computer networks and distributed systems
Internet services
Language errors
The Theory of NP-completeness

The learning verification mode:
- aims to ascertain the ability to know how to describe the architecture of an application and to understand the binary representation of information
- Intends to ascertain the learning of basic knowledge of programming principles

The verification of learning is based on two tests, a written test and an oral test.
The written test is preparatory to the oral test. It will be held at the premises of the Department of Psychology and each test will last 1 hour.
It consists of No. 30 multiple-choice tests followed by an open-ended question, which will be assigned a grade in thirtieths that will have a weight of 50/100 in the final result.

The oral test will consist of an interview consisting of questions on the topics:
-Representation of Information
-Elements of logic
-Principles of programming
-Algorithmic methods
-Computer models
-Correctness and computability
-Computer networks and distributed systems
-Internet services
-Language Errors
-The Theory of NP-completeness
achieved by the student.
The oral examination, which will be assigned a grade in thirtieths, will have a weight of 50/100 in the final result.
Passing the exam 18/30, which results from the arithmetic average of the two tests.

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.