Informatica A

A.a. 2013/2014

Allievi Ingegneria Gestionale

(P-Z)

Introduzione al Corso

Docenti Docente: Dott. ssa Elisa Quintarelli

Dipartimento di Elettronica e Informazione

Email: elisa.quintarelli@polimi.it

Ufficio: I Piano Dipartimento di Elettronica e Informazione

Tel.: 02 2399 3478

Esercitatrice: Ing. Mirjana Mazuran Email: mirjana.mazuran@polimi.it Responsabile di laboratorio: Ing. Laura Mandelli Email: laura.mandelli@tiscalinet.it Sito web del corso: su BEEP

Testi consigliati

Ceri, Mandrioli, Sbattella. Informatica, arte e mestiere. McGraw-Hill, 1999.

Un libro sul linguaggio C (a scelta) - AL KELLEY, Ira Pohl. C Didattica e

programmazione. Addison Wesley. - A. Bellini, A. Guidi. Linguaggio C guida alla

programmazione (seconda edizione). Mc-GrawHill, 2003.

- Programmazione in C, Apogeo.

Organizzazione

Il corso equivale a 10 crediti Lezioni = 52 ore Esercitazioni = 40 ore Laboratorio = 24 ore

Orario: Lezioni ed Esercitazioni: Mercoled 13.15 16.15 Gioved 10.15 12.15 Venerd 8.15 11.15 Laboratorio: Luned o Gioved

Ricevimento:

Luned: 10.30 11.30 Su appuntamento in altri orari o giorni

Laboratori

1 Squadra in Aula L1.4 dalle 8.15 alle 12.15 Ottobre: 28 Novembre: 4,11 Dicembre: 9, 16 Gennaio: 20

2 Squadra nelle Aule CS 0.6 e CS 0.7 dalle 14.15 alle 18.15 Ottobre: 31 Novembre: 7,14 Dicembre: 5, 12 Gennaio: 23

Ambiente di Sviluppo C In laboratorio verr utilizzato

l'ambiente DEV-C++. Per l'installazione necessario:

scaricare l'ambiente dal seguente sito http://prdownloads.sourceforge.net/dev-cpp/devcpp-4.9.9.2_setup.exe?use_mirror=heanet

e salvare il file devcpp-4.9.9.2_setup.exe lanciare il file eseguibile precedentemente salvato

(devcpp-4.9.9.2_setup.exe) seguire l'installazione automatica accettando tutte le

selezioni.

Per il MAC esiste XCode

Modalit di Valutazione

33 punti (che corrispondono a 30 e lode) suddivisi nel seguente modo: Laboratorio: da 0 a 3 punti; superato se

si ottiene un voto non negativo alla prova valutata obbligatoria per chi non ha ottenuto in passato una valutazione positiva.

Due prove in itinere NON OBBLIGATORIE: un massimo di 30 punti per ogni prova.

La prima prova in itinere ritenuta superata se lo studente ottiene un voto maggiore o uguale a 18.

Solo gli studenti che superano la prima prova possono accedere al pre-appello (seconda prova). La seconda prova superata se si ottiene almeno 18.

Il voto finale sar la media dei due voti scritti + il voto di laboratorio.

Modalit di Valutazione

Tre appelli scritti: Febbraio, Luglio e Settembre

Perch studiare informatica?

Perch linformatica a livello mondiale uno dei settori industriali maggiori e pi in crescita

Perch oltre ad essere una tecnologia primaria una tecnologia abilitante di altre tecnologie e di altri settori industriali

Per capire la societ dellinformazione

Perch imparare a programmare passando dalla formulazione del problema alla sua soluzione attraverso lo studio di un algoritmo risolutivo, insegna un metodo, rigoroso, spendibile in tutte le altre attivit.

Informatica Informatica

scienza che studia la rappresentazione e lelaborazione dellinformazione (mediante macchine dette calcolatori elettronici)

non solo la tecnologia dei calcolatori (il calcolatore solo uno strumento) ma anche il modo in cui linformazione viene strutturata ed elaborata automaticamente

Non solo applicazione su calcolatori (uso dei calcolatori in un dominio applicativo)

Include: La produzione di strumenti

informatici La costruzione di applicazioni

Informatica Informatica

Scienza: approccio rigoroso e sistematico Informazione: parte di qualsiasi attivit

umana Rappresentazione: il problema di astrarre i

