Dal problema al programma: le basi della programmazione e degli algoritmi

Conosciamo gli algoritmi e i linguaggi

Cosa studieremo

• Riconoscere un problema e saperlo affrontare
• Riconoscere un algoritmo e un programma
• Riconoscere un linguaggio di programmazione ad alto livello
• Riconoscere un linguaggio macchina

I problemi e la loro soluzione

Ogni giorno affrontiamo problemi che variano in complessità Alcuni di questi problemi sono risolvibili velocemente o perché sono semplici, oppure perché li abbiamo già svolti in passato Altri sono molto difficili, se non impossibili, da risolvere specie se ci mancano delle conoscenze o delle informazioni necessarie alla loro risoluzione

• Ripartire il costo di una cena
• Organizzare impegni
• Calcolare la distanza tra la Terra e il Sole

I problemi e la loro soluzione

Ogni giorno affrontiamo problemi che variano in complessità Alcuni di questi problemi sono risolvibili velocemente o perché sono semplici, oppure perché li abbiamo già svolti in passato Altri sono molto difficili, se non impossibili, da risolvere specie se ci mancano delle conoscenze o delle informazioni necessarie alla loro risoluzione

• Ripartire il costo di una cena
• Organizzare impegni
• Calcolare la distanza tra la Terra e il Sole

I problemi e la loro soluzione

Per individuare la soluzione bisogna comprendere bene il problema Bisogna effettuare un'analisi Nei casi più complessi è approfondita della situazione necessario individuare una strategia risolutiva Modalità, approccio con cui si risolve il problema ovvero, l'idea tramite cui il programmatore, sfruttando intuito, esperienza, fantasia e intelligenza affronta il processo creativo per trovare la chiave di soluzione del problema

Esempio: il contadino, il lupo, la capra e il cavolo

Situazione: sulla riva di un fiume ci sono un contadino, un lupo, una capra e un cavolo che devono attraversare un fiume con una piccola barca: su di essa è possibile portare soltanto una cosa alla volta Problema come può il contadino attraversare indenne il fiume, salvando «capra e cavoli», sapendo che se vengono lasciati da soli il lupo con la capra, oppure la capra con il cavolo, i primi divorano i secondi?

Esempio: il contadino, il lupo, la capra e il cavolo

La situazione descritta è sufficientemente chiara da non necessitare di ulteriori delucidazioni. Iniziamo quindi ad analiz il problema Analisi del problema.

• Obiettivo: consentire al contadino di traghettare le 3 risorse da una parte all'altra del fiume
• Vincoli del problema:
  • Limite massimo di risorse traghettabili per volta: 1 unità
  • Non è possibile lasciare lupo e capra soli
  • Non è possibile lasciare capra e cavolo soli

Esempio: il contadino, il lupo, la capra e il cavolo

Il nostro compito è quello di trovare la soluzione di questo problema in modo tale da non violare i vincoli analizzati. In altre parole dobbiamo suggerire al contadino quali azioni compiere (cosa fare) e in che ordine eseguire tali azioni come fare) Strategia risolutiva. In questo caso consiste nell'individuazione della corretta sequenza delle operazioni che il contadino-traghettatore deve eseguire per compiere con esito positivo la traversata 1 Tali procedure devono essere comunicate ad altre persone

Soluzione: il contadino, il lupo, la capra e il cavolo

La soluzione viene descritta solitamente indicando l'insieme delle operazioni (passi) che devono essere effettuate, nell'ordine riportandole in cui devono (sequenza di essere eseguite operazioni) Questa soluzione è facilmente comprensibile da tutti? È universale?

Soluzione: il contadino, il lupo, la capra e il cavolo

È di fondamentale importanza che l'esecutore sia in grado di comprendere le istruzioni che permettono di risolvere il problema e, inoltre, sia in grado di eseguirle

Il concetto di algoritmo

Per trovare la soluzione di un problema è necessario

1. Analizzare e comprendere il problema
2. Individuare la strategia risolutiva, cioè trovare l'idea che ci porta al raggiungimento del nostro obiettivo senza violare i vincoli analizzati

