Fondamenti di Informatica 1 Ingegneria Gestionale F OI ... · programmazione ed elementi di...

Università di Roma “Tor Vergata”

1 L1 Fondamenti di Informatica 1 - Vincenzo Grassi – FOI1BIS_GES Sandro Moriggi

Fondamenti di Informatica 1Ingegneria Gestionale

FOI1BIS_GESCORSO COORDINATO CON FOI1_GES PROF. V.GRASSI

obiettivo:introduzione a conoscenze di basedell’informatica

informatica come metodologia di risoluzione diproblemi con l’ausilio di una “macchina”

definire un metodo istruire unarisolutivo macchina____________________________________Docente: Sandro Moriggi

mio orario ricevimento:martedì ore 14:50 - 15:50 aula T7 (forse...)

e-mail: [email protected]

N.B.: nell'OGGETTO della e-mail specificare



"studente:NOME_COGNOME"



• materiale didattico:

1) A. Domenici, G. Frosini: Introduzione allaprogrammazione ed elementi di strutture daticon il linguaggio C++ - FRANCO ANGELI

2) V. Grassi - Note per il corso di Fondamentidi Informatica 1 (a.a. 2000/2001) - dispensa(disponibile sul sito del corso)

è possibile consultare anche3) Deitel & Deitel - C++ Fondamenti di programmazione- APOGEO

è possibile consultare anche4) Derek M. Capper - Introduzione a C++ per le scienzee l'ingegneria - McGraw-Hill

• ambiente di programmazione:

DevC++

in distribuzione libera su:http://www.bloodshed.net/devcpp.html



(per scaricare il software è consigliabile usare ilDownload from Simtel.net (ultima riga della pag.)e poi riferimento "italy")

oppureil link diretto

http://www.simtel.net/autodownload.html?mirror=47&product=17456&key=00ceeaf13c425823e3eb

• per programma del corso, lucidi delle lezioni,dispensa, esercizi, comunicazioni:

consultare:Pagina Didattica S.Moriggi

http://www.uniroma2.it/didattica/foi1bis_ges (in corso di aggiornamento)

i lucidi delle lezioni (sostanzialmente identici) sonoattualmente(12/12/01) disponibili sulla pag. didatticadel prof. V. Grassi

http://www.uniroma2.it/didattica/foi1_no

modalità d’esame (provvisorie, da precisare inseguito):• una prova scritta di metà corso



• una prova scritta finale[probabilmente preceduta da una prova pratica su PC]



applicazioni informatiche:

• animazione• elaborazione di suoni• reti di ipertesti (WWW)• calcolo scientifico (sintesi molecolare,

fluidodinamica, …)• …

cosa c’è dietro?

rappresentare informazione

capacità di

manipolare rappresentazioni



PREMESSA--------

Informaticapresente in tutti i settori dell'industria, dei servizi e dellavita privata

grande diffusione didispositivi elettronici

che effettuanol'elaborazione automatica di informazioni

