ALGORITMIProf. Pagani Corrado

PRIMI APPROCCI GRAFICI ALLA PROGRAMMAZIONE

Il coding (e la programmazione) è entrato con forza nella scuola anche grazie al progetto MIUR chiamato Programma il futuro (http://programmailfuturo.it/)

Programma il futuro http://studio.code.org/s/20-hour L’artista:

http://studio.code.org/s/20-hour/stage/5/puzzle/1 La contadina:

http://studio.code.org/s/20-hour/stage/9/puzzle/1…

DEFINIZIONI INTRODUTTIVE

PROBLEMA: situazione di difficolta' alla quale si cerca di trovare una soluzione

ISTANZA DI UN PROBLEMA: un singolo problema comprensivo degli specifici dati di input

CLASSE DI PROBLEMI: insieme di problemi semplici che solitamente differiscono solo per i dati di input

ISTANZA DI UN PROBLEMA O CLASSE DI UN PROBLEMA

Problema specifico (istanza): Quali sono le istruzioni per calcolare la somma di 103+439 ?

Soluzione: somma 3 con 9, scrivi 2 e porta 1 somma 3 con 0 e con 1 (il riporto), scrivi 4 e porta 0

Problema generale: Quali sono le istruzioni per calcolare la somma di due numeri interi qualsiasi?

Soluzione: somma la cifra meno significava del primo addendo con la cifra meno significava del secondo addendo……

PROFESSIONALITA’ COINVOLTE

RISOLUTORE: colui che inventa il processo di risoluzione del problema processo risolutivo

programmatore: colui che traduce il processo risolutivo in un linguaggio comprensibile per l’esecutore – elaboratore elettronico

ESECUTORE: colui che esegue i passi presenti nel processo risolutivo Essere umano Elaboratore elettronico (meglio)

ALGORITMO

ALGORITMO: Procedimento che consente di ottenere la risoluzione di un problema o (meglio)di una classe di problemi simili eseguendo, in un determinato ordine, un insieme finito di passi semplici (azioni, o meglio istruzioni); in informatica si intende un metodo per la soluzione di un problema adatto a essere implementato sotto forma di programma.

Parte da dati di input (istanza del problema) e restituisce dati di output

ALGORITMO IMPLEMENTATO IN MODO AUTOMATICO SU UN ELABORATORE

PROGR

Ling.Programm.

Programmatore

PROPRIETA’ DI UN ALGORITMO

Finitezza Numero finito di istruzioni

Terminazione Per ogni istanza deve terminare

Determinatezza Deve sempre essere specificata l’istruzione senza

ambiguità Effettività

L’istruzione deve sempre essere ammissibile Generalità

Dovrebbe essere progettato per risolvere la più grande classe di problemi possibili

LINGUAGGI

LINGUAGGI NATURALI usati dai popoli x comunicare non hanno una struttura completamente rigida possono essere interpretati in + di un modo es) italiano - inglese – russo…

LINGUAGGI FORMALI usati per comunicare con elaboratori elettronici struttura rigida ogni istruzione deve essere interpretabile in un unico

modo Es) linguaggi informatici, linguaggi di programmazione,

linguaggi per la rappresentazione di algoritmi

LINGUAGGI FORMALI

Si dividono in Linguaggi di modellazione

Diagrammi di flusso

Linguaggi di programmazioneAlto livello al livello del programmatore

Java, vb, c++, c# ….

Basso livello Al livello del processore Linguaggio macchina (binario) Assembler

Altri linguaggiHTML, CSS, SQL, ….

TRADUZIONE DEL CODICE SORGENTE IN CODICE ESEGUIBILE

Approccio Compilato Una volta compilato il programma è pronto per essere

utilizzato; si necessita la ricompilazione solo se il programma è stato modificato

Codice sorgente compilatore linker programma eseguibile (in linguaggio macchina)

Approccio Interpretato L’interprete interviene ogni volta che si richiede

l’esecuzione e deve essere installato sulla macchina Codice sorgente interprete Esecuzione tramite

virtual machine/interprete

TIPOLOGIE DI APPLICAZIONI

