1

Software e Algoritmi

Lezione n. 3

Nova24 del 3 marzo 2010“ Il software è un linguaggio, una tecnologia, ma anche un

generatore di linguaggi e di tecnologie, che a loro volta abilitano nuove attività. Creando nuove soluzioni, crea nuovi problemi. Che a loro volta chiedono soluzioni. Che entrano nella vita quotidiana e, servendola, la modificano.

Così, in senso antropologico, il software fa cultura. È originariamente opera di tecnici che però hanno di fatto superato i limiti della loro tecnologia. E imparano a conoscerne le conseguenze, se vogliono che il frutto del loro lavoro sia apprezzabile. Trovandosi dunque a confrontarsi con l’insieme delle dimensioni sociali che di tecnologico non hanno che gli strumenti sui quali si sviluppano. Del resto, come diceva il geografo Pierre Gourou, la cultura in fondo coincide con la tecnologia. Il che, nel mondo attuale, è sempre più evidente.”

http://lucadebiase.nova100.ilsole24ore.com/2010/03/cultware-si-scrive-codice-si-legge-azione.html

2

Obiettivi

3.1 Definizione di Software3.2 Definizione di algoritmo, sue proprietà e formalismi3.3 Metodo top-down, e programmazione strutturata3.4 Open source e Riuso

Software

parte n. 3.1

3

Metodo del problem solving e sviluppo del software

Il problem solving è l’insieme di metodi formali per definire e risolvere un problemaE’ un metodo usata dall’uomo per risolvere tutti i tipi di problemi (economici, statistici, giuridici, etc.) – Pascuzzi, Giuristi si diventa, cap. 3, Il Mulino, 2008.

Tecnica usata anche per sviluppare softwareEsempio di problem solving

Problema - Prelevare contanti in bancaAnalisi - si possono prelevare contanti in diversi modi:bancomat, mediante assegno, chiedendo un prestito, fare una rapina, etc.Soluzioni - si decide per il bancomat, si descrivono i passi operativi e le istruzioni che attivano il bancomatElaborazione - esecuzione delle operazioniRisultati - i contanti

Sviluppare software

Sviluppare software per un calcolatore, ossia per un esecutore-automa, e’ un’attivita’ di “risoluzione di problemi” secondo il metodo del problem solvingEssa è divisa in fasi:

Fasi di risoluzione di un problema con il calcolatore:1. Analizzare il problema da risolvere2. Avere l’idea risolutiva3. Scrivere l’algoritmo formalizzandolo4. Implementare l’algoritmo in un programma di alto livello5. Tradurlo in linugaggio macchina6. Verificare la correttezza del programma7. Documentare, mantenere e aggiornare il programma

4

Creazione di un software: dal problema ai risultati (1/2)

problema

ANALISI

algoritmo

FORMALIZZAZIONE

specificazioni

PROGRAMMAZIONE

programma

1. Comprendere il problema

2. Comprendere le soluzioni –idea risolutrice

4. Algoritmo tradotto in un linguaggio di alto livello

3. Formalizzazione dell’algoritmo

Creazione di un software: dal problema ai risultati (2/2)

programma

TRADUZIONE

eseguibile

ESECUZIONE

risultati

5. Traduzione in linguaggio macchina

6. Valutazione dei risultati

4. Algoritmo tradotto in un linguaggio di alto livello

MANUTENZIONE 7. Manutenere il software

5

Un esecutore particolare: il calcolatore

Se per un esecutore umano le fasi di formalizzazione, programmazione, traduzione in azioni (fasi n.3,4,5) avvengono con una elaborazione cognitiva Per il calcolatore occorrono tre fasi intermedie poiché non è dotato di cognizione autonoma:

Formalizzazione dell’algoritmo secondo un metodo non ambiguoProgrammazione ad alto livello comprensibile al calcolatoreTraduzione in linguaggio comprensibile al calcolatore ossia in linguaggio macchina

I precursori dei calcolatore

Calcolatore di Rodi o di Andikithira 65 a.C.Blaise Pascale – pascalina XVII secoloGottfried LeibnizJoseph Jacquard XVIII secoloCharles Babbage XIX secoloAlan Turing XX secolo - ColossusJohn Von Neumann – macchina programmabile universale - ENIAC

6

Programma & Software, Testi & OrdiniAnche la fase di l’esecuzione del programma necessita di alcune riflessioniPrima del calcolatore il testo era scritto dall’uomo per l’uomo Le operazioni eseguite dall’uomo o da macchine prive di capacità computazionale universaleCon l’avvento del calcolatore:

i programmi sono testi con una particolare proprietà ossia capaci di impartire ordini al calcolatoretesti creati dall’uomo che rendono il calcolatore capace di elaborazioni autonome, astratte, generali rispetto ad una classe di problemi

Software – definizione informatica

“Istruzioni che eseguite da un computer svolgono una funzione prestabilita con prestazioni prestabilite -(programma di alto livello ed eseguibile)

strutture dati mediante le quali i programmi trattano adeguatamente le informazioni - (schemi logici e fisici dei dati)

documenti che descrivono le operazioni e l’uso dei programmi - (documentazione tecnica e manuale utente)”

(R.S. Pressman,Principi di Ingegneria del software, McGraw-Hill 2000)

7

Software: definizione per livelli

Il Software usando il Framework di Zachman

Linguaggio alto livello,linguaggio macchina,esecuzione

Livello fisico

Formalizzazione/documentazione

Livello logico

AlgoritmoLivello concettuale

A=hxb/2

var A intvar h, b intA= hxb/2print A

10001010010011111100100011

8

Software: la definizione

Software: insieme di programmi scritti in qualche linguaggio di programmazione eseguibili dal computer (tutelato con il diritto d’autore anche se..)

software ≠ algoritmosoftware ≠ programmaalgoritmo ≠ programmasoftware = algoritmo + programmi & documentazione + file fisici eseguibili + l’azione di esecuzione

Hardware e firmware: definizioni

Hardware: parte fisica del computer costituita da parti elettroniche e meccaniche (tutelato con il brevetto)

Firmware: insieme di microprogrammi registrati sulle memorie permanenti dei dispositivi elettronici, solitamente introdotti dal costruttore e cablati nell’hardware (tutelato con il brevetto)

9

Strati del software

Utente

Programmi applicativi

Linguaggi e ambienti di programmazione

Sistema operativo

Firmware

HARDWARE

Tipologia del software

Software di basesoftware al servizio di altri software esempio il sistema operativo:

insieme di programmi che governano le funzioni e le risorse primarie del calcolatoreesecuzione di programmioperazioni di ingresso/uscitagestione di fileprotezionerilevazione errori

Software applicativo: dedicato ad uno scopo applicativo

10

Tipologie di software

software real-time - software dedicato alla sorveglianza, all’analisi e all’elaborazione di eventi esterni (rilevamento ditemperature di una piastra di acciaio durante la lavorazione, pilota automatico, sala operatoria)software gestionale - elaborazione dei dati e dei processi aziendali - 70%-80%software scientifico - astronomia, calcolo parallelo, etc.software di Intelligenza Artificiale - sistemi esperti, reti neurali, dimostratori di teoremi, alcuni sono dotati di autonomia, reattività e pro-attività (es. agenti intelligenti)software embedded - programmi residenti in prodotti industriali (lavatrici, forno, termostati ambientali, etc.)software per PC - applicativi di office-automation (fogli elettronici, elaboratori di testi, etc.)software basato su Internet - B2B, B2C, portali, etc. spesso erogato mediante servizi e non prodotti

Categorie di software

Software Genericiprodotti software standardizzati venduti sul mercatole specifiche vengono dettate dal mercato e dal produttore stesso

Software Dedicati o ad hocprogetti ad hoc creati per un determinato clientele specifiche vengono dettate dal cliente

Modello di business diversoProdotto (generici) vs. Progetto (ad hoc)Licenza (generici) vs. Contratto ad oggetto informatico (ad hoc)Metafora del prodotto industriale vs. quello artigianale

11

Materiali di riferimento e Domande possibili

Capitolo 3 del SartorDefinizione di software, hardware e firmwareTipi di software e tipi di modelli di business Relazione fra software, algoritmo e programmaIl problem solving e il softwareLe fasi di produzione di un softwareIl riuso e il software ad hoc nella normativa italiana (CAD e circolare Stanca)Nuovi modelli di business: open source a ASP

Open Source e Riuso

Lezione 3.4

12

Termini del problema (i)

Il mercato della produzione del software si classifica in base a tre fattori:

Proprietà intellettuale del software:software proprietario – il titolare detiene i diritti di

sfruttamento economicosoftware non proprietario – il titolare condivide i diritti

di IPStrategia commerciale:

software commerciale – software a pagamentosoftware non commerciale – software gratuito