§ personal computer§ office automation (aspetti amministrativi di

un'azienda)§ scrittura di documenti, fogli elettronici, posta

elettronica§ CAD, CAM (progettazione)§ sistemi di controllo di processi industriali§ basi di dati (gestione e manipolazione di archivi di

dati)§ sistemi di supporto alle decisioni§ sistemi integrati nei dispositivi di uso comuni

[sistemi embedded: televisori, VCR, cellulari,lavatrici, automobili, ...]



Ogni sistema informatico e` costituito da

- una parte HARDWARE (dispositivi elettronici)- una parte SOFTWARE (programmi)

Dal momento che e` il SOFTWARE che

determina caratteristiche e funzionalita`

specifiche di un sistema informatico, ci

concentreremo prevalentemente sugli aspetti

legati allo sviluppo di programmi

(programmazione) per risolvere determinati

problemi



PROBLEMA

Un PROBLEMA nasce• se un SOGGETTO intende raggiungere una META e• se è fallito un primo tentativo per raggiungerla

risolvere un problema significa:

potere identificare

§ STATO INIZIALE

§ PROCEDIMENTO DI ESECUZIONE

§ STATO FINALE

possedere un criterio di verifica del risultatoottenuto

PROCEDIMENTO→← verifica

datiiniziali

dati finali



per attuare il procedimento di soluzione sononecessari:

1. RISOLUTORE: chi si occupa di risolvereteoricamente il problema;impartisce le istruzioni

2. ESECUTORE: qualcuno o qualche cosa chepossiede tutte le capacità per risolvereoperativamente il problema, seguendo leistruzioni fornite dal risolutore

Il risolutore nel formulare le istruzioni relative allasoluzione del problema deve tenere conto dei seguentielementi:§ REPERTORIO dell’esecutore: quali sono le azioni

che l’esecutore è capace di svolgere effettivamente§ FINITEZZA delle azioni da svolgere: il procedimento

deve cominciare e finire dopo l’esecuzione di un certonumero (piccolo o grande) di azioni§ DETERMINISMO delle azioni: ogni azione svolta

dall’esecutore determina, cioè stabilisce senzaambiguità, quale sarà l’azione successiva



ESEMPIO: ricerca di un numero telefonico

fonti di informazione:(A) rubrica telefonica

(B) elenco telefonico

INFORMAZIONI ORGANIZZATE DIVERSAMENTE:

(A) rubrica:§ cognomi e numeri telefonici divisi per gruppi di

lettere (A-B, C-D, ...)§ all'interno di un gruppo cognomi in ordine casuale

(B) elenco:§ informazioni ordinate per cognome e poi per nome§ intestazione associata ad ogni pagina

ricerca di un cognome:dipende da come sono organizzate le informazioni:

(A) rubrica:1. cerchiamo la pagina con la lettera giusta2. all'interno della pagina ricerca sequenziale

(B) elenco:1. apriamo l'elenco in un punto opportuno2. avanti o indietro per gruppi di pagine fino a quella

giusta3. nella pagina avanti o indietro per gruppi di nomi



Per risolvere problemi che richiedono ricerca e/omanipolazione di informazione e` necessario individuare un

METODO RISOLUTIVO,

ovvero

una sequenza di operazioni che ci permette• a partire dalle informazioni a disponibili

(dati di ingresso)• di ricavare i risultati (dati di uscita)

ALGORITMO

la struttura del metodo risolutivo e` legata al modo in cui leinformazioni sono organizzate

per automatizzare la soluzione del problema dobbiamo

RAPPRESENTAREle informazioni edil metodo risolutivo

in un linguaggio eseguibile dal calcolatore(LINGUAGGIO DI PROGRAMMAZIONE)

PROGRAMMA



ALGORITMI E PROGRAMMI

Problemi da risolvere usando elaboratori possono essere dinatura molto varia.

ESEMPI

1) Dati due numeri, trovare il maggiore

2) Dato un elenco di nomi e numeri di telefono (rubrica oelenco telefonico) e un nome, trovare il numero ditelefono corrispondente

3) Data la struttura di una rete stradale e le informazioni suiflussi dei veicoli, determinare il percorso più veloce daA a B

4) Scrivere tutti i numeri pari che non sono la somma didue numeri primi (Congettura di Goldbach)

5) Decidere per ogni programma C++ e per ogni dato iningresso, se il programma termina quando viene eseguitosu quel dato



CARATTERISTICA COMUNE AI PROBLEMI

trasformate →

OSSERVAZIONE SULLA FORMULAZIONE DEIPROBLEMI

§ descrizione non fornisce un metodo risolutivo (si pensiall'es. 3)§ descrizione del problema è talvolta AMBIGUA o

IMPRECISA (ad es., 2 con Mario Rossi che compare piùvolte)§ per alcuni problemi non è noto un metodo risolutivo (ad es.

4)§ esistono problemi per i quali è stato dimostrato che non può

esistere un metodo risolutivo (ad es. 5)

Noi consideriamo solo problemi per i quali è noto esistere unmetodo risolutivo.

Informazioni in ingresso

Informazioni in uscita



PER DELEGARE AD UN CALCOLATORE LASOLUZIONE DI UN PROBLEMA E` NECESSARIO

1) individuare un ALGORITMO che risolve il problema, ovvero

un insieme di passi che, eseguiti in ordine,permettono a partire dalle informazioni a disposizionedi calcolare i risultati