concetti importanti da quelli trascurabili per poter modellare la realt di interesse. Dobbiamo studiare metodi di rappresentazione appropriati allelaborazione da parte di una macchina digitale

Elaborazione: uso e trasformazione dellinformazione in maniera funzionale agli obiettivi

Il punto di partenza Gli elaboratori sono stati introdotti

con lo scopo di risolvere problemi In modo autonomo non risolvono

niente Deve essere realizzata una

applicazione in grado di risolvere il problema

Informatica Informatica

scienza che studia la rappresentazione e lelaborazione dellinformazione (mediante macchine dette calcolatori elettronici)

Contesto e necessit delluomo

Problemi da risolvere

Informazioni da elaborare

Soluzione del Problema Struttura dei dati da elaborare

Rappresentazione (della soluzione e dei dati) Calcolatore Elettronico

Elaborazione mediante

Funzionalit programmata:

Comportamento determinato dallesecuzione di programmi

Programma: descrizione della soluzione di un problema

Flessibile

Funzionalit intrinseca (o cablata):

Comportamento determinato dalla struttura costruttiva

Efficiente ma rigida

Algoritmo: dal problema alla soluzione

Obiettivo: dato un problema definire un procedimento che

possa essere eseguito automaticamente da un esecutore per risolvere il problema

Definizione di Algoritmo Dato un problema e un esecutore,

lalgoritmo : una successione finita e ordinata di

passi elementari (operazioni e direttive)

eseguibili senza ambiguit (comprensibili) dallesecutore

che risolve il problema dato

Un esempio di algoritmo

Conti correnti on-line: apertura di un conto su XBANK

Registrati sul sito della banca Attendi user-id e password Attendi il PIN1 Effettua un bonifico per aprire il

conto (utilizzando il PIN1) Invia il contratto firmato e i

documenti richiesti Attendi il PIN2 (per sicurezza) . Opera sul tuo C/C

Gli algoritmi e linformatica

Un algoritmo pu essere svolto da un calcolatore

Il calcolatore va istruito quindi serve un formalismo adatto: linguaggio di programmazione

In un modo pi formale, possiamo quindi definire l'algoritmo come una sequenza ordinata e finita di istruzioni che, dato uno o una serie di elementi in input, produce uno o una serie di risultati in output Input sono i dati in ingresso Output sono i dati in uscita I passi sono detti istruzioni

Obiettivi del corso

Capire come le informazioni si rappresentano allinterno di un calcolatore

Conoscere le funzionalit del calcolatore: architettura HW e SW

Imparare a codificare gli algoritmi in linguaggio artificiale: Capacit di individuare una

soluzione algoritmica Conoscenza del linguaggio di

programmazione

Programma Breve rassegna sullInformatica

Nozioni di base sullarchitettura hardware e software di un calcolatore Struttura e principi di funzionamento di un

calcolatore elettronico elementare Codifica binaria dell'informazione Il linguaggio ASSEMBLER

La programmazione del calcolatore: Rappresentazione dello schema risolutivo

(algoritmo) di un problema in una forma adatta all'elaborazione automatica

Rappresentazione e codifica degli algoritmi in un linguaggio formale (programmi)

Linguaggio C

Applicazioni dellInformatica Basi di dati: progettazione e interrogazione

Specifiche

Problema

Algoritmo

Soluzione del Problema in forma adatta alla risoluzione automatica

Espressione della soluzione

Programma Descrizione dellAlgoritmo in forma capibile dal calcolatore

Esecuzione

Architettura HW Blocchi Funzionali

Architettura SW: Sistema Operativo

Esecutore

(Rappresentazione binaria

dellInformazione)

Codifica

Uso del calcolatore per agevolare e potenziare le possibilit di trattamento dellinformazione

Dal problema alla soluzione automatica

Specifiche dei requisiti: descrizione precisa e corretta dei requisiti (verificabilit)

cosa? Progetto: procedimento con cui

si individua la soluzione come?

Soluzione: algoritmo

Esempio: il prodotto di due interi positivi

Leggi W Leggi Y Somma W a se stesso Y volte Scrivi risultato

Prodotto di due interi positivi

1 Leggi W 2 Leggi Y 3 SP = 0 4 NS = Y 5 SP = SP + W 6 NS = NS - 1 7 NS = 0?

Se NO: torna a 5

8 Z=SP 9 Scrivi Z

Procedimento sequenziale