Prodotto venduto:codice aperto – codice sorgente e codice oggettocodice chiuso – solo codice oggetto

Termini del problema (ii)

Lo scenario è quanto mai complesso per diversi motivi:si intrecciano definizione “ideologiche” con definizioni giuridiche o tecnologichesul modello “astratto-teorico” si innesca il modello concreto-fattuale (i casi concreti)il confine fra le definizioni spesso non è così chiaramente demarcatola pratica spesso crea modelli “ibridi” non previsti dalla categorizzazione teorica

13

Scenariodiagram by Chao-Kuei

OpenSource

Definizioni: software proprietarioSoftware proprietario

software sviluppato da una o più soggetti (imprese, enti o individui) i quali detengono i diritti di proprietà intellettuale, di sfruttamento commerciale, di utilizzo del softwaregli utenti/clienti possono utilizzare tale software mediante:

licenza d’uso apposito contratto ad oggetto informatico concessione d’uso gratuita da parte del titolare dei diritti

il software proprietario è rilasciato in formato eseguibile, raramente in codice sorgenteil software proprietario non può essere copiato, modificato, distribuito senza l’autorizzazione dal titolare dei diritti ogni utilizzo ulteriore del software da parte di terze parti deve essere regolato tramite contratti di distribuzione o di utilizzo fra il proprietario e le parti

14

Definizioni: software proprietarioSoftware proprietario secondo i tre parametri

introdotti si colloca come segue:ad esso sono connessi diritti di proprietà intellettuale e di sfruttamento economico in capo ad uno o più soggettipuò essere rilasciato sia a pagamento sia gratuitamentepuò essere rilasciato a codice aperto (codice sorgente) oppure rilasciato a codice chiuso (codice oggetto) per tutelare l’oggetto commerciale ossia la forma rappresentativa del codice sorgente

Definizioni: sharewere/freeware

Sharewere /Freewareappartiene alla categoria del software proprietario software distribuito con licenza gratuita disponibile solitamente solo l’eseguibile e non il codice sorgenteè fornito in modalità gratuita con usi di prassi limitati

nelle funzioni (es:tutte tranne il salvataggio, tutte tranne la stampa)negli usi (es: scopi didattici, dimostrativi, di ricerca)nel tempo (es: solo per 30 giorni)

Scopo di questo software:motivi di pubblicità: demo, trialmotivi divulgativi o di ricercamotivi di essere presenti sul mercato: entrare nelle analisi di mercato

15

Definizioni: public domain

Software public domainsenza licenza - gli autori non sono tutelaticodice accessibile a tuttitutti possono modificarlo, copiarlo, usarlo tutti possono distribuirlo in modalità diverse rispetto alle volontà dell’autore e.g. aggiungere e distribuire modifiche proprietarie non più disponibili in codice sorgente, limitando quindi la ridistribuzioneviene costruito senza seguire particolari regole etiche o codici metodologici

Padri fondatori:free-software-fondation

Anni ‘80 Richard Stallman - lancia il progetto GNU per la creazione di un sistema operativo Unix libero e circolabile- fonda la Free software fondationfree software è più una filosofia legata alla libera circolazione del codice sorgenteGNU="Gnu's Not Unix"http://www.gnu.org/

Free as in freedom“Free software is a matter of freedom: people should be free to use software in all the ways that are socially useful.”“The Free Software Foundation (FSF), founded in 1985, is dedicated to promoting computer users' right to use, study, copy, modify, and redistribute computer programs.”

16

Definizioni: free software

Free softwareNel 1985 Richard Stallman, ex ricercatore del MIT, fondò la Free Software Foundation (FSF)

codice sorgente disponibileGPL base: possibilità di distribuirlo, copiarlo, modificarlo, usarlo GNU-General Public LicenceLGPL – Lesser General Public Licence

I quattro gradi di libertà del movimento free software

(freedom 0) Libertà di eseguire il programma per ogni scopo

(freedom 1) Libertà di studiare come il programma lavora e di adattarlo alle proprie esigenze. L’accesso al codice sorgente è un prerequisito per questo.

(freedom 2) Libertà di ri-distribuire copie in modo da aiutare il tuo “vicino”

(freedom 3) Libertà di migliorare il programma e di rilasciare i miglioramenti alla comunità per il beneficio pubblico. L’accesso al codice sorgente è un prerequisito per questo

17

Definizione: open source