Applicazioni Stand Alone Console (3^ INF) Desktop con interfaccia grafica (4^ INF)

Applicazioni Client – Server Applicazioni WEB (5^ INF) Web Service (5^ TDP) App per dispositivi mobili (5^ TDP)

Applicazioni Peer 2 Peer

RAPPRESENTAZIONE DEGLI ALGORITMI

Programmazione imperativa

Diagrammi a Blocchi In informatica è una rappresentazione grafica usata

per descrivere un algoritmo Pseudocodice o Notazione Lineare Strutturata

È un linguaggio di progetto il cui scopo è la rappresentazione di algoritmi, può essere utilizzato alternativamente al classico diagramma di flusso.

DIAGRAMMI A BLOCCHI

AMBIENTI PER DIAGRAMMI A BLOCCHI

Ambienti web https://www.draw.io/

Gratuito e non richiede la registrazione

https://cacoo.com/diagrams/

Ambienti Desktop Editor di testi evoluti Plugin

per EclipsePer Visual Studio…..

VARIABILI

Una variabile è un dato (o un insieme di dati insieme di dati) modificabili situati in una porzione di memoria (RAM) suscettibili di modifica nel corso dell'esecuzione di un programma. Una variabile è caratterizzata da un nome (identificatore) univoco (nell’ambito di visibilità) che deve rispettare determinate regole dettate dal linguaggio un tipo di dati ammessiUn valore, modificabile nel corso del programma dall’operazione di assegnamento

REGOLE PER I NOMI DI VARIABILI

si possono usare sia lettere sia numeri (sia alcuni caratteri di punteggiatura come _), ma il primo carattere deve essere una lettera

La maggior parte dei linguaggi (tra cui il C) sono case sensitive, quindi le maiuscole sono distinte dalle minuscole

le parole riservate come if, int, ... non possono essere usate per i nomi delle variabili

Non possono contenere caratteri speciali che hanno altri significati (ad esempio operandi +,-,*,/…)

TIPI DI DATI PER LE VARIABILI

Ad una variabile viene associato un tipo di dato che definisce l’insieme dei valori che la variabile può assumere e (di conseguenza) l’insieme delle operazioni ammesse.

Tipo Descrizione Dimensione (byte)

Char Singolo carattere 1

Short int N° intero 2

int N° intero Dipende dal compilatore

Long int N° intero 4

bool True / false 1 bit

float N° con virgola 4

double N° con virgola 8

string Testo (non presente come dato primitivo in tutti i linguaggi)

ASSEGNAMENTO L’operazione di assegnamento modifica il valore di una

variabile (distruggendo il valore precedentemente contenuto)

Variabile valore Si valuta prima l’espressione a destra della freccia e poi si

assegna il valore alla variabile che si trova a sinistra della freccia

Esempio) A 2 A 7+4

ASSEGNAMENTO ESEMPI ED ERRORI – 1

Si consideri che ogni variabile è di tipo intero.

X 5 La variabile x assume il valore di 5 y 7+3 La variabile y assume il valore di 10 y z+1 La variabile z NON è assegnata ed il calcolo non è determinato z x+y+2 La variabile z assume il valore di 17 3 x 3 non è un nome di variabile y 10-z La variabile y assume il valore di -7 (4+x) 7 (4+x) è una espressione e non è un nome di variabile x x+1 La variabile x assume il valore di 6 y Y*Y Y non è y ed il suo valore è indeterminato y,z 1 y,z non è un nome di variabile

ASSEGNAMENTO CON CHAR E STRING

Un singolo carattere costante di tipo char deve essere racchiuso tra apici singoli (per distinguerlo da una variabile con nome di un carattere)