Non ambiguo Formulazione

generale Prevede tutti i

casi (che succede se Y

< 0?)

Propriet degli Algoritmi Procedimenti sequenziali: un passo dopo

laltro secondo un ordine specificato (flusso di esecuzione)

Correttezza: Lalgoritmo perviene alla

soluzione del compito cui preposto, senza difettare di alcun passo fondamentale

Efficienza: Lalgoritmo perviene alla soluzione del

problema nel modo pi veloce possibile e/o usando la minima quantit di risorse fisiche

Determinismo: I passi elementari devono essere eseguiti in modo univoco dallesecutore devono essere descritti in una forma

eseguibile per lesecutore

Propriet degli Algoritmi La descrizione di un algoritmo per un

esecutore deve avere una formulazione generale la soluzione individuata non deve

dipendere solo da valori predefiniti dei dati, cosi che lalgoritmo sia utilizzabile nel maggior numero possibile di casi

gli algoritmi prevedono particolari passi destinati ad acquisire i valori dei dati da utilizzare ed elaborare in ogni particolare esecuzione

Terminazione: Lesecutore deve terminare in

tempo finito per ogni insieme di valori in ingresso Insieme finito di istruzioni e ogni istruzione

eseguita un numero finito di volte Realizzabilit pratica: Lesecutore deve essere

in grado di eseguire lalgoritmo con le risorse a sua disposizione (informazioni + tecnologia)

Propriet degli Algoritmi

Ogni operazione o direttiva deve: terminare entro un intervallo finito di tempo

Es.: calcolare le cifre decimale di , NO!

produrre un effetto osservabile (stato prima dellesecuzione, stato dopo lesecuzione)

Produrre lo stesso effetto ogni volta che viene eseguita a partire dalle stesse condizioni iniziali Es. X=5, y=10 x+y=15

Elementi degli Algoritmi

Oggetti: le entit su cui opera lalgoritmo Dati iniziali del problema, informazioni

ausiliarie, risultati parziali e finali Le informazioni sono dette dati (anche i

risultati parziali e finali) e possono essere variabili o costanti

Operazioni: Interventi da effettuare sui dati Calcoli, confronti, ricopiature, acquisizioni,

emissioni, ecc.

Flusso di controllo: lindicazione delle possibili successioni dei passi dellalgoritmo La correttezza dei risultati dipende non solo

dalla corretta esecuzione delle singole operazioni, ma anche dalla corretta sequenza con cui sono eseguite

Elementi degli Algoritmi

NOTA: Flusso di controllo: la descrizione a priori di

tutte le possibili sequenze nellesecuzione dei passi dellalgoritmo, in particolare di operazioni in alternativa e di operazioni da ripetere pi volte ciclicamente

Flusso di esecuzione: la sequenza di

operazioni effettivamente seguita durante una particolare esecuzione dellalgoritmo e che dipende dai particolari valori che i dati assumono in quellesecuzione

Rappresentazione di un algoritmo destinato

allesecuzione automatica Rappresentazione di un

algoritmo Descrizione, univoca per lesecutore,

di tutte le possibili sequenze di operazioni da eseguire per risolvere il problema dato

Descrizione del flusso di controllo, delle operazioni eseguibili, e degli oggetti su cui agiscono le singole operazioni

E necessario un formalismo di rappresentazione, cio un linguaggio.

Rappresentazione di un algoritmo destinato

allesecuzione automatica Il linguaggio costituito da:

Vocabolario: insieme di elementi per la descrizione di oggetti, operazioni e flusso di controllo

Sintassi: insieme di regole di composizione degli elementi in frasi eseguibili e costrutti di controllo (istruzioni)

Semantica: insieme di regole per linterpretazione degli elementi e delle istruzioni sintatticamente corrette

Linguaggi di descrizione

I linguaggi per descrivere gli algoritmi devono essere noti alluomo che progetta gli algoritmi e al calcolatore che deve eseguirli

Fasi iniziali di progetto: struttura generale dellalgoritmo descrizione rigorosa del flusso di

controllo descrizione semplificata delle

direttive, per es. mediante luso di linguaggio naturale

Linguaggi semi-formali Esempi di linguaggi semiformali:

Schemi a blocchi (o diagrammi di flusso)

elementi grafici per indicare il flusso di controllo e i tipi di operazioni

elementi testuali per descrivere le operazioni e gli oggetti