Open Sourcefondato da Bruce Perenscodice sorgente disponibilemodifica della licenza GPL di base per consentire la commercializzazione possibilità di commercializzare le distribuzioni derivate dal codice sorgente specificando l’autore e sgravando così l’autore precedente di eventuali responsabilità www opensource.org.

Caso LINUX

1991 Linus Benedict Torvalds - lancia il progetto di creare la prima versione di un sistema UNIX per il processore 80386 ossia per PCAnnuncio fatto al newsgroup UseNet“Hello everybody out there using minix -

I'm doing a (free) operating system (just a hobby, won't be big and professional likegnu) for 386(486) AT clones.”

1994 esce la prima versione definitiva di LINUX 1.0

1997 Transmeta

2003 Open Source Developement Lab

18

Open Source Definition:modifica della GPL di base

1. Libera distribuzione2. Codice sorgente3. Prodotti derivati - permettere di derivare altri prodotti

sempre sottostanti alle stesse modalità di licenza GPL4. Integrità del codice sorgente dell’autore - consentite solo

modalità patch che modificano il codice dell’autore durante la compilazione

5. Nessuna discriminazione per persone e gruppi6. Nessuna discriminazione per tipi di applicazioni7. Distribuzione della licenza8. La licenza non deve essere specifica per un prodotto9. La licenza non deve essere restrittiva di altri software10. Deve essere neutra rispetto a tutte le scelte tecnologiche

Copyleft

Copylefted sw: è free software le cui clausole di distribuzione e uso non permettono di aggiungere restrizioni nelle modifiche successive del software. Questo per garantire che ogni copia, modifica, distribuzione uscita da questo software mantenga ancora lo stesso grado di circolabilità.

Nessun copyright è permesso neppure sulla parte nuova. (OSS) – Il copyleft non significa “senza diritti” ma significa che i diritti permettono le 4 libertà.

19

Non-copyleft

Non-copylefted sw: è il software free le cui clausole di distribuzione permettono a chi modifica, copia, ridistribuisce il software di non mantenere lo stesso grado di libertà ossia di riservarsi dei diritti di tutela di quanto svolto.

Permette un grado di reintroduzione del copyright sulla parte nuova svolta o modificata. (Public Domian, semi-free)

Perché delle Distribuzioni

Spesso le imprese distribuiscono software open source in formato amichevole o corredando il software di base (kernel) di programmi aggiuntivi (sempre open source) che garantiscono alcune migliorie:

stabilità del codiceperformance ottimizzate sulla singola piattaforma hardwareinstallazione veloce ed amichevoleottimizzazione di tutti i moduliassistenzamanutenibilità degli aggiornamenti e degli errori

20

Il modello di business cambiaL’OOS impone quindi di modificare il modello di business dell’industria del software.Il modello classico di business è basato sulla licenza: l’impresa di software investe con risorse interne per produrre il prodotto finale e mediante il prezzo della licenza rientra dell’investimento in un lasso di tempo di 3-5 anni.Il modello basato sull’OOS non può più basarsi sulle revenue delle licenze. Quindi deve basare la sua politica di profitto sui servizi, sulle consulenze, sulle personalizzazioni.L’industria del software è pronta a questa trasformazione?La normativa sì---Codice della PA digitale – art. 69 sul riusoDirettiva Stanca 19/12/2003

ProsCircolabilità della conoscenza

Pari opportunità di accesso al software per i paesi/aziende/cittadini/utenti svantaggiatiCircolabilità delle idee nella ricerca

Maggiore qualità del softwarecommunity di alto valore tecnologico

Maggiore trasparenzaprivacysicurezzavirus &c.

Riduzione dei costi di acquisto del software (?)Minimizzare il potere delle multinazionali di softwareMinimizzare l’utilizzo di brevetti relativi al softwareSmantellamento del modello “licenza d’uso”

21

Cons

Struttura non gerarchica ma a rete distribuita in tutto il mondo: mancanza di efficienza, efficacia, tempestività specie per produrre nuove funzionalità legate al mercato“Non vi è una “mente” strategica e tatticaNon vi è un “referente” chiaro per le modifiche apportate e per l’assistenza/manutenzioneElevai tempi di risposta della communityAlti costi di produzione delle personalizzazioni softwareAlti costi di personale specializzato in queste tecnologieIl modello di business sposta il costo di acquisto sul costo di manutenzione ossia dalla licenza al costo del personale specializzato per la gestione di tale software

AttenzioneCodice aperto non vuole dire open sourceStandard aperto non vuol dire open source

