Informatica - ce.uniroma2.itlopresti/IntroLop_2015x4.pdf · Prof. Francesco Lo Presti Informatica...

Informatica

Prof. Francesco Lo Presti Prof. Francesco Lo Presti

[email protected]@info.uniroma2.it

CalendarioCalendario delledelle lezionilezioni

�� 11/11 16:0011/11 16:00--18:00 18:00 AulaAula D15D15

�� 18/11 16:0018/11 16:00--18:00 18:00 AulaAula D15D15

�� 25/11 16:0025/11 16:00--18:00 18:00 AulaAula D15D15

�� 2/12 16:002/12 16:00--18:00 18:00 AulaAula D15D15�� 2/12 16:002/12 16:00--18:00 18:00 AulaAula D15D15

�� 99/12 16:00/12 16:00--18:00 18:00 AulaAula D15D15

�� 16/12 16:0016/12 16:00--18:00 18:00 AulaAula D15D15

�� 13/1 16:0013/1 16:00--18:00 18:00 AulaAula D15D15

�� 20/1 16:0020/1 16:00--18:00 18:00 AulaAula D15D15

ProgrammaProgramma ((indicativoindicativo))

�� IntroduzioneIntroduzione al al corsocorso

�� CodificaCodifica dell’Informazionedell’Informazione

��ArchitettureArchitetture deidei CalcolatoriCalcolatori

�� ElaborazioneElaborazione dell’Informazionedell’Informazione

RetiReti di di CalcolatoriCalcolatori�� RetiReti di di CalcolatoriCalcolatori

MaterialeMateriale didatticodidattico

�� TestoTesto di di riferimentoriferimento❍❍ IntroduzioneIntroduzione aiai sistemisistemi informaticiinformatici 4/4/eded –– D. D. SciutoSciuto, G. , G.

BuonannoBuonanno, L. Mari , L. Mari -- McGrawMcGraw--Hill Hill

�� MaterialeMateriale sulsul sitosito del del corsocorso❍❍ http://www.ce.uniroma2.it/...http://www.ce.uniroma2.it/...❍❍ http://www.ce.uniroma2.it/...http://www.ce.uniroma2.it/...

❍❍ Le slides Le slides delledelle lezionilezioni pubblicatepubblicate sulsul sitosito possonopossono essereessereutilizzateutilizzate come come integrazioneintegrazione ma non ma non sonosono sufficientisufficienti per per prepararsiprepararsi per per l’esamel’esame (BISOGNA STUDIARE SUL (BISOGNA STUDIARE SUL LIBRO!)LIBRO!)

RicevimentoRicevimento eded esamiesami

�� RicevimentoRicevimento❍❍ In In aulaaula al al terminetermine delladella lezionelezione❍❍ Su Su appuntamentoappuntamento (da (da concordareconcordare tramitetramite email) email) pressopresso la la

FacoltàFacoltà di di IngegneriaIngegneria

��DipartimentoDipartimento InformaticaInformatica SistemiSistemi e e ProduzioneProduzione stanza D1stanza D1--1212

�� EsameEsame�� EsameEsame❍❍ ProvaProva scrittascritta❍❍ date date dada definiredefinire

�� RiconoscimentoRiconoscimento EsameEsame❍❍ PatentePatente EuropeaEuropea -- OKOK❍❍ EsameEsame dada 1+ CFU 1+ CFU didi InformaticaInformatica pressopresso altraaltra sedesede e/o e/o

CdLCdL -- OKOK

IntroduzioneIntroduzione

Prof. Francesco Lo PrestiProf. Francesco Lo Presti

InformaticaInformatica

�� Varie DefinizioniVarie Definizioni

1.1. “Scienza degli Elaboratori Elettronici”“Scienza degli Elaboratori Elettronici”❍❍ Computer ScienceComputer Science

2.2. “Scienza dell’Informazione”“Scienza dell’Informazione”

�� “Scienza della Rappresentazione e della “Scienza della Rappresentazione e della

Introduzione 7

�� “Scienza della Rappresentazione e della “Scienza della Rappresentazione e della Elaborazione dell’Informazione”Elaborazione dell’Informazione”

L’informatica studia le caratteristiche L’informatica studia le caratteristiche dell’informazione e i modi di usarla, dell’informazione e i modi di usarla, immagazzinarla, trasportarla e manipolarla in immagazzinarla, trasportarla e manipolarla in modo automaticomodo automatico

L’Informatica comprende:L’Informatica comprende:

1.1. Metodi per la rappresentazione dell’informazioneMetodi per la rappresentazione dell’informazione2.2. Metodi per la rappresentazione delle soluzioniMetodi per la rappresentazione delle soluzioni3.3. Linguaggi di programmazioneLinguaggi di programmazione4.4. Linguaggi di integrazioneLinguaggi di integrazione5.5. Architettura dei calcolatoriArchitettura dei calcolatori6.6. Sistemi operativiSistemi operativi7.7. Reti di CalcolatoriReti di Calcolatori8.8. Basi di DatiBasi di Dati

Introduzione 8

8.8. Basi di DatiBasi di Dati9.9. Tecnologie WebTecnologie Web10.10. AlgoritmiAlgoritmi

……

�� Due AnimeDue Anime❍❍ TecnologicaTecnologica: I calcolatori elettronici ed i sistemi che li : I calcolatori elettronici ed i sistemi che li

utilizzanoutilizzano❍❍ MetodologicaMetodologica: I metodi per la soluzione di problemi e la : I metodi per la soluzione di problemi e la

gestione delle informazioni gestione delle informazioni

CalcolatoreCalcolatore

