1

Ferdinando Cicalese, cicalese@dia.unisa.it

Adele Rescigno, rescigno@dia.unisa.it

Fondamenti di Informatica

Orario Corso

!  Giovedì 15-18

!  Venerdì 9-11 " Martedì 14-16 (per questa prima parte del corso)

Ricevimento Studenti # Martedì 13-14, Giovedì 14-15 # Dopo le lezioni in aula # Contattando il docente per e-mail

Come rintracciarmi

# E-mail: cicalese@dia.unisa.it

$  L’oggetto della mail deve contenere l’indicazione

del corso: Fondamenti di Informatica

$  La mail deve essere sottoscritta con nome

cognome e numero di matricola

Comunicazioni sul corso

#  Pagina web:

http://www.dia.unisa.it/~cicalese/Fond-Inf/

$  !!! Under construction !!!

2

Testi di Riferimento Algoritmi. Lo spirito dell'informatica Harel David; Feldman Yishai

Capitoli 1, 2, 4, 6, 8

Testi di Riferimento Introduzione ai sistemi informatici Donatella Sciuto; Giacomo Buonanno, Luca Mari

Capitoli 2, 3, 5, 6, 7

Esame e voto

#  una prova scritta (ed un colloquio orale)

#  Esame scritto o “prove in itinere” (sessione estiva) $  due “prove in itinere”

$  Voto: media pesata delle singole prove

$  Orale: permette di aumentare il voto di al piu’ 4 punti.

Domande ?

3

Parte 2 Presentazione dei Contenuti del Corso

Tre domande fondamentali

$  Che cosa studiamo in questo corso?

$  Cosa intendiamo per Informatica? %  e cosa ne costituisce i Fondamenti?

$  Perchè questo corso a VCA?

E’ importante distinguere

Informatica (computer science)

vs. Programmazione (Java, C++, etc.)

Nozione di computazione vs. sue implementazioni (IBM, Tablets, iPhone, etc.)

Niente “programmazione” in questo corso!

$  Non è necessaria per comprendere

% Avremo piu’ tempo per capire lo spirito dell’informatica

% Poco vantaggio per chi ha precedenti esperienze di programmazione

4

Breve storia della “computazione” $  Tecnologia:

%  Orologio calcolatore (Schickard, 1600)

%  Telai meccanici con motore a vapore (1801)

%  Difference and Analytic Machine (C. Babbage, 1822) $  First programmer: Ada Byron

%  Tubi catodici, calcolatori elettronici (1910-1930)

%  ENIAC (1945)

%  Macchina di von Neumann Computer (1949)

%  Primi PC, anni’ 70

Breve storia della ``computazione’’ $  Teoria - Informatica

% Filosofi dell’Antica Grecia $  come “formalizzare il pensiero” $  Algoritmo di Euclide (~350 a.C)

% al Khowarizmi (IX sec.) % Logica Booleana (G. Boole, 1815-1864) % Crisi della matematica

$  Hilbert: necessita’ di sistematizzare la matematica $  Gödel: Teorema di incompletezza

% Lambda calcolo (A. Church, 1936) % Macchine di Turing (A. Turing, 1937) Prima chiara nozione di

“computazione”

Wang tiles 1961

Informatica: Un modo nuovo di guardare il mondo

Esempio 1:

5

Esempio 2: Elezione a voto segreto in pubblico

$  Una votazione % ognuno si esprime pubblicamente

(no computer, email, etc.) % Alla fine: ognuno e’ d’accordo su chi

ha vinto e di quanto % Nessuno sa il voto degli altri

% Possibile? % SI! (A. Yao)

Esempio 3: Biologia Computazionale

Biologia Tradizionale Nuove Metodologie

Microarrays

Pathways

Un universo computazionale

“Cosa da vita alla materia” – La prospettiva del 20th secolo

$  “Materia”: Atomi, molecole, meccanica quantistica, relativita’ …

$  “Vita”: Cellule, nucleo, DNA, RNA, …

$  “Dar vita alla materia”: Computazione

6

Fondamenti di Informatica: ``Tentative syllabus’’ Domande?

Philippe Semeria CIMA museum

Dave Bowman and HAL from the movie "2001: A Space Odyssey” (Stanley Kubrick 1968)

Algoritmica (prime nozioni)

$  Una procedura precisa e priva di ambiguità per ottenere un risultato computazionale

$  Algoritmo discende da Abu Abdullah Muhammad bin Musa al-Kohwarizmi %  Il suo libro "Al-Jabr wa-al-Muqabilah" e’ il

progenitore dei moderni libri di algebra.

$  Esempi: ricette, divisioni a piu’ cifre, MCD, Google.

7

$  passi “elementari” interpretabili in modo “univoco”

$  numero finito di passi e quantità finita di input

$  terminazione dopo un tempo finito e risultato univoco;

$  la sequenza di passi è deterministica eccezione: algoritmi randomizzati