Non è detto che le due definizioni coincidano Codice aperto può significare la facoltà di distribuire il codice sorgente e nulla imporre al fornitore in termini di cessione della titolarità (licenza classica ma con rilascio del codice sorgente)Codice aperto può significare codice aperto + licenza che consenta le 4 libertà fondamentali, a fini specifici, ma non la cessione della titolarità (simil-GPL)Codice aperto –> può indicare la mera traduzione in italiano della dicitura inglese open source ossia con le 4 libertà e quindi di fatto spogliarsi della titolarità (GPL)La normativa italiana non è chiara a questo riguardo: occorre interpretare dal contesto.

22

Sintesi

Creare un modello di business sostenibile per tutelare l’idea di base dell’open source e creare un modo nuovo di fare mercato del software senza ritornare all’era dell’artigianatoSostenere l’industria del software nel passaggio senza uccidere l’industria stessaFare profitto senza uccidere i principi fondamentali dell’open sourceEric Raymond “The cathedral and bazaar”

RIUSO: Obblighi per la PA in materia di sviluppo software

Per la PA vi sono norme che OBBLIGANO le amministrazioni a richiedere ed ottenere la titolarità dei software “ad hoc”

ex Art. 5, Direttiva del 19 dicembre 2003 “Sviluppo ed utilizzazione dei programmi informatici da parte delle pubbliche amministrazioni” – Circolare Stanca – (Gazzetta Ufficiale n. 31 del 7-2-2004)

e a rilasciare in “uso gratuito” tale software alle altre PA (ex Art. 69, D.lgs. 82/2005 – CAD – Codice dell’Amministrazione Digitale)

Introduzione del concetto di RIUSO

23

Possibile scenario di riuso

PA1Fornitore Prodotto αPA2

PA3

Prodotto α

Prodotto β

Prodotto α ≠ Prodotto β

licenza a titolo gratuitoCessione della titolarità

Codice sorgenteCodice oggettoDocumentazionePossibilità di adattamento

Codice sorgenteCodice oggettoDocumentazioneTitolarità

Prodotto δAdattamento

Il riuso e la crisi del modello di business (1/2)

Il riuso del software nella PA è stato introdotto per:

razionalizzare la spesa pubblica in tema di servizi informatici

incentivare il riuso piuttosto che duplicare gli acquisti

rendere autonome le PA di poter modificare, integrare, aggiornare i software senza un legame vincolante con il fornitore

Riuso è spesso assimilabile una licenza proprietaria a titolo gratuito con permessi di rilascio del codice aperto e la garanzia delle libertà fondamntali (semi-GPL)

24

Il riuso e la crisi del modello di business (2/2)

Il riuso accompagnato al fenomeno dell’open source ha fortemente modificato l’industria del software che da un modello basato principalmente sulla licenza d’uso a pagamento (es. Microsoft) è passata a due nuovi modelli di business:

open source – basato principalmente sulla vendita di personalizzazioni e di giornate uomo di assistenzaservizi ASP – application service provider vendita di servizi via rete (es. GoogleDocs, hosting di software, etc.)

Sulla base di questi due nuovi modelli di business sono nati nuovi strumenti giuridici di tutela del software

GPL e LGPL – licenze dell’open sourceContratti/Appalti di servizi ASP

Creative Commonshttp://creativecommons.org/about/licenses/meet-the-licenses

Nuova forma di tutela il diritto d’autore delle opere dell’intelletto favorendo nel contempo la circolabilità della conoscenzaVi sono 6 forme di tutela per attivare delle restrizioni sull’utilizzo del prodotto dell’ingegno non utilizzo commerciale NCno opere derivate NDstesso grado di tutela SA – Share-Alike

25

Domande

Cosa è l’open sourceCosa è il copyleftCosa è il riusoDifferenze fra l’open source e il free softwareDifferenze fra pubblic domain e open sourceDifferenze fra open source e riuso

Algoritmo

parte n. 3.2

26

Informatica – definizione dell’ACM

Come si è visto l’algoritmo è una delle tante fasi della creazione del software e rappresenta la fase concettuale

La fase dedicata alla formalizzazione delle soluzioni in informatica si realizza nella creazione di algoritmi

Del resto la definizione data dall’ACM dell’informatica è:

“L’Informatica è lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione: la loro teoria, analisi, progetto, efficienza, realizzazione e applicazione.” (ACM - Association for Computing Machinery)

Algoritmo - definizione intuitiva