Linguaggio naturale completamente testuale i costrutti di controllo sono identificabili

anche visivamente

le operazioni sono descritte in italiano Pseudo-codice

completamente testuale costrutti di controllo descritti con la forma

e le parole chiave dei linguaggi di programmazione

le operazioni possono essere descritte in modo informale

IF A>0 THEN A=A+1 ELSE A=0

Schemi a Blocchi

Elementi di base Blocco esecutivo

Blocco di inizio

Blocco di terminazione

Flusso di controllo delle operazioni

Blocco condizionale

operazione

Inizio

Fine

Condizione vera falsa

Schemi a Blocchi

Elementi di base

Blocco di ingresso dati

Blocco di uscita dati

Operazione di ingresso

Operazione di uscita

Schemi a blocchi

Variabili: rappresentate tramite nomi simbolici Le operazioni descritte possono essere

eseguite di volta in volta sui diversi valori assegnabili alle variabili (formulazione generale)

Variabile: contenitore di valori Propriet: una variabile non pu

essere vuota, cio ad una variabile sempre associato un valore

Negli schemi a blocchi operazioni e condizioni sono rappresentate in modo testuale e tramite simboli che rappresentano le operatori aritmetici, di confronto, ecc.

Regole di composizione ed interpretazione degli

elementi Composizione degli elementi

flusso di controllo dellalgoritmo, cio tutte le

possibili sequenze di blocchi da eseguire Un solo blocco di inizio Almeno un blocco di terminazione Dal blocco di inizio e da ogni blocco esecutivo

deve uscire una sola freccia Se per ogni blocco ce un solo blocco

successivo: flusso di controllo sequenziale (sequenza)

Da ogni blocco condizionato devono uscire due frecce contrassegnate dalle indicazioni vero (si) e falso (no)

Condizione vera falsa

Inizio

operazione

Regole di composizione ed interpretazione degli

elementi Il flusso di controllo non pi sequenziale se

dopo un blocco si possono presentare diverse alternative. In questo caso si usa un blocco di selezione

Dal blocco di selezione escono due frecce che devono essere contrassegnate dal valore vero o falso. Il successivo blocco da eseguire dipende dal valore della condizione

In tutti i casi -in esecuzione- unica la scelta del blocco successivo da eseguire

Condizione vera falsa operazione1 operazione2

Condizione vera falsa operazione1 operazione2

Esempio Prodotto di due numeri

interi positivi Diagramma di flusso con direttive in

italiano

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

Moltiplica intero W per intero Y e denota

il risultato con Z

Fine

Acquisizione dallutente dei particolari valori da considerare per i due fattori del prodotto e da assegnare alle variabili W e Y

Operazioni di elaborazione, valide per qualsiasi valore dei dati

Emissione allutente del risultato dellelaborazione

Variabili W, Y, Z intere

W, Y, fattori di ingresso

Z risultato in uscita

Operatori ed espressioni Operatori aritmetici: +, -, , /, ...

agiscono sugli operandi (variabili o costanti) producono un valore numerico

Operatori di confronto: >, =,

Esempio 2 Prodotto di due interi

tramite somme ripetute Algoritmo: somma W a se stesso

tante volte quanto vale Y

Variabili: W,Y intere (valori in ingresso) Z intera (valore in uscita)

Variabili ausiliari: NS intera (contatore del numero di

somme ancora da eseguire) SP intera (valore della somma

parziale)

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

SP:=SP+W

NS:=NS-1

NS>0

no si

Z:=SP

Acquisizione dei dati in ingresso e attribuzione dei loro valori a W e Y

Inizializzazione delle variabili ausiliarie

Corpo del ciclo

Valutazione della condizione di uscita dal ciclo

Emissione del risultato

Schema a Blocchi con ciclo a condizione finale (lalgoritmo corretto se Y>0)

Flusso di controllo ciclico

Permette di esprimere literazione di un insieme di istruzioni (corpo del ciclo)

Il corpo del ciclo ripetuto un numero finito di volte

La ripetizione controllata dalla valutazione della condizione di permanenza del ciclo

variabile di controllo del ciclo inizializzata prima di entrare nel

ciclo condizione di permanenza

funzione della variabile di controllo corpo del ciclo

contiene la modifica della variabile di controllo

CICLO A CONDIZIONE FINALE CICLO A CONDIZIONE INIZIALE

Schema a blocchi con ciclo a condizione iniziale (lalgoritmo corretto per Y>=0)

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