�� Un Un calcolatore elettronicocalcolatore elettronico è una è una macchina macchina programmabileprogrammabile per la rappresentazione, la per la rappresentazione, la memorizzazione, l’elaborazione e la trasmissione memorizzazione, l’elaborazione e la trasmissione delle informazioni delle informazioni

�� Deve essere in grado di:Deve essere in grado di:❍❍ Eseguire istruzioni sui datiEseguire istruzioni sui dati

Introduzione 9

❍❍ Eseguire istruzioni sui datiEseguire istruzioni sui dati

❍❍ Controllare il flusso di esecuzioneControllare il flusso di esecuzione

❍❍ Memorizzare le istruzioni e i dati su cui operareMemorizzare le istruzioni e i dati su cui operare

❍❍ Interagire con gli utenti e gli altri sistemiInteragire con gli utenti e gli altri sistemi

�� DecomposizioneDecomposizione❍❍ HardwareHardware: Struttura fisica del calcolatore: Struttura fisica del calcolatore

❍❍ SoftwareSoftware: Insieme di programmi che consentono : Insieme di programmi che consentono all’hardware di svolgere compiti utiliall’hardware di svolgere compiti utili

Programma e ProgrammazioneProgramma e Programmazione

�� ProgrammaProgramma❍❍ Sequenza di istruzioni che il computer esegue e di Sequenza di istruzioni che il computer esegue e di

decisioni che il computer prende per svolgere una certa decisioni che il computer prende per svolgere una certa attivitàattività

❍❍ IstruzioniIstruzioni�� estrarre un numero da una posizione della memoriaestrarre un numero da una posizione della memoria�� sommare due numerisommare due numeri

inviare la lettera inviare la lettera A A alla stampantealla stampante

Introduzione 10

�� inviare la lettera inviare la lettera A A alla stampantealla stampante�� se un dato è negativo, proseguire il programma da una certa se un dato è negativo, proseguire il programma da una certa

istruzione anziché dalla successiva (istruzione anziché dalla successiva (decisionedecisione))

❍❍ Ogni programma svolge una diversa funzione, anche Ogni programma svolge una diversa funzione, anche complessacomplessa�� impaginare testi o giocare a scacchiimpaginare testi o giocare a scacchi

�� ProgrammazioneProgrammazione❍❍ L’attività di L’attività di progettareprogettare e e realizzarerealizzare un un programmaprogramma

AlgoritmoAlgoritmo

�� Quale tipo di problemi è possibile risolvere con un Quale tipo di problemi è possibile risolvere con un computer?computer?

�� Si dice Si dice algoritmoalgoritmo la descrizione di un la descrizione di un metodo di metodo di soluzionesoluzione di un di un problemaproblema cheche

❍❍ sia eseguibilesia eseguibile

Introduzione 11

❍❍ sia eseguibilesia eseguibile

❍❍ sia priva di ambiguità arrivi ad una conclusione in un sia priva di ambiguità arrivi ad una conclusione in un tempo finitotempo finito

�� Un Un computercomputer può risolvere soltanto quei può risolvere soltanto quei problemiproblemiper i quali sia noto un per i quali sia noto un algoritmoalgoritmo

Cosa e’ un calcolatore?Cosa e’ un calcolatore?

�� “A device that computes, especially a “A device that computes, especially a programmable electronic machineprogrammable electronic machine that performs that performs highhigh--speed mathematical or logical operations or speed mathematical or logical operations or that assembles, stores, correlates, or otherwise that assembles, stores, correlates, or otherwise processes information”processes information”---- The American Heritage Dictionary of the The American Heritage Dictionary of the English LanguageEnglish Language, 4th Edition, 2000, 4th Edition, 2000

Introduzione 12

---- The American Heritage Dictionary of the The American Heritage Dictionary of the English LanguageEnglish Language, 4th Edition, 2000, 4th Edition, 2000

Calcolatore Elettronico Calcolatore Elettronico

�� Macchina per l’esecuzione automatica di algoritmiMacchina per l’esecuzione automatica di algoritmi❍❍ General Purpose:General Purpose: puo’ svolgere qualsiasi elaborazione di puo’ svolgere qualsiasi elaborazione di

cui sia noto un algoritmo risolutivocui sia noto un algoritmo risolutivo

�� Programma e’ un algoritmo espresso in un Programma e’ un algoritmo espresso in un linguaggio di programmazionelinguaggio di programmazione

�� Linguaggio macchina binarioLinguaggio macchina binario: l’insieme delle : l’insieme delle

Introduzione 13

�� Linguaggio macchina binarioLinguaggio macchina binario: l’insieme delle : l’insieme delle istruzioni istruzioni direttamente eseguibile dal calcolatore direttamente eseguibile dal calcolatore

�� Istruzione MacchinaIstruzione Macchina❍❍ operazione logico/aritmetica su dati o di trasferimento operazione logico/aritmetica su dati o di trasferimento

datidati

❍❍ codificata in binariocodificata in binario�� Esempio 10000110010100000 istruisce il calcolatore di Esempio 10000110010100000 istruisce il calcolatore di

effettuare una sommaeffettuare una somma

�� Programma eseguibileProgramma eseguibile: un algoritmo espresso in : un algoritmo espresso in linguaggio macchinalinguaggio macchina

Calcolatore ElettronicoCalcolatore Elettronico

1.1. Accetta in ingresso informazioni codificate in Accetta in ingresso informazioni codificate in forma digitaleforma digitale

2.2. Le elabora attraverso un Le elabora attraverso un programma memorizzatoprogramma memorizzato

3.3. Produce informazioni in uscitaProduce informazioni in uscita

Introduzione 14

Computer

Programma memorizzato in esecuzione

Dati Risultati

Modello di Von NeumannModello di Von Neumann

Unità di controllo