PROPRIETA` DI UN ALGORITMO:

• NON-AMBIGUITA’: le istruzioni devono essereunivocamente interpretabili dall'esecutore

• ESEGUIBILITA’: ogni istruzione deve poter essereeseguita (in tempo finito) con le risorse a disposizione

• FINITEZZA: l'esecuzione dell'algoritmo deve terminare intempo finito per ogni insieme di dati in ingresso



2) rappresentare in un linguaggio di programmazione(LDP)

a) l'algoritmo a) programma(codifica di un algoritmoin un LDP)

b) le informazioni adisposizione

b) dati in ingresso

c) le informazioniutilizzatedall'algoritmo

c) dati ausiliari

d) le informazionifornite al termine

d) dati in uscita

RIASSUMENDO:

PROBLEMA ALGORITMO PROGRAMMA



§ soluzione di un problema=

RAPPRESENTAZIONE + ALGORITMO

?

rappresentazione ( ) = [alt, largh, prof]

rappresentazione ( ) = [ p_alt, p_largh]

algoritmo:(alt < p_alt) e (largh < p_largh)? si ⇒ OK

no⇓

(alt < p_largh) e (largh < p_alt)? si ⇒ OKno⇓

… (quanti tentativi ancora?)



rappresentazione: uso di strumenti formaliper rappresentare in modo simbolicoun “frammento” di realtà

algoritmo: sequenza finita di operazionielementari che manipolano simboli percostruire una soluzione del problema

nota: finito può anche essere molto grande⇓

macchine per eseguire algoritmi

informatica = punto di confluenza di:

• metodi di soluzione (Euclide ~300 a.C., …,al-Kuwarizmi ~1000 d.C., …Hilbert ~1800 d.C.,Gödel, Turing, ~1900 d.C., …)

• macchine per manipolare simboli secondoregole date (abaco ?a.C., …, macchina diBabbage ~1800 d.C., … ENIAC ~1940 d.C.,…)



le macchine sono “stupide”⇓

manipolazione “sintattica”, siamo noi a dare unsignificato ai simboli

Esempio: determinare z = MCD(n,m) n,m∈N

D(n) =def insieme dei divisori di nD(n) = { k | n = k·q, k∈N+, q∈N } N+=N-{0}

z = MCD(m,n) = max{D(m)∩D(n)}

m,n zMCD



algoritmo:

1. prendi due numeri n e m2. scrivi m in una casella di nome x

scrivi n in una casella di nome y

3. se x=0 oppure y=0 allora: termina rispondendo: « problema banale o irrisolvibile » altrimenti: calcola il resto r di x diviso y

se r=0allora: termina rispondendo

« il risultato è il valorescritto in y »

altrimenti: sovrascrivi in x ilvalore scritto in y, sovrascriviin y il valore di r

4. ritorna ad eseguire 3

(l’algoritmo dato è noto come algoritmo di Euclideper il calcolo di MCD)



quali “abilità” (capacità di eseguire operazioni)sono necessarie per eseguire l’algoritmo?

a) leggere e scrivere numerib) eseguire operazioni aritmetichec) seguire un flusso di operazioni

utilizzando tre regole base: i. sequenzaii. sceltaiii. iterazione

“chiunque” sappia fare a, b e c può eseguirel’algoritmo, anche se ignora cosa è MCD

le macchine reali (calcolatori) sanno fare solooperazioni di tipo a, b e c

come fanno macchine così “primitive” adeseguire applicazioni complesse?

tutto è rappresentabile tramite numeri(“digitalizzazione”)



Esempio 1: elaborazione testi

testo⇓

sequenza di caratteri⇓

sequenza di numeri

si usa una tabella analoga a questa:

a ↔ 1 A ↔ 27 . ↔ 53b ↔ 2 B ↔ 28 : ↔ 54c ↔ 3 C ↔ 29 ; ↔ 55d ↔ 4 D ↔ 30 , ↔ 56e ↔ 5 E ↔ 31 (spazio) ↔ 57

• • •• • •• • •

z ↔ 26 Z ↔ 52 …

Ada cade ⇔ 27 4 1 57 3 1 4 5



Esempio 2: elaborazione suoni

onda sonora⇓

“discretizzazione”⇓

sequenza di numeri

12345

••

• • •

• •

•

••

⇓

4 5 4 4 4 2 2 5 3 4



Esempio 3: elaborazione immagini

immagine⇓

“discretizzazione”⇓

sequenza di triple di numeri

123

1 2 3

codifica: casella bianca → 0casella non bianca → 1

decodifica: 0 → casella bianca1 → casella grigia



(1,1,1) (1,2,0) (1,3,0) (2,1,1) (2,2,1) (2,2,0) (3,1,1) (3,2,1) (3,3,1)

codifica

decodifica

123

1 2 3

approssimazione della rappresentazione



come si comunica con una macchina cherappresenta tutto tramite numeri?

si usa un linguaggio fatto di numeri !!!

linguaggio macchina:

0001 1100 1000 01101101 1101 0000 0010

problemi: • difficile (per essere umani) da scrivere, leggere, correggere• legato ad una particolare macchina

linguaggi di alto livello (C++, Pascal,Java,…):

if (5>0) somma = 5 + 6;

• istruzioni “vicine” al linguaggio umano• istruzioni indipendenti da una particolare macchina

⇓necessità di tradurre nel linguaggio macchina

Fondamenti di Informatica 1 Ingegneria Gestionale F OI ... · programmazione ed elementi di...

Documents

Transcript of Fondamenti di Informatica 1 Ingegneria Gestionale F OI ... · programmazione ed elementi di...