Elenco preciso di operazioni, comprensibile da un esecutore, che definisce una sequenza finita di passi i quali risolvono ogni problema di un dato tipo (classe di problemi).

Esempio: operazioni necessarie per compiere una telefonata, per prelevare denaro dal bancomat, per iscriversi ad un esame, etc.

27

Origini dell’algoritmo

Il concetto di algoritmo è antico e non è strettamente legato al calcolatore: l’esecutore può essere diverso

Sono stati ritrovati algoritmi in tavolette antiche in Mesopotamia risalenti al 1800-1600 a.c.

Il termine algoritmo è la latinizzazione dal nome di un matematico persiano –Al-Khuwarizmi – vissuto nel nono secolo d.c. (Algoritmi de numero Indorum – versione latina, trattato sull’algebra dei numeri arabo-indiani)

Esempio – prelevo contanti dal bancomat, macro operazioni

1. Inserimento della tessera nell’apposito macchinario2. Inserimento del codice segreto3. Scegli importo4 Scelta operazione

4.1 Se l’operazione è possibile allora esegui l’operazioneAltrimenti

4.2 Visualizza messaggio di errore5. Conclusione6. Prelievo tessera7. Prelievo contanti

28

Algoritmo - definizione rigorosa

Sequenza ordinata finita di passi, ripetibili e non ambigui, che se eseguita con determinati dati in ingresso (input) produce in uscita(output) dei risultati ovvero la soluzione di una classe di problemi

dati risultatialgoritmo

Soluzione ad una classe di problemi

Proprietà di un algoritmo

Finitezza - deve portare alla soluzione in un numero finito di passi

Generalità - per classi di problemi

Ripetitività - con gli stessi dati deve fornire gli stessi risultati

Determinismo o Non ambiguità – non dipende dall’esecutore, ossia le azioni sono non ambigue e se eseguite con gli stessi dati da persone diverse si ottengono sempre gli stessi risultati

29

Una ricetta non è un algoritmo

di solito fra gli ingredienti vi sono espressioni ambigue come “un pizzico di sale” o “quanto basta” quindi lasciati alla soggettività la descrizione delle azioni non sono rigorose e necessitano interpretazioni “temperare il coccolato” o “fare un impasto base per torte” – violazione del principio di determinismonon è vero che ripetendo gli stessi passi si ottengono gli stessi risultati – violazione del principio di ripetitività

Dati soggettivi +istruzioni+esecutore = risultati

Un algoritmo si suppone sempre che comunichi con l’ambiente acquisendo dati (dati soggettivi) e restituendo risultatiL’algoritmo è composto da istruzioni che operano su dati prodotti dall’algoritmo stesso o acquisiti dall’esternoL’algoritmo deve essere eseguito da un esecutore(calcolatrice, uomo, meccanismo, ingranaggio meccanico, etc. non necessariamente dal computer)Occorre quindi descrivere le istruzioni utilizzando un linguaggio preciso e generale comprensibile all’esecutore

dati istruzione esecutore risultati

30

Istruzioni = azioni+dati oggettivi

Le istruzioni sono composte da due parti:azione - descrizione delle operazionidati - descrizione degli oggetti manipolati dalle operazioni (dati oggettivi)

esempioInserisci [azione] la tessera [dato] digitare [azione] codice segreto [dato]selezionare [azione] importo [dato]

vi sono istruzioni zerarie, unarie, binarie, ternariestartinizializza Ametti A in Bsomma A e B in C

Rappresentazione logica degli algoritmi: due tecniche

pseudocodifica (o pseudocodice)professionale

verbi di ”esecuzione” (effetto osservabile)condizioniiterazioni

diagramma a blocchi utile a scopi dimostrativi

indica un flusso di istruzioni ovvero la sequenza dei passi da eseguirebasato su simboli grafici

ogni simbolo corrisponde a un costrutto

le due modalità sono semanticamente equivalenti

31

Pseudocodifica

Descrive l’algoritmo con il linguaggio naturale semplificato al fine di togliere le ambiguitàLa descrizione mediante la pseudocodificasi suddivide in due parti:

dichiarazione delle variabilidichiarazione delle azioni

Pseudocodifica - esempio

InizioInizializza MAX a 0Inizializza N1 a 0Leggi N1Finché N1 != 999

Se N1 > MAX alloraAssegna N1 a MAX

Leggi N1Stampa MAXFine

32

I diagrammi a blocchi – (1/6)