Unità di elaborazione

Memoria

Processore

Dispositivi di I/O

Dispositivi di I/O

Interfaccia di I/O

Interfaccia

Introduzione 15

elaborazione dati

Interfaccia di I/O

Interfaccia di I/O

Busdatiindirizzicontrollo

Processore Processore -- Central Processing Unit (CPU)Central Processing Unit (CPU)

�� Provvede all’esecuzione delle istruzioni macchina Provvede all’esecuzione delle istruzioni macchina

�� Ciclo di EsecuzioneCiclo di Esecuzione1.1. Prelievo Istruzione dalla MemoriaPrelievo Istruzione dalla Memoria

2.2. Decodifica IstruzioneDecodifica Istruzione

3.3. Esecuzione IstruzioneEsecuzione Istruzione

�� Ogni Processore e’ caratterizzato da un proprio Ogni Processore e’ caratterizzato da un proprio

Introduzione 16

�� Ogni Processore e’ caratterizzato da un proprio Ogni Processore e’ caratterizzato da un proprio linguaggio macchinalinguaggio macchina

Processore Processore -- Central Processing Unit (CPU)Central Processing Unit (CPU)

�� Processore e’ composto da due sottosistemi:Processore e’ composto da due sottosistemi:1.1. Unità di Controllo (Control) Unità di Controllo (Control) –– Parte di ControlloParte di Controllo

❍❍ Controlla il sequenziamento e l’esecuzione delle istruzioni Controlla il sequenziamento e l’esecuzione delle istruzioni generando i segnali di controllogenerando i segnali di controllo

2.2. Unita’ di Elaborazione (Datapath) Unita’ di Elaborazione (Datapath) –– Parte Parte OperativaOperativa

Esegue le istruzioniEsegue le istruzioni

Introduzione 17

❍❍ Esegue le istruzioniEsegue le istruzioni❍❍ ALUALU

�� Esegue operazioni logico aritmetiche sui datiEsegue operazioni logico aritmetiche sui dati

❍❍ Banco di Registri (Register File)Banco di Registri (Register File)�� Memoria interna CPUMemoria interna CPU�� Program Counter (PC)Program Counter (PC)

–– Indirizzo Prossima IstruzioneIndirizzo Prossima Istruzione�� Instruction Register (IR)Instruction Register (IR)

–– Codice Istruzione da eseguireCodice Istruzione da eseguire

Processore Processore -- Central Processor Unit (CPU)Central Processor Unit (CPU)

ALU

Registri

Bus I

nterno C

PU

PCIR

Bus D

ati

Bus I

ndir

izzi

Bus C

ontrolloUnità di Elaborazione

Introduzione 18

Unità di Controllo

ALU

Bus I

nterno C

PU

Segnali di Controllo

Bus I

ndir

izzi

Bus C

ontrollo

Il BusIl Bus

�� La struttura di interconnessione più comuneLa struttura di interconnessione più comune❍❍ percorsi di comunicazione tra due o più dispositivipercorsi di comunicazione tra due o più dispositivi

❍❍ mezzo di trasmissione condivisomezzo di trasmissione condiviso

❍❍ Usualmente di tipo broadcastUsualmente di tipo broadcast�� I dati sono visibili da tutte le unità connesse I dati sono visibili da tutte le unità connesse

Introduzione 19

Unità di controllo

Unità di elaborazione dati

Memoria

ProcessoreDispositivi di

I/ODispositivi di

I/O

Interfaccia di I/O

Interfaccia di I/O

Busdati

indirizzi

controllo

La Memoria La Memoria

�� Memoria Primaria: Memoria CentraleMemoria Primaria: Memoria Centrale❍❍ Contiene istruzioni/dati dei programmi in esecuzioneContiene istruzioni/dati dei programmi in esecuzione

�� …in formato binario…in formato binario

❍❍ VolatileVolatile❍❍ RAM RAM –– Random Access MemoryRandom Access Memory

��Memoria ad accesso casualeMemoria ad accesso casuale–– Tempo di accesso costanteTempo di accesso costante

Introduzione 20

–– Tempo di accesso costanteTempo di accesso costante�� SRAM, DRAM, etc.SRAM, DRAM, etc.

❍❍ Veloce (~10Veloce (~10--100ns) Costosa100ns) Costosa❍❍ Dimensioni contenute (fino a qualche Gigabyte)Dimensioni contenute (fino a qualche Gigabyte)❍❍ E’ organizzata come una gerarchia di memorieE’ organizzata come una gerarchia di memorie

�� Cache di primo e secondo livello…Cache di primo e secondo livello…

�� Memoria Secondaria: Dischi, CD, etc..Memoria Secondaria: Dischi, CD, etc..❍❍ Memoria di lungo periodo Memoria di lungo periodo -- non volatilenon volatile❍❍ Tempo di accesso maggiori (~ms e piu’), economicaTempo di accesso maggiori (~ms e piu’), economica

La Memoria Centrale La Memoria Centrale

�� CompostaComposta didi cellecelle, o , o locazionilocazioni, a , a loroloro voltavoltacompostecomposte dada un un numeronumero fissofisso didi bitbit

❍❍ CellaCella elementareelementare didi memoriamemoria puòpuò memorizzarememorizzare solo solo due due valorivalori: 0 o 1, : 0 o 1, cifracifra binariabinaria (binary digit (binary digit --> bit) > bit)

❍❍ TipicamenteTipicamente cellacella=1 byte (8 bit)=1 byte (8 bit)

�� OgniOgni locazionelocazione e’ e’ associataassociata ad un ad un indirizzoindirizzonell’intervallonell’intervallo [0,1,…,M[0,1,…,M--1]1]