x e y sono variabili di tipo char x y assegna il valore di y (se c'è) alla variabile x x 'y‘ assegno il carattere y nella variabile x

Una stringa di testo costante deve essere racchiusa tra doppi apici (virgolette); il testo compreso tra virgolette non viene mai valutato dal compilatore (nomi di variabili ed operazioni non vengono svolte)

var1 e var2 e y sono variabili di tipo string var1 var2 assegna il valore di var2 (se c'è) alla variabile var1 var1 cadel se la variabile cadel non esiste, non è possibile eseguire l’istruzione var2 "evans" dentro la variabile var2 inserisco il testo evans var2 'cadel' non è eseguibile in quanto cadel non è un singolo carattere y ";. -/" Corretto: ad y assegno la sequenza di caratteri indicata y "(5/2)*34" Corretto: y vale la sequenza di caratteri (e non il risultato) y "" Corretto: y assume il valore di stringa vuota

ASSEGNAMENTO ESEMPI ED ERRORI – 2

Si consideri che x è di tipo stringa, y e t di tipo carattere, z di tipo intero e k numero con virgola (float):

x “cadel” x assume il testo “cadel” y ”w” y è di tipo carattere, potrebbe assumere il valore w solo se fosse tra singoli apici t x una variabile di tipo carattere non può assumere un valore string t y Sarebbe ammissibile se il valore di y fosse inizializzato z 13*4-50 z assume il valore di 2 k x+y+2 x e y non sono variabili numeriche k 4 k assume il valore di 4 k k+z k assume il valore di 6 k 5.0/z k assume il valore di 2.5 “evans” 7 “evans” non è un nome di variabile ammissibile x “x+1” x assume il valore stringa composto da 3 caratteri x+1 y ‘y*y’ tra apici singoli ci può stare un solo carattere y ’a’ y assume il valore di un singolo carattere ‘a’

ESERCIZI DA SVOLGERE – 1

Si consideri che ogni variabile è di tipo float.

x 15 ____________ y 7+x ____________ y x+1 ____________ z z+y+2 ____________ 3 x ____________ x “3+5-4” ____________ z 10-x ____________ (4%x) 7 ____________ x x+1 ____________ y y*y ____________ y+z1 ____________ 10 3+ 7 ____________

ESERCIZI DA SVOLGERE – 2

Si consideri che x e w sono di tipo stringa, y di tipo carattere, z di tipo intero e k numero con virgola (float):

x “Evans” ____________ y ’w’ ____________ z 3*4-10 ____________ k x+y+2 ____________ k k+3 ____________ z 5/z ____________ “gatto” 7 ____________ x “x+1” ____________ y ‘y*y’ ____________ y ’a’ ____________ w x ____________ x “” ____________

TABELLA DI TRACCIA

X Y Z

4

4 8

4 8 6

4 8 12

2 8 12

I

F

x 4;y x * 2 ;z 18 - x - y;

z <= yz z * 2;x x / 2;

SI

NO

E’ uno strumento utilizzato dal programmatore per simulare il corretto funzionamento di un programma, riportando nelle colonne della tabella il cambiamento dei valori delle variabili dopo ogni istruzione eseguita.

DAB - ESERCIZI SEQUENZA– 1

1. Calcolare il perimetro di un rettangolo date le misure dell'area e della base.

2. Calcolare l'area di un rettangolo date le misure del perimetro e dell'altezza.

3. Calcolare l'area di un triangolo rettangolo sapendo che un cateto è 3/5 dell'altro.

4. Calcolare il prezzo di un articolo conoscendo il prezzo base, lo sconto percentuale da applicare e l’iva.

5. Di un oggetto si conosce il prezzo comprensivo dell'IVA; determinarne il prezzo netto.

6. Un'automobile percorre 20 km con un litro di benzina. Calcolare la spesa necessaria a percorrere 100 km.

DAB - ESERCIZI SEQUENZA – 2

7. Calcolare il successivo del doppio del quadrato di un numero.

8. Calcolare il quadrato del successivo del doppio di un numero.

9. Calcolare la differenza tra il quadrato di un numero e il numero stesso.

10. Calcolare l'area di un trapezio, conoscendo la base maggiore e sapendo che l'altezza è doppia della base minore, mentre la loro somma è uguale alla base maggiore.

11. Un rappresentante di commercio guadagna un fisso mensile di lire 1.000.000 più lire 200.000 per ogni enciclopedia venduta. Quanto guadagna al mese, sapendo che gli viene trattenuto il 18%?

12. Data l’area di un rettangolo determinare il rettangolo di perimetro minimo