Esempio: Somma di due numeri

Discussion

Time

Immagina di descrivere come addizionare a qualcuno che non ne ha mai sentito parlare. Come lo spiegheresti?

Prova prima con due numeri ad una sola cifra!

In generale:

Come possiamo descrivere un algoritmo in un modo sufficientemente preciso da non lasciare ambiguita’?

Il linguaggio di un robot: passi elementari

$  Semplici istruzioni di movimento e calcolo %  Es. “Muoviti in avanti/indietro”; “leggi un numero”; “confronta

numeri”; “Prendi un oggetto”

$  Due tipi di istruzioni composite (di controllo)

If condition Then

{

List of instructions

}

Else

{

List of instructions

}

Do 5 times

{

List of instructions

}

Condizionali Loop

8

Un primo semplice problema

$  Un robot si prepara ad un’uscita galante…

$  Come identificare il profumo piu’ economico? (Assumiamo possa leggere i prezzi)

Soluzione

%  0. Prendi la prima bottiglia, %  1. Vai alla prossima bottiglia nello scaffale %  2. Confronta il prezzo sulla bottiglia nello scaffale con quello in

mano %  3. Se e’ minore scambia la bottiglia tenuta in mano con quella

sullo scaffale %  4. Ripeti da 1.

$  Alla fine la bottiglia di costo minimo e’ nelle mani del robot

Analizziamo la soluzione al problema del Robot

Discussion

Time

E’ un algoritmo?

E’ corretto?

Quanto tempo impiega?

Riposiziona le bottiglie in modo tale che i prezzi crescano da sinistra a destra.

9

Il linguaggio del robot illustra gli elementi essenziali di tutti i linguaggi per computer

Java

C++ BASIC

Python

Torre di Babele dei computer

Caratteristiche dei languaggi umani: sostantivi/verbi/aggettivi/etc.

Caratteristiche dei linguaggi dei computer: variabili, semplici istruzioni aritmetiche,

Istruzioni condizionali/loop

Per un computer, esistono solo numeri Justin Bieber song

Sequenza di Numeri che rappresentano ampiezza,

frequenza, etc. ad ogni istante (es., formato mp3)

Sequenza di Numeri che rappresentano intensita’ dei colori

per ogni pixel.

Image

Compito base di un computer

Data: una sequenza di numeri in memoria (es., musica mp3)

Scopo: Elabora questi numeri per ottenere una specifica sequenza di numeri come output (es., segnali elettrici che comandano le

cuffie e riproducono la musica)

40.99 62.99 52.99 … 22.99

Problema simile in altro contesto

$ Robot ha n prezzi in memoria

$ Vuole trovare il prezzo minimo

10

Memoria: visione semplificta

$  Una lavagnetta che puo’ essere cancellata e riscritta quante volte si vuole

$  Una variabile: un pezzo di memoria con un nome; contiene/memorizza un “valore”

22.99 i =

valore nome

Esempi

i ! 5 Assegna ad i il valore 5

j ! i Assegna a j qualsiasi valore sia assegnato ad i. Lascia il valore di i invariato

i ! j + 1 Assegna i al valore di j + 1. Lascia il valore di j invariato

i ! i + 1 Assegna ad i il valore ottenuto sommando 1 al valore precedentemente assegnato ad i stesso.

Array

$  A e’ un array di n valori A[ i ] e’ l’ i-esimo valore

$  Esempio: A[3] = 52.99

40.99 62.99 52.99 … 22.99 A =

Soluzione

$  Prendi la prima bottiglia, controlla il prezzo

$  Vai lungo lo scaffale. Per ogni bottiglia, esegui: %  Se il prezzo sulla bottiglia e’ inferiore al prezzo di quella in mano,

scambia le bottiglie.

11

Procedura trovamin!

$  n elementi, nell’array A $  Variabili di supporto: i, best

best ! 1!Do for i = 2 to n !!{!! !if ( A[i] < A[best] ) then!! ! best ! i !!}!

Un’alternativa per lo stesso task

best ! 1;!

i ! 1!

Do while (i < n)!

{!

!i ! i + 1;!

!if ( A[i] < A[best] ) then!

! !best ! i !

}!

Molti passi di elaborazione in poche righe di codice

Devo ordinare n bottiglie. Mmmm?!? Aha! trovo quella col prezzo minimo e la

metto nella posizione piu’ a sinistra. Quindi mi rimane da ordinare solo le n-1 bottiglie

alla sua destra.

12

Soluzione

Do for i=1 to n-1

{

Trova la bottiglia piu’ economica tra quelle numerate da i a n

Scambia tale bottiglia e la bottiglia i -esima.

} “selection sort”

Nota: sappiamo gia’ fare questo! Scambio

$  Date due variabili x e y, Come scambio i loro valori?

$  Ho bisogno di un’altra variabile!

tmp ! x

x ! y

y ! tmp