IL PROBLEMA L'ANALISI L'IDEA (LA STRATEGIA) LA SOLUZIONE (L'ALGORITMO) Quando la strategia risolutiva è stata definita bisogna «scrivere» le singole istruzioni che l'esecutore deve compiere, in sequenza, una dopo l'altra

Il concetto di algoritmo

L'insieme delle istruzioni ordinate che permettono di risolvere un problema è detto algoritmo Definizione: l'algoritmo è una sequenza ordinata di passi semplici che hanno lo scopo di portare a termine un compito, a volte anche complesso Proprietà degli algoritmi:

• Chiaro e comprensibile
• Generale, valido per tutti i casi possibili

Esempio: una ricetta in cucina è, a tutti gli effetti, un algoritmo, dato che descrive, a partire dagli ingredienti, le operazioni che devono essere eseguite passo passo, in sequenza, per ottenere il piatto desiderato

Il concetto di algoritmo

inizio riempi una pentola d'acqua > poggiala sul fornello e accendi la fiamma aspetta un po' No è cotta? Sì spegni la fiamma V scola impiatta filo d'olio > Sì formaggio? No grattuggiare > servi in tavola > si mangia! aspetta un po' No l'acqua bolle? Sì > metti il sale butta la pasta

Il linguaggio che descrive l'algoritmo

Un algoritmo deve essere descritto in modo chiaro, in un linguaggio che sia comprensibile per il suo esecutore L'esecutore non è sempre un umano, potrebbe essere anche una macchina, ad esempio il nostro computer La descrizione di un algoritmo in linguaggio naturale prende il nome di pseudocodifica Se per un umano è sufficiente descrivere le istruzioni a «parole», ovvero con un linguaggio naturale oppure in forma grafica utilizzando diagrammi a blocchi ( flowchart) per una macchina bisogna individuare un modo particolare che ci permetta di comunicare con essa

Esempio di pseudocodifica

Scriviamo la pseudocodifica dell'algoritmo che ci consente di inviare un messaggio whatsapp

1. Accendi il telefono
2. Seleziona l'applicazione whatsapp
3. Se il numero del destinatario è presente in rubrica
   1. Seleziona il contatto scorrendo l'elenco
   2. Altrimenti, digita il numero sulla tastiera
4. Compila il messaggio da inviare
5. Clicca sul tasto «invio»

I linguaggi di programmazione

La codifica usata precedentemente non è univoca poiché possiamo descrivere le stesse operazioni utilizzando una terminologia diversa o anche sequenze di istruzioni diverse senza compromettere la correttezza dell'algoritmo Inoltre, potremmo avere casi più articolati come quello in cui la conversazione è già presente nell'applicazione oppure quello in cui l'applicazione non è presente e necessita di essere installata Né la descrizione in linguaggio naturale né i diagrammi a blocchi sono adatti per scrivere programmi che devono essere eseguiti dagli elaboratori elettronici

I linguaggi di programmazione

Né la descrizione in linguaggio naturale né i diagrammi a blocchi sono adatti per scrivere programmi che devono essere eseguiti dagli elaboratori elettronici Elaboratori elettronici: tutti i dispositivi che «hanno al loro interno» un sistema programmabile, cioè un microprocessore Il microprocessore è un dispositivo in grado di comprendere istruzioni codificate in binario Quindi Nella memoria di un dispositivo che esegue un programma deve essere presente il codice binario I Questo programma è detto programma binario o codice eseguibile in linguaggio macchina

I linguaggi di programmazione

Pseudocodifica Troppo vicino al linguaggio naturale umano Inadatto per gli elaboratori elettronici Codice binario Adeguato per gli elaboratori elettronici Troppo complesso per l'uomo, troppo a basso livello Bisogna individuare una soluzione intermedia «Invenzione» di linguaggi di programmazione ad alto livello

I linguaggi di programmazione

Possiamo quindi sintetizzare in 2 tappe fondamentali la nascita della programmazione Inizialmente i programmatori producevano codice binario. Il processo era lungo:

1. Si scriveva l'algoritmo in linguaggio naturale
2. Lo si riscriveva avvicinandosi sempre di più alla descrizione con le sole operazioni che la CPU era in grado di eseguire
3. Lo di zeri e uno in una serie

Oggi per ottenere questa conversione si è ricorsi a un apposito programma, chiamato compilatore (o traduttore), in grado di trasformare in codice binario un programma scritto utilizzando un linguaggio vicino al programmatore, cioè ad alto livello, ma composto da poche parole (parole chiave o riservate), scritte con una sintassi molto rigorosa

Il compilatore

Il compilatore è a sua volta un programma Analizza le istruzioni scritte in linguaggio di programmazione una per una Genera il codice macchina In questo formato il codice prende anche il nome di programma eseguibile (executable), proprio perché in questo formato è eseguibile dal processore

Conclusione

Per scrivere un programma che risolve un problema dobbiamo seguire questi step

1. Individuare l'algoritmo
2. Tradurlo in un linguaggio di programmazione ad alto livello che è un linguaggio formale, rigoroso e composto da un insieme di regole lessicali e sintattiche come ogni linguaggio parlato
3. N.B .: Il linguaggio di programmazione da usare è scelto dal programmatore
4. Compilare il codice prodotto per ottenere codice binario eseguibile