la diagrammazione a blocchi o flow chart è un metodo per rappresentare l’algoritmo in modo grafico sintetico e preciso un diagramma a blocchi indica un flusso di istruzioni ovvero la sequenza dei passi da eseguireè basato su simboli graficiogni simbolo corrisponde ad un preciso costrutto o insieme di istruzioni

I diagrammi a blocchi – (2/6)

Un diagramma a blocchi è un insieme di blocchielementari costituito sempre dalle seguenti parti:

blocco di inizioblocco di finenumero finito di blocchi di lettura/scrittura o di blocchi operativinumero finito di blocchi di controllo(opzionale)

33

I diagrammi a blocchi – (3/6)

Istruzioni di inizio e di fine

iniziofine

Rappresenta il flusso (l'ordine) del diagramma

I diagrammi a blocchi – (4/6)

istruzione operativa (effettiva)

Rappresenta una elaborazione

Esempi:

calcola archivia

34

I diagrammi a blocchi – (5/6)

istruzioni di controllo

condizionevero falso

I diagrammi a blocchi – (6/6)

istruzione di input/output

Rappresenta un'operazione di

input/output. Esempi:

scrivi leggi

35

Esempio: conversione miglia-chilometri

Algoritmo

1.Inizio2.Leggi miglia3. Km=miglia*1.6094. Scrivi km5. Fine

inizio

Leggi miglia

km=miglia*1.609

scrivi km

fine

Diagramma a blocchi

Ordinamento emendamenti

Ho ancora emendamenti ?no

Votazione

Inserire nella listadegli approvati

sì

Start

Fine

Es. Votazione emendamenti alla Camera

Approvato?

Inserire nella listadei rigettati

Passa all’emendamentosuccessivo

sìno

Inserimento emendamenti

Stampa listaemendamentiapprovati

Stampa listaemendamentirigettati

36

Spiegazione esempio

Vi sono istruzioni di input/ouput: inserimento emendamenti e stampa liste

Vi sono istruzioni operative: ordinamento, votazione, inserimento nella lista, etc.

Vi è un blocco di istruzioni ripetuto finché non si esauriscono gli emendamenti (ciclo)

Vi è un confronto (if): emendamento approvato o no

Vi è una solo inizio e una sola fine

Art. 75 Cost. Referendum abrogativo

1. Proposta a cura di 5 regioni o da parte di 500.000 cittadini2. Proposta ammissibile valutata della Corte Costituzionale

2.1 allora si fissa la data di votazione2.2 altrimenti decade la proposta

3. Se si vota3.1 si raggiunge il quorum

3.1.1 vincono i sì, allora si abroga la legge3.1.2 vincono i no, allora non si abroga la legge

3.2 non si è raggiunto il quorum4. Fine

37

Ammissibile alla valutazione?no

Votazione

sì

Start

Fine

Es. Referendum abrogativo

Quorum?

AbrogazioneLegge

sìno

Proposta referendum

Firme insufficienti onon ammissibileDecade la proposta

Esito?noQuorum

insufficiente

Esitonegativo

Sviluppo strutturato degli algoritmi e metodologia top-down

Lezione n. 3.3

38

Tecniche di programmazione: verso la qualità del software

Negli anni ’70 la programmazione avveniva come un’operazione artigianale e i metodi erano non omogenei, frammentari, con molti salti incondizionati (goto)

Negli anni ’80 si ipotizzano delle tecniche per migliorare la qualità del software:

Metodo Top-down

Programmazione strutturata

Scomposizione in sotto-algoritmi: metodo top-down

Spesso per semplificare il flusso procedurale si rappresentano insieme più istruzioni in un solo blocco grezzo concettualmente omogeneoSuccessivamente si scompone il blocco in istruzioni sempre più “fini” Si procede dal generale al particolareQuesto metodo di analizzare i problemi partendo da macro-blocchi per poi arrivare alle istruzioni più dettagliate è detto metodo top-down

39

Il metodo top-down

Metodo top-down: scomposizione progressiva del problema e delle azioni (istruzioni) che lo risolvono

Favorisce la divisione del lavoro:Analisi: definizione della struttura generale del programma, dei moduli principali che lo compongono, e delle operazioni astratte svolte da ciascuno di essi, le cosiddette “specifiche”Programmazione: realizzazione dei programmi che svolgono le singole operazioni individuate nella fase di analisi

Art. 75 Cost. Referendum abrogativo

1. Proposta2. Valutazione di ammissibilità della Corte Costituzionale3. Votazione4. Controllo dell’esito5. Fine

40

Start

Valutazione ammissibilitàBlocco2

VotazioneBlocco3

Fine

InizializzazioneBlocco1

Stampa esitoBlocco4

Start blocco1

Proposta

Fine blocco1

Esito=false

Inizializzazione

Verifica=false

Messaggio=“---”

41

Start blocco2

Fine blocco2

AutoritàAmmissibile?

sìno

Messaggio=“Referendum inammissibileautorità non

consentite per legge”

Numero firme ok?

verono

Messaggio=“Referendum inammissibile

mancanza di firme” Verifica=trueVerifica=false

Verifica=false

Valutazione

Fine blocco3

Num Votanti< quorum?

nosì

Votazione

Messaggio=“Quorum non raggiunto”

Esito=false

Esito?sìno

Messaggio=“Esito negativo”

Esito=false

Messaggio=“Esito positivo”

Esito=true

Verifica=true? no

sì

Start blocco3

42

Fine blocco4

Esito=true?nosì

Esito

Abrograzione della legge

Start blocco4

Stampa messaggio

Programmazione strutturatala programmazione strutturata è quel procedimento che permette di ottenere algoritmi facilmente documentabili e comprensibili, manutenibili e di buona qualitàSi utilizzano solo tre tipi di istruzioni (costrutti):

SequenzaSelezioneRipetizione : vi sono tre tipi di ripetizione; condizione in testa (while), condizione in coda (repeat), ripetizione enumerativa (for)

Regole base:i salti (goto) sono rigorosamente proibitiesiste un solo inizio e una sola fine di tutto il programma e di ogni bloccole selezioni si chiudono sempre

43

Potenza della programmazionestrutturata

Le tre strutture presentate (sequenza, condizione, ripetizione) consentono di esprimere qualsiasialgoritmo

Teorema di Bohm-Jacopini:

“Ogni diagramma a blocchi non strutturato è sempretrasformabile in un diagramma a blocchi strutturato

equivalente...”(...con l’eventuale aggiunta di una variabile)

Legge 22 aprile 1941 n. 633 e i diagrammi

Art. 2, 8) i programmi per elaboratore, in qualsiasi forma espressi purché originali quale risultato di creazione intellettuale dell'autore. Restano esclusi dalla tutela accordata dalla presente legge le idee e i principi che stanno alla base di qualsiasi elemento di un programma, compresi quelli alla base delle sue interfacce. Il termine programma comprende anche il materiale preparatorio per la progettazione del programma stesso.Significa che i diagrammi a blocchi sono tutelati e quindi come tali possono essere veicolo di tutela della forma espressa dell’idea risolutrice.