❍❍ M M dimensionedimensione delladella memoriamemoria Memoria

byte M-1

byte M-2

Introduzione 21

❍❍ M M dimensionedimensione delladella memoriamemoria❍❍ La La memoriamemoria e’ vista come un e’ vista come un vettorevettore didi bytebyte

�� La CPU (ma non solo) accede La CPU (ma non solo) accede allealle informazioniinformazioni in in scritturascrittura//letturalettura tramitetramite indirizzoindirizzo delladella cellacella

❍❍ IndirizziIndirizzi a m bit: a m bit: spaziospazio didi indirizzamentoindirizzamento 22mm

�� Non Non necessariamentenecessariamente M= 2M= 2mm

�� OperazioniOperazioni: : LetturaLettura//ScritturaScrittura❍❍ LetturaLettura: : PrelevarePrelevare ilil contenutocontenuto didi unauna cellacella didi memoriamemoria❍❍ ScritturaScrittura: : SostituireSostituire ilil contenutocontenuto didi unauna cellacella didi memoriamemoria

Memoria

8 bit

byte 0

byte 1

Software Applicativo

Software di Base

SoftwareSoftware

�� Programmi che vengono eseguiti dal sistemaProgrammi che vengono eseguiti dal sistema❍❍ Software di baseSoftware di base

�� Sistema OperativoSistema Operativo

❍❍ Software ApplicativoSoftware Applicativo��Word Word ProcessorProcessor

Insieme (complesso) di programmiInsieme (complesso) di programmi

Hardware

Introduzione 22

Software Applicativo�� Insieme (complesso) di programmiInsieme (complesso) di programmi

�� Organizzato a stratiOrganizzato a strati❍❍ Ciascuno con funzionalità di livello più alto rispetto a Ciascuno con funzionalità di livello più alto rispetto a

quelli sottostantiquelli sottostanti

�� Concetto di Macchina VirtualeConcetto di Macchina Virtuale

Il Sistema OperativoIl Sistema Operativo

�� Strato software che opera sopra l’hardware e Strato software che opera sopra l’hardware e gestisce l’elaboratoregestisce l’elaboratore

❍❍ Windows, Linux, Windows, Linux, MacOsMacOs X, X, Android, etc.Android, etc.

�� FunzioniFunzioni❍❍ Gestione delle risorse disponibiliGestione delle risorse disponibili

�� Processore, Memoria, Dischi, Processore, Memoria, Dischi, etcetc,,

Introduzione 23

�� Processore, Memoria, Dischi, Processore, Memoria, Dischi, etcetc,,

❍❍ Processore: Sistema MultiutenteProcessore: Sistema Multiutente❍❍ Memoria Centrale: Memoria VirtualeMemoria Centrale: Memoria Virtuale❍❍ Memoria Secondaria: File SystemMemoria Secondaria: File System

�� Gli utenti vedono l’elaboratore solo tramite il Gli utenti vedono l’elaboratore solo tramite il Sistema OperativoSistema Operativo

❍❍ Il SO realizza una “macchina virtuale”Il SO realizza una “macchina virtuale”

Programmi ApplicativiProgrammi Applicativi

�� Risolvono problemi specifici degli utenti:Risolvono problemi specifici degli utenti:❍❍ Word processorWord processor

❍❍ Fogli elettroniciFogli elettronici

❍❍ DatabaseDatabase

❍❍ GiochiGiochi

❍❍ Etc. Etc.

Introduzione 24

Etc. Etc. �� Scritti in linguaggi di programmazione di alto livelloScritti in linguaggi di programmazione di alto livello

�� Ambiente di ProgrammazioneAmbiente di Programmazione❍❍ L’insieme dei programmi che consentono la scrittura, la L’insieme dei programmi che consentono la scrittura, la

verifica e l’esecuzione di nuovi programmi verifica e l’esecuzione di nuovi programmi �� Fase di sviluppoFase di sviluppo

Alcune Domande FondamentaliAlcune Domande Fondamentali

�� Quali istruzioni esegue un eleboratore?Quali istruzioni esegue un eleboratore?

�� Quali problemi puo’ risolvere un eleboratore?Quali problemi puo’ risolvere un eleboratore?

�� Esistono problemi che un elaboratore non puo’ Esistono problemi che un elaboratore non puo’ risolvere?risolvere?

�� Che ruolo ha il linguaggio di programmazione?Che ruolo ha il linguaggio di programmazione?

Introduzione 25

Problemi da RisolvereProblemi da Risolvere

�� I problemi che siamo interessati a risolvere sono di natura I problemi che siamo interessati a risolvere sono di natura molto varia:molto varia:

1.1. Trovare il maggiore fra due numeriTrovare il maggiore fra due numeri

2.2. Dato un elenco di nomi e numeri di telefono, trovare il Dato un elenco di nomi e numeri di telefono, trovare il numero di una data personanumero di una data persona

3.3. Problema del lupo, della capra e del cavoloProblema del lupo, della capra e del cavolo

4.4. Dati a e b, risolvere l’equazione ax+b=0Dati a e b, risolvere l’equazione ax+b=0

Introduzione 26

4.4. Dati a e b, risolvere l’equazione ax+b=0Dati a e b, risolvere l’equazione ax+b=0

5.5. Stabilire se una parola precede alfabeticamente un’altraStabilire se una parola precede alfabeticamente un’altra

6.6. Ordinare una lista di elementiOrdinare una lista di elementi

7.7. Creare, alterare suoniCreare, alterare suoni

8.8. Analizzare e riconoscere immaginiAnalizzare e riconoscere immagini

9.9. Salvare e recuperare delle informazioniSalvare e recuperare delle informazioni

10.10. Trasmettere informazioniTrasmettere informazioni