SP:=SP+W

NS:=NS-1

NS>0

no

si

Z:=SP

SP:=SP+W

NS:=NS-1

NS>0 no

si

Algoritmo in linguaggio naturale per calcolare il prodotto di due numeri con

somme ripetute ( a controllo iniziale)

Leggi W Leggi Y Azzera il prodotto Le somme da fare = Y Ripeti se hai ancora somme da

fare | somma W al prodotto |_ sottrai 1 ai cicli ancora

da fare Scrivi il prodotto

Algoritmo in linguaggio naturale per calcolare il prodotto di due numeri con

somme ripetute ( a controllo finale)

Leggi W Leggi Y Azzera il prodotto Le somme da fare = Y Ripeti | somma W al prodotto | sottrai 1 ai cicli ancora

da fare |_ fintantoch hai ancora

somme da fare Scrivi il prodotto

Algoritmo con esecutore calcolatore per lesempio

precedente (ciclo a condizione finale)

int main () { int w,y,z,sp,ns; /*dichiarazione delle variabili */ leggi(w); leggi(y);

sp=0; /*inizializzazione*/ ns=y; /*inizializzazione*/

/*ciclo a condizione finale: lalgoritmo

e corretto solo nellipotesi y>0 */ do { sp=sp+w; ns=ns-1;

}while (ns>0); z=sp; scrivi (z);

}

Algoritmo con esecutore calcolatore per lesempio precedente

(ciclo a condizione iniziale) int main () { int w,y,z,sp,ns; /*dichiarazione delle variabili */ leggi(w); leggi(y);

sp=0; /*inizializzazione*/ ns=y; /*inizializzazione*/

/*ciclo a condizione iniziale:

lalgoritmo e corretto solo nellipotesi y>=0 */

while (ns>0) { sp=sp+w; ns=ns-1;

} z=sp; scrivi (z);

}

Raffinamenti Successivi

Nelle prime fasi di progetto si trascurano i dettagli

Man mano che il progetto evolve si conosce meglio il problema

Uno dei raffinamenti tipici: VERIFICA DEI DATI IN INGRESSO

Lutente pu commettere errori nellimmissione dei dati

si verifica che i dati immessi siano accettabili rispetto alle ipotesi di correttezza dellalgoritmo

Esempio precedente: lalgoritmo non fornisce valori corretti per valori negativi di Y

Y >= 0 ?

ESEMPIO: verifica dei dati in ingresso

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

Z:=SP

SP:=SP+W

NS:=NS-1

NS>0 no

si

Y>=0 no si

Scrivi: Secondo fattore Negativo

Ipotesi: lalgoritmo non calcola il prodotto nei casi in cui Y < 0

Flusso di controllo condizionale

Costrutto di selezione semplice Si utilizza quando alcune operazioni possono

essere o non essere eseguite, in dipendenza del verificarsi di una condizione

Si esprime tramite un un blocco condizionale. Lungo uno dei due rami uscenti sono collocati i blocchi che descrivono le operazioni da eseguire; laltro riguarda le operazioni da non eseguire

Costrutto di selezione doppia Si utilizza quando, in dipendenza del verificarsi

di una condizione, si devono eseguire operazioni alternative

Si esprime tramite un blocco condizionale. Lungo uno dei due rami uscenti sono collocati i blocchi che descrivono le operazioni da eseguire in un caso; laltro riguarda le operazioni da eseguire in alternativa

Ipotesi: i due fattori possono essere positivi, nulli o negativi

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

NS:=Y

Fine

CS:=1

Z:=SP

SP:=SP+W

NS:=NS-1

NS> 0? no si

no si Y>=0 ?

NS:=-Y

CS:=-1

CS=1? no si

Z:=-SP

SP:=0

In linguaggio naturale: Leggi w e y Controlla e ricorda se y0 | sp=sp+w | ns=ns-1 se cs==1 z=sp altrimenti z=-sp scrivi(z);

Codifica in C int main () {int w,y,z,sp,ns,cs;/*dichiarazione variabili*/

leggi(w); leggi(y); if (y>=0) { ns=y; cs=1; } else /*y negativo*/ { ns=-y; cs=-1; } sp=0; /*inizializzazione*/ while (ns>0) { sp=sp+w; ns=ns-1; } if (cs==1) {z=sp;} else {z=-sp;} scrivi(z); }