Post on 03-May-2015
transcript
1
Parte 2
Fondamenti di programmazione
2
Definizione intuitiva di algoritmo Elenco finito di istruzioni che specificano una serie di operazioni, eseguendo le quali e’ possibile risolvere ogni istanza di un problema di un dato tipo
3
Proprietà degli algoritmi FINITI NON AMBIGUI GENERALI
4
Soluzione di ax2+bx+c=0
1. inizio dell’algoritmo;2. acquisire dall’esterno i valori dei coefficienti a, b e c;3. calcolare il valore b2-4ac;4. se , allora non esistono radici reali: eseguire 8;5. se , allora x1=x2=-b/2a: eseguire 7;6. se , allora x1=(-b+)/2a e x2=(-b-)/2a;7. comunicare all’esterno i valori di x1 ed x2;8. fine dell’algoritmo.
5
Descrizione degli algoritmi
Diagramma a blocchi (flow chart): rappresentazione grafica di un algoritmo che indica il flusso delle trasformazioni descritte dall’algoritmo che devono essere eseguite a partire dai dati iniziali per ottenere i risultati finali.
6
Blocchi elementari
begin
end
input
output
azione
Cverofalso
7
Esempio su ax2+bx+c=0
end
begin
a, b, c
b2-4ac
V F
FV x1=-b/2a
x2=-b/2a
x1=(-b+)/2a
x2=(-b-)/2a
radici c.c. x1, x2
8
Il gioco dei quindici
Quindici oggetti, ad esempio fiammiferi, sono su una tavola. Il primo giocatore ne raccoglie 1, 2 o 3. Il secondo giocatore ne raccoglie a sua volta 1, 2 o 3. Quindi è ancora il primo giocatore a raccogliere 1, 2 o 3 fiammiferi. I giocatori alternano le loro mosse finchè sul tavolo non esistono più fiammiferi. Il giocatore che è costretto a raccogliere l’ultimo fiammifero è il perdente.
Descrivere una strategia vincente per il primo giocatore
9
Problema delle dodici monete
Tra 12 monete di identico aspetto potrebbe nascondersene una falsa e pertanto di peso diverso. Disponendo di una bilancia a 2 piatti per confrontare gruppi di monete, si vuole individuare la moneta falsa e stabilire se essa pesi più o meno delle altre, mediante non più di 3 pesate.
10
Soluzione del gioco dei quindici
Siano A il primo giocatore e B il secondo
1. Prima mossa: A raccoglie 2 fiammiferi
2. Mosse successive: se B raccoglie k fiammiferi (k<=3), allora A raccoglie 4-k fiammiferi
11
Soluzione del gioco delle monete
1, 2, 3, 4 : 5, 6, 7, 8
1, 2, 5 : 3, 4, 6 1, 2, 5 : 3, 4, 6
9, 10 : 11, 1
1:2 7:8 1:2
9:10
7P 8P
1L
9L 0
1L 2L 3L 4L5P 6P 7P 8P
1P 2P 3P 4P5L 6L 7L 8L
9L 10L 11L 12L9P 10P 11P 12P01L 2L 6P 5P 3L 4L 5L 3P 4P 7L 8L 1P 2P 6L
9L 10L 11P12L 12P 0
9P 10P 11l
7:8 3:4 3:4
6P 2L 8P imp 7P 3L 5P 4L 4P 5L 3P 7L imp 8L 2P 6L
12:1 9:10
11P 10L 12L 12P 10P 11L 9P
1P
12
Breve storia dei calcolatori
Primi strumenti di calcolo meccanici
Abaco1600
Pascal (somma e sottrazione)Leibniz (moltiplicazione e divisione)
1800Babbage (quadrato e stampa)Babbage (macchina analitica)
Ada Augusta Lovelace (prima programmatrice)Schede perforate utilizzate nel 1890 (inizio di IBM)
13
1944Mark I (primo calcolatore elettromeccanico)
1946ENIAC
1949EDSAC (macchina di tipo Von Neumann)
Anni successiviStessa architettura ma tecnologia più avanzata
1960Internet (fine anni sessanta per esigenze militari, si chiamava Arpanet)
1989www (word wide web: enorme enciclopedia)
14
HardwarePezzi fisici tangibili che supportano l’elaborazione (chip di silicio, fili elettrici, tastiera, dischi, stampanti….)SoftwareI componenti hardware sono inutili se non ricevono precise istruzioni. Un programma è una serie di istruzioni che l’hardware esegue in sequenza.
15
Componenti hardware principali
Dispositivi di input
Ad es.: mouse, tastiera
Dispositivi di output
Ad es.: monitor, stampante
Insieme in uno stesso contenitore
Processore (CPU)Central Processing UnitInterpreta e esegue le istruzioni
Memoria
Organizzazione hardware standard
Memoria
Processore(CPU)
Dispositividi
input
Dispositivi di output
16
Due Tipi di Memoria
Principalearea di lavoromantiene temporaneamente programmi e dati (mentre il programma è in esecuzione)
Ausiliariapermanentesalva programmi e risultati Esempi: floppy & hard disk, CD, nastri
17
Indirizzo Dato
3021 1111 0000
3022 1100 1100 Dato 1: 2 byte
3023 1010 1010 Dato 2: 1 byte
3024 1100 1110
3025 0011 0001
3026 1110 0001
Dato 3: 3 byte
3027 0110 0011
3028 1010 0010 Dato 4: 2 byte
3029 … Etc.
Organizzazione della Memoria Principale
Bit = una cifra binaria
valori: 0 o 1Byte = 8 bitLa memoria principale è una lista di locazioni numerate ciascuna di un byteIl numero di byte utilizzato per memorizzare un dato varia con il tipo di dato
18
Radice
Organizzazione della Memoria Ausiliaria
File Directory Directory
File Directory Directory
File
File
File FileDirectory
Directory
19
Programma
Insieme di istruzioni che il calcolatore deve eseguire
Calcolatore
Programma
Input Output
20
Tipi di Programmi
Sistema OperativoProgramma supervisore
DOS, Windows, MacOS, UNIX, LinuxApplicazioni esistenti
word-processor/editorweb browsercompilatori o assembler
Applicazioni create dall’utente
21
Informazione
Esistono due formati per memorizzare l’informazione:ANALOGICO DIGITALE
L’informazione analogica è continua La tecnologia digitale spezza e cresce proporzionalmente alla l’informazione in tanti pezzisorgente di informazione che rappresenta come numeriEs: termometro di mercurio, segnali Es: compact discelettrici
22
I computer moderni sono digitali:Ogni tipo di informazione è spezzato in blocchi. Ogni blocco è rappresentato da un numero e l’informazione è memorizzata sotto forma di sequenza di numeri. Il computer digitale memorizza l’informazione sotto forma di numeri binari (base 2).La singola cifra binaria si chiama bit (binary digit). La base del sistema indica quante cifre si hanno a disposizione e il valore posizionale di ogni cifra in un numero.
23
Sistemi posizionali
Il sistema di numerazione decimale è basato sull’alfabeto decimale {0,1,2,3,4,5,6,7,8,9} ed ogni numero è rappresentato come sequenza di simboli di tale alfabeto. Ad ogni simbolo è associato un peso a seconda della posizione.Es:2863=2x103 +8x102+6x101+3x100
24
In generale i sistemi numerici posizionali in base b2 rappresentano ogni numero con m cifre in base b:N=cm-1…….c0
Dove i ci denotano elementi di un insieme di b simboli che corrispondono ai primi b numeri naturali 0…..b-1.Vale N=∑cibi
Es:11002=1x23+1x22+0x21+0x20
25
Come comunicare
Linguaggio macchina:sequenze di 0 ed 1rigorosoessenziale
Linguaggio assembler:simbolicosemplice traduzione aggiuntiva
Linguaggio naturale:linguaggio preferito dall’essere umanoambiguo, ridondante, non preciso
Linguaggio di programmazione ad alto livello
26
Storia Moderna
PASCAL (1970)
Programming in Logic (1971)
C (1974)
ADA(1980)
27
Storia Contemporanea
C++ (1985)
Java (1994)
28
Tipi di programmazione
Funzionale
Logica
Procedurale
Orientata agli oggetti
29
Traduttori
traduttore
programma
macchina
Codice in l. macchina
dati
macchina
Codice in l. macchina risultati
30
Compilatori ed interpreti
Compilatoreprogramma che traduce un programma in linguaggio ad alto livello in un programma in linguaggio più semplice che il calcolatore può eseguire (più o meno) direttamente.
Interpreteprogramma che traduce ed esegue una dopo l’altra le istruzioni che compongono il programma sorgente
31
L’approccio di Java
Sia compilato che interpretato
Codice intermedio: “Byte Code”codice a basso livello portabilesimile al codice assembler ma indipendente dall’hardwareinvisibile ai programmatori Java
L’interprete traduce dal byte code in un programma nel linguaggio macchina della macchina specifica
32
L’ambiente Java
Programma Java
Compilatore Java
Programma inByte-Code
Dati in input
Esecuzione
Interprete
Programmi precedentementecompilati
Output del Programma Java