……

Risoluzione di ProblemiRisoluzione di Problemi

�� La descrizione di un problema non fornisce (in La descrizione di un problema non fornisce (in generale) un metodo per risolverlogenerale) un metodo per risolverlo

�� Non tutti i problemi sono risolvibili attraverso l’uso Non tutti i problemi sono risolvibili attraverso l’uso del calcolatore: Esistono classi di problemi per le del calcolatore: Esistono classi di problemi per le quali la soluzione automatica non è proponibile. As quali la soluzione automatica non è proponibile. As

Introduzione 27

quali la soluzione automatica non è proponibile. As quali la soluzione automatica non è proponibile. As esempio:esempio:

❍❍ Se il problema ammette infinite soluzioniSe il problema ammette infinite soluzioni

�� Noi considereremo problemi che ammettono un Noi considereremo problemi che ammettono un metodo risolutivo metodo risolutivo ovvero…ovvero…

�� Problemi per i quali esiste un algoritmo risolutivoProblemi per i quali esiste un algoritmo risolutivo

AlgoritmoAlgoritmo

�� Un algoritmo è una sequenza Un algoritmo è una sequenza finitafinita di mosse/azioni di mosse/azioni che risolve che risolve in un tempo finitoin un tempo finito una una classeclasse di di problemiproblemi

�� L'esecuzione delle azioni nell'ordine specificato L'esecuzione delle azioni nell'ordine specificato dall'algoritmodall'algoritmo consente di ottenere, a partire dai consente di ottenere, a partire dai dati di ingresso, i risultati che risolvono il dati di ingresso, i risultati che risolvono il

Introduzione 28

dall'algoritmodall'algoritmo consente di ottenere, a partire dai consente di ottenere, a partire dai dati di ingresso, i risultati che risolvono il dati di ingresso, i risultati che risolvono il problemaproblema

�� EsecutoreEsecutore è una è una macchina astrattamacchina astratta capace di capace di eseguire le azionieseguire le azioni specificate dall’specificate dall’algoritmoalgoritmo

❍❍ Il calcolatore è un caso particolare di esecutoreIl calcolatore è un caso particolare di esecutore

Esempio di ProblemaEsempio di Problema

�� Problema:Problema: Come si cucina un uovo al burro?Come si cucina un uovo al burro?

�� SoluzioneSoluzione

1.1. Far sciogliere in un tegamino 20g. di burroFar sciogliere in un tegamino 20g. di burro

2.2. Quando il burro assume un colore dorato rompere Quando il burro assume un colore dorato rompere il guscio dell’uovoil guscio dell’uovo

3.3. Far scivolare delicatamente nel tegamino albume e Far scivolare delicatamente nel tegamino albume e

Introduzione 29

3.3. Far scivolare delicatamente nel tegamino albume e Far scivolare delicatamente nel tegamino albume e tuorlotuorlo

4.4. RosolareRosolare

5.5. Quando l’albume è ben rappreso spegnere il fuocoQuando l’albume è ben rappreso spegnere il fuoco

Esempio di ProblemaEsempio di Problema

�� Problema:Problema: Risolvere l’equazione ax+b=0Risolvere l’equazione ax+b=0

�� SoluzioneSoluzione

1.1. leggi i valori di a e bleggi i valori di a e b

2.2. calcola calcola ––bb

3.3. dividi quello che hai ottenuto per a e chiama x il dividi quello che hai ottenuto per a e chiama x il risultatorisultato

Introduzione 30

risultatorisultato

4.4. stampa xstampa x

Algoritmi e ProgrammiAlgoritmi e Programmi

�� Passi per la risoluzione di un problema:Passi per la risoluzione di un problema:❍❍ individuazione di un procedimento risolutivoindividuazione di un procedimento risolutivo

❍❍ scomposizione del procedimento in un insieme ordinato di azioni scomposizione del procedimento in un insieme ordinato di azioni �� AlgoritmoAlgoritmo

❍❍ rappresentazione dei dati e dell’algoritmo attraverso un rappresentazione dei dati e dell’algoritmo attraverso un formalismo comprensibile dal calcolatore (linguaggio di formalismo comprensibile dal calcolatore (linguaggio di programmazione) programmazione) �� ProgrammaProgramma

Introduzione 31Problema

Inizio

Leggi a e b

Sì w > 0 ?

No

w ← a; z ← 0;

Scrivi z = a × b

Fine

z ← z + b w ← w – 1

Dichiarazione: a, b, w, z contengono numeri interi

Prodotto di due numeri

naturali

Algoritmo

Metodo di Risoluzione

Linguaggio di Programmazione

main() { /* prodotto C */unsigned int a, b;int w, z;

scanf("%d %d",&a,&b);z = 0;w = a;while (w > 0) {

z = z + b;w = w – 1;

}printf("%d", z);

}

Programma

Dati e istruzioniDati e istruzioni

�� Tipi di datiTipi di dati❍❍ Numeri naturali o interi o realiNumeri naturali o interi o reali (1, (1, --2, 0.34)2, 0.34)

❍❍ Caratteri alfanumerici Caratteri alfanumerici (A, B, ..)(A, B, ..)

❍❍ Dati logici o booleani Dati logici o booleani (Vero, Falso)(Vero, Falso)

❍❍ Array o vettore di n elementi Array o vettore di n elementi ({1,2,3})({1,2,3})

�� IstruzioniIstruzioni

Introduzione 32

�� IstruzioniIstruzioni❍❍ Operazioni di Input/OutputOperazioni di Input/Output (es. (es. leggileggi, , scriviscrivi))

❍❍ Operazioni AritmeticoOperazioni Aritmetico--logichelogiche (es. (es. max = A + Bmax = A + B))

