Appunti di Informatica per la Comunicazione Lumsa 2024-25 PDF

Lumsa Dipartimento di Scienze umane Corso di studi in Scienze della Comunicazione, Marketing e Digital media Informatica per la comunicazione (A- F e P-Z) Pensiero Computazionale e algoritmi Prof.ssa Alessandra Musolino A.A. 2024-25...

Lumsa Dipartimento di Scienze umane Corso di studi in Scienze della Comunicazione, Marketing e Digital media Informatica per la comunicazione (A- F e P-Z) Pensiero Computazionale e algoritmi Prof.ssa Alessandra Musolino A.A. 2024-25 1 Quanto tempo impiegherò per spostarmi tra due punti della città? Lo chiedo a Google Maps? 7 destinazione 4 3 origine 10 11 8 4 2 Algoritmi di routing  INPUT ELABORAZIONE OUTPUT 18 anni 61 anni 43 anni fa 3 Pensiero computazionale Jeannette Wing, Executive Vice President for Research and Professor of Computer Science at Columbia “è il processo mentale che sta alla University, afferma che il pensiero computazionale base della formulazione dei problemi e delle loro soluzioni così che le soluzioni siano rappresentate in una forma che può essere implementata in maniera efficace da un elaboratore di informazioni sia esso umano o artificiale”. Ovvero è lo sforzo che un individuo deve mettere in atto per fornire a un altro individuo o macchina tutte e sole le “istruzioni” necessarie affinché questi, eseguendole, sia in grado di portare a termine il compito dato. Algoritmo 4 Da dove deriva il termine Algoritmo? Deriva dal nome del matematico persiano del IX secolo Muhammad al-Khwarizmi, scrisse « Algoritmi de Numero Indorum » che può essere considerato il primo trattato del sistema numerale indiano. Il termine Algebra deriva dal titolo arabo di questo testo. Algoritmo: regole, secondo un ragionamento logico, da impiegare per risolvere un problema secondo una sequenza prefissata https://www.treccani.it/enciclopedia/muhammad-ibn-musa-al-khuwarizmi/ 5 Algoritmo e coding Algoritmo: regole, secondo un ragionamento logico, da impiegare per risolvere un problema secondo una sequenza prefissata Coding: permette l’esecuzione dell’algoritmo secondo la sequenza fissata, utilizzando un linguaggio di programmazione. 6 Coding “Quando si diventa agili a leggere e scrivere non lo si fa unicamente per diventare uno scrittore di professione. Ma imparare a leggere e scrivere è utile a tutti. Accade lo stesso per la programmazione. La maggior parte delle persone non diventerà un esperto di informatica o un programmatore, ma l’abilità di pensare in modo creativo, pensare schematicamente, lavorare collaborando con gli altri […] sono cose che le persone possono usare, indipendentemente dal lavoro che fanno”. (Mitchel Resnick, Professore di ricerca sull’apprendimento presso il MIT Media Lab di Boston, Scratch) 7  Pensiero computazionale: note Nel 2006 Jeannette Wing, formulò una definizione ampiamente condivisa: Il pensiero computazionale è un processo di formulazione di problemi e di soluzioni in una forma che sia eseguibile da un agente che processi informazioni. Esso consiste nel pensare a diversi livelli di astrazione; è un’abilità fondamentale per tutti, che dovrebbe diventare la quarta abilità di base oltre al saper “leggere, scrivere e fare di conto”. J.M.Wing, “Computational Thinking,” https://www.cs.cmu.edu/afs/cs/usr/wing/www/ct-italian.pdf 8 Pensiero computazionale (3 A) Automazione Astrazione Pensiero computazionale Analisi 9 Le 3 A del pensiero computazionale Sarà quindi necessario costruire un modello della realtà (astrazione) per trovare una soluzione che possa agire sulla realtà attraverso il modello (automazione). L’esecuzione della soluzione trovata permetterà di analizzare il risultato (analisi) Il processo iterativo che sta alla base del pensiero computazionale è così caratterizzato dalle tre fasi: Ͱ Astrazione Ͱ Automazione Ͱ Analisi } Le 3 A del pensiero computazionale 10 Relazione tra Realtà e Modello Costruzione modello … Sì test No blocco 1 blocco 2 … Interpretazione della soluzione Mondo Reale Ricerca della soluzione 11  Relazione tra Realtà e Modello Il processo di astrazione richiede l’individuazione e la presa in esame delle informazioni significative in un contesto, tralasciando quelle ritenute non rilevanti. Per crearci un modello della realtà in esame, mediante l’astrazione, organizziamo le informazioni a disposizione, per ricercare una soluzione al nostro problema. Le informazioni di cui disponiamo sono quelle fornite in fase di "raccolta dati" nel contesto specifico, ma per valutarne la significatività dovremo utilizzare «strumenti cognitivi» che si appoggiano al nostro bagaglio di conoscenze pregresse. In fase di astrazione,disporremo così di un modello costruito sui «fondamentali», sugli elementi strutturali di base, privi di quei dettagli che offuscherebbero la chiarezza della «visione d’insieme» 12 Algoritmi: lo scenario di riferimento Aumenta ogni giorno l’importanza di applicazioni che ne fanno uso, sono l’asse portante del mondo dell’informatica, ne tessono la trama. Stanno trasformando il nostro mondo e dobbiamo conoscerli per governare il nostro futuro e non farci governare da essi. Non possiamo prescindere da una cultura digitale che permetta di analizzare i dati, dando significato ai fenomeni che i dati rappresentano, usando opportune tecniche algoritmiche. Dobbiamo essere sempre in grado di partecipare attivamente a gruppi di lavori nei quali non necessariamente si rivesta il ruolo di data scientist ma con il data scientist si dovrà interagire in maniera costruttiva Algoritmo 13 Algoritmo in breve Per giungere all’algoritmo si dovrà scegliere una strategia per scegliere i singoli passi da compiere e la loro sequenza Perché l’algoritmo diventi operativo, su un dispositivo di calcolo, dovremo, attraverso il coding, rendere quei passi «eseguibili» da un calcolatore Dovremo cioè, utilizzando un linguaggio di programmazione, procedere ad una formalizzazione utilizzabile da un dispositivo di calcolo automatico 14 Algoritmo in breve → Organizzazione di una sequenza di azioni, → comprensibili da un esecutore (si può trattare di uno strumento automatico), → per raggiungere il risultato atteso (come risolvere un “problema”). ▪ Istruzioni di montaggio di un elettrodomestico ▪ Uso di un terminale Bancomat ▪ Calcolo del massimo comune divisore di numeri naturali Algoritmo 15 Se il problema da risolvere è complesso? Problema complesso Sotto-problema Sotto-problema Sotto-problema Sotto-problema Compito Compito Compito Sotto-problema Sotto-problema Sotto-problema Sotto-problema (task) (task) (task) Compito Compito Compito Compito Compito Compito (task) (task) (task) (task) (task) (task) Divide et impera 16  note Se il problema da risolvere è complesso, per utilizzare agevolmente le tecniche di astrazione, procederemo alla «Decomposizione» del problema in sotto-problemi di complessità minore. (Divide et impera) Procediamo con la stessa metodologia, per scissioni successive, fin quando riteniamo possibile isolare un sotto-problema che possiamo risolvere attraverso un task (codifica, compito svolto) A valle del processo di astrazione, per l’implementazione dell’algoritmo, saranno presi in considerazione i dettagli, che si erano provvisoriamente ignorati quando l’attenzione era posta sull’identificazione della visione d’insieme. 17 Algoritmo – Coding (abilità da acquisire ) Comprensione Modifica Progettazione 18 Abbiamo già compreso che … Algoritmo = descrizione di come si risolve un problema Programma = algoritmo scritto in modo che possa essere eseguito da un calcolatore (linguaggio di programmazione) quindi dovremo disporre della traduzione in Linguaggio macchina = linguaggio effettivamente “compreso” da un calcolatore, caratterizzato da istruzioni primitive semplici attenzione all’efficienza (costi, complessità, velocità) difficile e noioso da utilizzare per un programmatore 19 Algoritmo e Programmazione Posto che possono sembrare equivalenti ma non lo sono: Algoritmo Sequenza di passi volti alla risoluzione di un problema; le istruzioni sono precise, non ambigue ma non necessariamente espresse attraverso un linguaggio di programmazione Programma Implementazione di un algoritmo espresso in un linguaggio di programmazione. Algoritmo 20 Come procedere? Eliminare le ambiguità nella formulazione del problema Individuare il risultato che si vuole ottenere, gli obiettivi da raggiungere Evidenziare le regole da rispettare i vincoli interni ed esterni i dati espliciti ed impliciti Eliminando quindi i dettagli inutili e quelli ambigui Algoritmo 21 Recap: come affrontare la complessità nel progettare algoritmi Posto che un algoritmo rappresenti la soluzione di un problema attraverso una sequenza di passi/istruzioni che portano alla soluzione possiamo procedere scomponendo il problema in sotto- problemi La struttura del problema originario viene così divisa in componenti dotate di minor complessità. Possono essere a loro volta scomposti in sotto-sottoproblemi, e si prosegue fino a giungere a problemi elementari (o primitivi) che possono cioè essere risolti direttamente dall’esecutore. La soluzione del problema originario è garantita attraverso le soluzioni dei singoli sotto-problemi (Tecnica «Divide et Impera») Un algoritmo deve essere corretto ed efficiente. Algoritmo 22 Proprietà degli algoritmi Correttezza L’algoritmo perviene alla soluzione del compito cui è preposto, senza difettare di alcun passo fondamentale Efficienza L’algoritmo perviene alla soluzione del problema usando la minima quantità di risorse fisiche tempo di esecuzione, memoria, … Algoritmo 23 Proprietà di un’azione elementare Finitezza l’azione deve concludersi in un tempo finito Osservabilità l’azione deve avere un effetto osservabile, cioè deve produrre qualcosa Riproducibilità a partire dallo stesso stato iniziale, la stessa azione deve produrre sempre lo stesso risultato Algoritmo 24 Il problema delle tre monete Problema: abbiamo tre monete apparentemente identiche. Solo una è falsa, di peso diverso dalle altre. Possiamo utilizzare una bilancia con due piatti. Vogliamo identificare quella falsa (ha peso diverso) Dobbiamo fare al massimo due pesate. Il problema delle tre monete 1 2 ≠ = 1 3 3 è Falsa * = ≠ * Si ricorda che per ipotesi abbiamo affermato che una è sicuramente falsa 2 è Falsa 1 è Falsa Il problema delle tre monete Ricerca di un possibile algoritmo; Scegliere la disposizione delle monete sulla bilancia Interpretare i risultati per ogni pesata Decidere se l’obiettivo è raggiunto o no Cominciamo con il confrontare due monete,1 e 2 Si aprono due percorsi di calcolo: 1=2 (la moneta falsa è la 3) oppure 1≠2 (sostituiamo la 2 con la 3) 1=3 (la moneta falsa è la 2) Altrimenti (la moneta falsa è la 1) Il problema delle tre monete Problema: abbiamo tre monete apparentemente identiche. Solo una potrebbe essere falsa, di peso diverso dalle altre. Possiamo utilizzare una bilancia con due piatti. Possono essere anche tutte autentiche Vogliamo sapere se una è falsa ed in questo caso se pesa più o meno delle altre due Dobbiamo fare al massimo due pesate.  Il problema delle tre monete ◼ Falsa e più pesante 1 2  Falsa e più leggera 1>2 12 1=2 1