44

Uso dei diagrammi a blocchi in ambito sanitario per definire un protocollo

Diagramma di una procedura amministrativa

Analisi dell’impatto della regolamentazione, Regione Toscana, 2005

45

Esempi di uso dei diagrammi a blocchi

“uso del “diagramma di flusso” (cd. flow chart) negli uffici giudiziari, per monitorare lo stato dei singoli fascicoli, evidenziando i punti – e i soggetti – del procedimento di maggiore sofferenza;” RELAZIONE SULL’AMMINISTRAZIONE DELLA GIUSTIZIA NELL’ANNO 2009, Corte di Cassazione, Gennaio 2010, pag. 123

uso dei diagrammi a blocchi per modellare le procedure amministrative degli enti localiuso dei diagrammi a blocchi per modellare le procedure civili e penali

Conclusioni

I diagrammi a blocchi maggiormente tutelano la forma espressa dell’algoritmo nell’ambito della disciplina del diritto d’autore (art. 2, punto 8)I diagrammi a blocchi sono uno strumento formale e rigoroso per l’organizzazione di un’idea risolutivaI diagrammi a blocchi sono strumento utile per modellare la propria conoscenza all’interno di gruppi interdisciplinari I diagrammi a blocchi sono utilizzati in molti libri giuridici per rappresentare procedure, prassi, procedimenti ed è importante avere dimestichezza con questi strumenti tipici del knowldge worker

46

Materiali di riferimento e Domande possibili

Capitolo 3 del SartorDefinizione di algoritmo e sue caratteristicheFormalizzazione di un algoritmo secondo la pseudocodifica e i diagrammi a blocchiCosa è la sequenza, una condizione, un ciclo, un salto I principali tipi di istruzioni secondo la grafica dei diagrammi a blocchiLa programmazione strutturata: caratteristiche e obiettiviIl metodo top-down: caratteristiche e obiettivi