❍❍ Strutture di ControlloStrutture di Controllo (es. (es. SESE, , RIPETI RIPETI ))

Algoritmi e VariabiliAlgoritmi e Variabili

�� Gli algoritmi sono parametrici:Gli algoritmi sono parametrici:❍❍ producono un risultato che dipende da un insieme di dati producono un risultato che dipende da un insieme di dati

di partenza;di partenza;❍❍ descrivono la soluzione non di un singolo problema, ma di descrivono la soluzione non di un singolo problema, ma di

una intera classe di problemiuna intera classe di problemi strutturalmente equivalenti.strutturalmente equivalenti.❍❍ Esempi:Esempi:

�� l’algoritmo per la moltiplicazione di due numeri specifica l’algoritmo per la moltiplicazione di due numeri specifica come effettuare il prodotto di come effettuare il prodotto di tuttetutte le possibili coppie di le possibili coppie di numeri;numeri;

Introduzione 33

come effettuare il prodotto di come effettuare il prodotto di tuttetutte le possibili coppie di le possibili coppie di numeri;numeri;

�� l’algoritmo per la ricerca di un libro nello schedario della l’algoritmo per la ricerca di un libro nello schedario della biblioteca vale per tutti i possibili libri;biblioteca vale per tutti i possibili libri;

�� ……

Algoritmi e VariabiliAlgoritmi e Variabili

�� Le istruzioni dell’algoritmo Le istruzioni dell’algoritmo fanno riferimento a fanno riferimento a variabilivariabili

❍❍ Somma x ad ySomma x ad y❍❍ Se a>o alloraSe a>o allora❍❍ ……❍❍ Come in matematica una variabile è Come in matematica una variabile è

un sinonimo per indicare un dato un sinonimo per indicare un dato

�� VariabileVariabile: Nome associato ad : Nome associato ad

Memoria

Introduzione 34

�� VariabileVariabile: Nome associato ad : Nome associato ad una locazione di memoria una locazione di memoria

❍❍ Contenitore per datiContenitore per dati

�� Astrazione delle cella di Astrazione delle cella di memoriamemoria

y

x

a

totale

4

8

3

6

Uso delle VariabiliUso delle Variabili

�� All’interno di espressioni,All’interno di espressioni,❍❍ l’esecutore usa il valore contenuto nelle variabili per l’esecutore usa il valore contenuto nelle variabili per

calcolare il risultato dell’espressione,calcolare il risultato dell’espressione,❍❍ per esempio var1per esempio var1 ++ var2 var2 ×× var3 oppure var1var3 oppure var1 // var2 var2 –– var3, var3,

……

�� in istruzioni di assegnamento/assegnazionein istruzioni di assegnamento/assegnazione❍❍ introdurre nel contenitore identificato dal nome della introdurre nel contenitore identificato dal nome della

variabile il valore specificato a destra dell’assegnamento;variabile il valore specificato a destra dell’assegnamento;

Introduzione 35

variabile il valore specificato a destra dell’assegnamento;variabile il valore specificato a destra dell’assegnamento;❍❍ Esempi: Esempi: ❍❍ rr == 35 (assegna 35 alla variabile il cui nome è 35 (assegna 35 alla variabile il cui nome è rr),),❍❍ PiPi == 3,143,14❍❍ ……

L’AssegnazioneL’Assegnazione

�� SintassiSintassi

nomeVariabile = espressione;

…

total=total+ quarters * 0.25;

…

C++: Introduzione 36

�� Calcola il valore di Calcola il valore di espressioneespressione e memorizza il e memorizza il risultato nella posizione di memoria assegnata alla risultato nella posizione di memoria assegnata alla variabile variabile nomeVariabilenomeVariabile

…

L’AssegnazioneL’Assegnazione

…

total=total+ quarters * 0.25;

…

Memoria

total+ quarters * 0.25

Calcola

1.23

Memoria

C++: Introduzione 37

dimes

pennies

quarters

total

4

8

3

0.48

total+ quarters * 0.251.23

Memorizza il risultato in total

dimes

pennies

quarters

total

4

8

3

1.23

Uso delle VariabiliUso delle Variabili

�� in istruzioni di assegnamento combinate con in istruzioni di assegnamento combinate con espressioniespressioni

❍❍ assegna a una variabile il risultato ottenuto dalla assegna a una variabile il risultato ottenuto dalla valutazione di un’espressionevalutazione di un’espressione

❍❍ CircCirc == 22 ×× rr ×× pipi�� il risultato dell’espressione 2il risultato dell’espressione 2 ×× rr ×× pipi viene calcolato viene calcolato

utilizzando i valori contenuti nelle variabili utilizzando i valori contenuti nelle variabili rr e e pipi e il e il risultato viene poi assegnato alla variabile risultato viene poi assegnato alla variabile circcirc;;

Introduzione 38

risultato viene poi assegnato alla variabile risultato viene poi assegnato alla variabile circcirc;;

❍❍ la stessa variabile può comparire in entrambi i lati la stessa variabile può comparire in entrambi i lati dell’istruzione di assegnamentodell’istruzione di assegnamento�� kk= k= k ++ 11�� il valore contenuto in k viene utilizzato per trovare il valore il valore contenuto in k viene utilizzato per trovare il valore

dell’espressione kdell’espressione k ++ 1 che viene memorizzato come nuovo 1 che viene memorizzato come nuovo valore di k.valore di k.

Rappresentazione degli algoritmiRappresentazione degli algoritmi

�� Linguaggio naturaleLinguaggio naturale

�� Diagramma a blocchiDiagramma a blocchi

�� Pseudo codicePseudo codice

Introduzione 39

�� Linguaggio di programmazioneLinguaggio di programmazione

Rappresentazione degli algoritmiRappresentazione degli algoritmi

�� Linguaggio NaturaleLinguaggio Naturale

❍❍ Sollevare il ricevitoreSollevare il ricevitore

❍❍ Attendere il segnale di Attendere il segnale di linea liberalinea libera

❍❍ Comporre il numeroComporre il numero

❍❍ ……

�� Diagramma di flussoDiagramma di flusso

Inizio

Leggi

x e y

d ←x – y

Introduzione 40

……

Sì

d ←x – y

d > 0 ?No

Fine

Scrivi

“max è x”

Scrivi

“max è y”

Diagrammi di flussoDiagrammi di flusso

START

Inizio

END

Fine

I/O

Operazioni di ingresso/uscita

PROCESS

Elaborazione

Introduzione 41

ingresso/uscita

PredicatoPredicato

Selezione a due vie

Sì NoSUB-PROCESS

Sottoprogramma

EsempioEsempio

Esempio:Esempio:dati in ingresso due numeri dati in ingresso due numeri x e y, si calcoli e stampi il x e y, si calcoli e stampi il maggiore.maggiore.

Inizio

Leggi

x e y

d ←x – y

Introduzione 42

Sì

d ←x – y

d > 0 ?No

Fine

Scrivi

“max è x”

Scrivi

“max è y”

Somma dei primi N numeri naturaliSomma dei primi N numeri naturali

Inizio

Leggi n

ris ← 0 i ← 0

Inizio

Leggi n

ris ← n

Introduzione 43

No Sì

Scrivi ris

Fine

i > n ?

ris ← ris + i i ← i +1

No Sì

Scrivi ris

Fine

n < 1 ?

n ← n –1 ris ← ris + n


Inizio

Leggi n

ris ← 0 i ← 0

2

1

T posiz. n i ris note

t01 � ?? ?? ?? Variabili non ancora definite

t02 � 4 ?? ?? Letto il valore 4 e inserito in n

t03 � 4 0 0 i < n ⇒ posiz. 4

t04 � 4 0 0

t05 � 4 1 0 i < n ⇒ posiz. 4

t06 � 4 1 0

Introduzione 44

No Sì

i ← 0

Scrivi ris

Fine

i > n ?

ris ← ris + i i ← i +1

3

4 5

6

t06 � 4 1 0

t07 � 4 2 1 i < n ⇒ posiz. 4

t08 � 4 2 1

t09 � 4 3 3 i < n ⇒ posiz. 4

t10 � 4 3 3

t11 � 4 4 6 i = n ⇒ posiz. 4

t12 � 4 4 6

t13 � 4 5 10 i > n ⇒ posiz. 5

t14 � 4 5 10

t15 � 4 5 10 Stampato risultato (10)


�� Esiste infatti una soluzione analitica: Esiste infatti una soluzione analitica: nn ×× (n(n ++ 1)1) // 22

�� L’algoritmo è molto più semplice (il numero L’algoritmo è molto più semplice (il numero di istruzioni da eseguire è costante e non di istruzioni da eseguire è costante e non dipende dal valore di dipende dal valore di nn).).

Inizio

Leggi n

ris ← n × (n + 1) / 2

2

1

Introduzione 45

ris ← n × (n + 1) / 2

Scrivi ris

Fine

3

4

T posiz. N ris note

t01 � ?? ?? Variabili non ancora definite

t02 � 4 ?? Letto il valore 4 e inserito in n

t03 � 4 10 Calcolato il risultato 10=4×5/2

t04 � 4 10 Stampato risultato (10)

Prodotto di due numeri naturaliProdotto di due numeri naturali

Dati

aa, bb interi positiviww, zz interi

Risoluzione

leggi aa e bbzz ← 0ww ← afinché ww > 0 ripeti

Inizio

Leggi a e b

Dichiarazione: a, b, w, zcontengono numeri interi

Introduzione 46

finché ww > 0 ripetizz ← zz + bbww ← ww – 11

fine cicloscrivi zzfine Sì

w > 0?No

w ←a;

z ←0;

Scrivi z

Fine

z ←z + b

w ←w – 1

Istruzioni e Strutture di ControlloIstruzioni e Strutture di Controllo

�� Le Le istruzioniistruzioni esprimono esprimono azioniazioni che, una volta che, una volta eseguite, comportano una eseguite, comportano una modifica permanentemodifica permanentedello stato internodello stato interno del programmadel programma

�� Le Le strutture di controllostrutture di controllo permettono di permettono di aggregareaggregareistruzioni sempliciistruzioni semplici in istruzioni più complessein istruzioni più complesse

�� Un’istruzione C++ ha la seguente forma:Un’istruzione C++ ha la seguente forma:

C++: Strutture di Controllo 47

�� Un’istruzione C++ ha la seguente forma:Un’istruzione C++ ha la seguente forma:

istruzione istruzione == istruzione semplice istruzione semplice istruzione istruzione == istruzione semplice istruzione semplice

istruzione istruzione == istruzione di controlloistruzione di controllo

Istruzioni SempliciIstruzioni Semplici

�� Qualsiasi Qualsiasi espressioneespressione seguita da un punto e virgola seguita da un punto e virgola è una è una istruzione sempliceistruzione semplice

� Esempi

istruzione semplice istruzione semplice = = espressioneespressione;;istruzione semplice istruzione semplice = = espressioneespressione;;


…

x = 0;

y=y+x;

K=k+1;

…

Istruzioni di ControlloIstruzioni di Controllo

�� Una istruzione di controllo può essere:Una istruzione di controllo può essere:

1.1. una istruzione una istruzione compostacomposta (blocco)(blocco)

2.2. una istruzione una istruzione condizionale condizionale (selezione)(selezione)

3.3. una istruzione di una istruzione di iterazioneiterazione (ciclo)(ciclo)

�� Le istruzioni di controllo sono alla base della Le istruzioni di controllo sono alla base della programmazione strutturataprogrammazione strutturata (Dijkstra, 1969)(Dijkstra, 1969)


programmazione strutturataprogrammazione strutturata (Dijkstra, 1969)(Dijkstra, 1969)

Programmazione StrutturataProgrammazione Strutturata

�� ObiettivoObiettivo: rendere piu’ facile la lettura dei : rendere piu’ facile la lettura dei programmi (e quindi la loro modifica e programmi (e quindi la loro modifica e manutenzione)manutenzione)

�� Abolizione di salti incondizionati (goto) nel flusso Abolizione di salti incondizionati (goto) nel flusso di controllodi controllo


di controllodi controllo

�� La parte di esecuzione di un programma è ottenuta La parte di esecuzione di un programma è ottenuta dalla combinazione di istruzioni elementari tramite dalla combinazione di istruzioni elementari tramite regole di composizione (strutture di controllo) regole di composizione (strutture di controllo)

Strutture di ControlloStrutture di Controllo

Concetti chiave:Concetti chiave:

�� concatenazione o composizione concatenazione o composizione BLOCCOBLOCCO❍❍ istruzioni eseguite in sequenzaistruzioni eseguite in sequenza

�� istruzione condizionale istruzione condizionale SELEZIONESELEZIONE❍❍ ramifica il flusso di controllo in base al valore vero o falso ramifica il flusso di controllo in base al valore vero o falso

di una espressione (“di una espressione (“condizione di sceltacondizione di scelta”)”)


di una espressione (“di una espressione (“condizione di sceltacondizione di scelta”)”)

�� ripetizione o iterazione ripetizione o iterazione CICLOCICLO❍❍ esegue ripetutamente un’istruzione finché rimane vera esegue ripetutamente un’istruzione finché rimane vera

una espressione (“una espressione (“condizione di iterazione”condizione di iterazione”))

Bohm e Jacopini (1966): queste tre strutture di Bohm e Jacopini (1966): queste tre strutture di controllo sono sufficienti per definire tutte le controllo sono sufficienti per definire tutte le funzioni computabilifunzioni computabili

BloccoBlocco


blocco = {

istruzione 1

…

istruzione n

istruzione 1

istruzione 2


istruzione n

}

istruzione 2

istruzione n

Istruzioni CondizionaliIstruzioni Condizionali


�� Struttura di controllo che ramifica il flusso di Struttura di controllo che ramifica il flusso di esecuzione in base al esecuzione in base al

valore valore verovero o o falsofalso di una espressione di una espressione booleanboolean

selezione = scelta


❍❍ valore valore verovero o o falsofalso di una espressione di una espressione booleanboolean(“(“condizione di sceltacondizione di scelta”)”)

Istruzione di Scelta: if Istruzione di Scelta: if


scelta =

if ( condizione )

istruzione if

[else

istruzione if istruzione else

condizionevero falso


❍❍ La parte else e’ opzionaleLa parte else e’ opzionale

[else

istruzione else]

istruzione if

condizionevero falso

Istruzione whileIstruzione while


�� L’istruzione viene L’istruzione viene

istr. while =

while (condizione)

istruzione condizione

vero falso


�� L’istruzione viene L’istruzione viene eseguita finche’ la eseguita finche’ la condizione rimane condizione rimane veravera

�� Puo’ essere eseguita 0 Puo’ essere eseguita 0 o piu’ volteo piu’ volte

❍❍ cfr. con docfr. con do--while while ❍❍ Infinite volte se la Infinite volte se la

condizione è sempre condizione è sempre vera!!vera!!

istruzione

Istruzione doIstruzione do--whilewhile


La condizione è La condizione è

istr. do while = do {

istruzione

} while (condizione); istruzione


�� La condizione è La condizione è controllata a fine controllata a fine ciclociclo

❍❍ Il ciclo viene eseguito Il ciclo viene eseguito 1 o piu’ volte1 o piu’ volte

❍❍ Nel while la condizione Nel while la condizione è controllata a inizio è controllata a inizio ciclociclo

condizionevero

falso

Esempio: Iterazione Controllata da Contatore Esempio: Iterazione Controllata da Contatore

�� Una classe di 10 studenti ha sostenuto un test. Una classe di 10 studenti ha sostenuto un test. Inserire i voti (compresi da 0 a 100) e calcolare la Inserire i voti (compresi da 0 a 100) e calcolare la media. media.

Inizializzazione


?

Inizializzazione

Processamento

Termine

EsempioEsempio

�� Dal Pseudocodice al codiceDal Pseudocodice al codice

Inizializzazione

Dichiara Variabili totale, contatore, voto e media

totale=0

contatore=0Dichiarare variabili

e inizializzarle


Inizializzazione

Processamento

Inserire i 10 valori

while contatore<10

richiedi voto

somma voto a totale

incrementa contatore

Media=totale/10

Calcolare la media

Termine

Stampa la mediaStampa la media

EsempioEsempio

�� Dal Pseudocodice al codiceDal Pseudocodice al codice

while contatore<10

richiedi voto

somma voto a totale

contatore<10vero falso


somma voto a totale

incrementa contatorerichiedi voto

incrementa contatore

somma voto a totale

Informatica - ce.uniroma2.itlopresti/IntroLop_2015x4.pdf · Prof. Francesco Lo Presti Informatica...

Documents

Transcript of Informatica - ce.uniroma2.itlopresti/IntroLop_2015x4.pdf · Prof. Francesco Lo Presti Informatica...