Fondamenti di Informatica

Problemi, algoritmi e programmi

Carmine Dodaro, Università della Calabria

Problem solving

Problema

Un problema, comunemente inteso, è un ostacolo che rende difficile raggiungere un determinato obiettivo o soddisfare una certa esigenza, frapponendosi tra la volontà dell’individuo e la realtà oggettiva.

Problem solving:

Da Wikipedia: “Un’attività finalizzata all’analisi e alla risoluzione dei problemi usando tecniche e metodi generici o ad hoc”.

​

In informatica la soluzione si ottiene formulando un processo automatico.

​

Problema: la moneta falsa

Problema: abbiamo 3 monete di cui 1 è falsa. Le monete false sono identiche nell’aspetto alle monete reali ma hanno un peso leggermente diverso (non sappiamo se maggiore o minore). Avendo a disposizione una bilancia a due piatti, quante pesate sono necessarie per essere sicuri di capire qual è la moneta falsa?

1. Confrontiamo due monete qualsiasi, ad esempio la prima e la seconda.
2. Se hanno lo stesso peso, allora la terza è falsa.
3. Se non hanno lo stesso peso, confrontiamo la prima con la terza.
4. Se hanno lo stesso peso, allora la seconda è falsa. Altrimenti la prima è falsa.

Problema: la moneta falsa

Problema: abbiamo 9 monete di cui 1 è falsa. Le monete false sono identiche nell’aspetto alle monete reali ma hanno un peso inferiore. Avendo a disposizione una bilancia a due piatti, quante sono le pesate minime necessarie per trovare la moneta falsa?

​

Soluzione: 2 pesate.

1. Confronta due blocchi da 3 monete qualsiasi.
2. Se hanno lo stesso peso, allora la moneta falsa è nelle 3 che non sono state confrontate.
3. Altrimenti considera il blocco con il peso inferiore.
4. In qualunque caso ti rimane un blocco da 3 monete che contiene la falsa. Confronta due monete a caso.
5. Se hanno lo stesso peso, quella rimasta fuori è falsa.
6. Altrimenti quella con il peso minore è falsa.

I passi del problem solving

Risolvere un problema richiede un percorso tra diverse fasi:

• Definire in modo preciso il problema, con eventuali vincoli da soddisfare. Se quest’ultimo è particolarmente complesso, può essere utile anche suddividerlo in problemi più semplici.
• Proporre e valutare soluzioni alternative al problema. In questa fase è opportuno proporre soluzioni di diversa natura e poi si selezionano le soluzioni che sembrano più promettenti a risolvere il problema.
• Realizzare le soluzioni che sono state selezionate.
• Valutare i risultati finali.

Problem solving e informatica

• Nel campo informatico vogliamo che i computer ci aiutino nel processo di risolvere i problemi.
• Ma i computer sono "stupidi", non possono sfruttare il sistema di ragionamento di noi esseri umani.
• Quindi, abbiamo bisogno di un modo o, più precisamente, di un linguaggio per impartire degli ordini ai computer.

Algoritmi e programmi

Algoritmo

Definizione Treccani:

​

“Algoritmo (ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)].

1. Termine che indicò nel medioevo i procedimenti di calcolo numerico fondati sopra l’uso delle cifre arabiche. Nell’uso odierno, anche con riferimento all’uso dei calcolatori, qualunque schema o procedimento matematico di calcolo; più precisamente, un procedimento di calcolo esplicito e descrivibile con un numero finito di regole che conduce al risultato dopo un numero finito di operazioni, cioè di applicazioni delle regole. In partic., a. euclideo, metodo per determinare il massimo comune divisore di due numeri interi a e b, basato su divisioni successive.
2. In informatica, insieme di istruzioni che deve essere applicato per eseguire un’elaborazione o risolvere un problema.
3. In logica matematica, qualsiasi procedimento «effettivo» di computo di una funzione o di decisione di un insieme (o predicato), cioè qualsiasi procedimento che consenta, con un numero finito di passi eseguiti secondo un insieme finito di regole esplicite, di ottenere il valore della funzione per un dato argomento, o di decidere se un dato individuo appartiene all’insieme (o soddisfa il predicato).”

​

Algoritmo

Definizione classica:

Una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito.

​

Da questa definizione emergono delle proprietà degli algoritmi:

• Atomicità: ogni passo è elementare, cioè non si può scomporre ulteriormente.
• Non ambiguità: ogni passo deve essere interpretabile in modo univoco dall’esecutore.
• Finitezza: il numero di passi deve essere finito.
• Terminazione: l’esecuzione deve terminare.
• Effettività: l’esecuzione deve portare a un risultato univoco.

​

​

Algoritmo: input, output ed esecuzione

Un algoritmo riceve in input dei dati in ingresso e produce come output dei dati in uscita.

​

L’esecuzione di un algoritmo consiste nell’applicare i passi elementari nell’ordine specificato dall’algoritmo a partire dai dati in input. Al termine dell’esecuzione dell’algoritmo, si ottiene l’output del programma.

​

Chi esegue un algoritmo? In generale, è una macchina astratta che è capace di eseguire le azioni specificate dall’algoritmo.

Dati

Risultati

Algoritmo

Esecutore

Algoritmi (funzionalmente) equivalenti

Un algoritmo può essere visto come una funzione da un dominio in ingresso (input) a un dominio in uscita (output).

Due algoritmi si dicono equivalenti quando:

• hanno lo stesso dominio di ingresso e lo stesso dominio di uscita;
• in corrispondenza degli stessi valori nel dominio di ingresso producono gli stessi valori nel dominio di uscita.

Efficienza degli algoritmi

Gli algoritmi possono anche essere classificati in base alla loro efficienza, che si misura in base al tempo impiegato per risolvere il problema e allo spazio di memoria occupato durante l’esecuzione.

In generale, il concetto di tempo si misura in termini di passi (istruzioni elementari) dell’algoritmo e non in termini di tempo effettivo di calcolo.

Dall’algoritmo al computer

I processori dei computer sono composti da circuiti elettronici in grado di riconoscere ed eseguire solo un numero limitato di istruzioni semplici, che tipicamente sono del tipo:

• sommare due numeri;
• controllare se un numero è pari a 0,
• copiare i dati da un punto a un altro punto della memoria.

Il linguaggio macchina permette di utilizzare queste istruzioni per codificare un programma.

Linguaggio macchina

Chi progetta i computer deve decidere quali istruzioni includere nel proprio linguaggio macchina. Tipicamente, si tende a progettare dispositivi con istruzioni semplici per ridurre i costi.

​

Tuttavia, questo fa sì che sia abbastanza complicato utilizzare questo linguaggio per codificare i programmi. Per risolvere questo problema in genere si definisce un insieme di istruzioni più comodo da usare rispetto a quelle predefinite.

​

Queste istruzioni formano un linguaggio che si trova a un livello di astrazione più alto rispetto al linguaggio macchina. A questo punto, per poter essere eseguite dal computer, le istruzioni scritte nel linguaggio più alto devono essere in qualche modo convertite nel linguaggio macchina.

Esistono due tecniche principali: compilazione e interpretazione.

Compilazione e interpretazione

La compilazione prevede che le istruzioni scritte in un linguaggio di alto livello vengano convertite, in una fase iniziale, in istruzioni equivalenti scritte nel linguaggio macchina.

​

L’interpretazione invece prevede che venga scritto un programma in linguaggio macchina, chiamato interprete, che accetta in input istruzioni del linguaggio ad alto livello. Questo programma poi si occupa di processare ed eseguire le istruzioni del linguaggio ad alto livello convertendole di volta in volta con la sequenza di istruzioni equivalenti scritte nel linguaggio macchina.

​

La differenza principale tra le due tecniche è che nella compilazione le istruzioni vengono convertite all’inizio del processo, mentre nel caso dell’interpretazione vengono convertite man mano.

Multi-livelli

In generale, è possibile definire una gerarchia (dove sono presenti diversi strati o livelli) di linguaggi. Dove ogni linguaggio a un livello superiore utilizza quello del livello precedente come base.

​

In generale, il linguaggio che si trova a un livello più basso è quello più semplice come insieme di istruzioni ma più difficile da utilizzare, mentre i linguaggi ai livelli più alti sono più complessi come insieme di istruzioni ma sono più semplici da utilizzare.

​

È importante osservare che chi scrive in un linguaggio ad alto livello non deve, in genere, preoccuparsi dei livelli sottostanti o di come le istruzioni vengano convertite (attraverso compilazione o interpretazione). Tuttavia, conoscere come funzionano i vari livelli è importante per capire il reale funzionamento del computer e, soprattutto, in alcune applicazioni specifiche.

Linguaggi di programmazione

Come visto, il linguaggio macchina è poco pratico per scrivere dei programmi.

Per questo motivo, sono nati i linguaggi di programmazione, che sono dei linguaggi a più alto livello che permettono di scrivere delle istruzioni che poi vengono convertite in modo automatico in linguaggio macchina.

Esistono diversi linguaggi di programmazione:

• Python
• C++
• Java
• Javascript
• Kotlin
• ...

​

​

Dall’algoritmo al programma

Codifica: fase di scrittura di un algoritmo attraverso un insieme ordinato di frasi (“istruzioni”), scritte in un determinato linguaggio di programmazione, che specificano le azioni da compiere.

Metodo risolutivo: fase in cui si pensa a come risolvere il problema in termini di passi elementari.

Il programma viene convertito in linguaggio macchina: tramite compilazione oppure attraverso un interprete che esegue il codice.

Problema

Algoritmo

Programma

Linguaggio macchina

Introduzione alla programmazione

Prima di parlare di un linguaggio di programmazione vero e proprio, possiamo anche provare con un “gioco”: https://studio.code.org/s/express-2024/lessons/1/levels/2.

Python

Python

Python è un linguaggio di programmazione di alto livello.

Tra i vantaggi di Python troviamo:

• Pensato per programmare velocemente e modificare i programmi altrettanto velocemente.
• Oggi è uno dei linguaggi più largamente utilizzati.
• Sintassi semplice.

Python: esecuzione

Editor

Controllo sintattico e traduzione

Python Virtual Machine

Byte Code

Rileva errori di sintassi

Rileva errori di esecuzione

Output

Codice

Interprete

Idea intuitiva:

• Il codice sorgente viene passato all’interprete python che controlla che le istruzioni siano sintatticamente corrette.
• In caso affermativo, traduce le istruzioni in bytecode.
• Il bytecode viene eseguito dalla Python Virtual Machine insieme all’input dell’utente per produrre l’output atteso.

Input dell’utente

Tipologie di errori

Errori di sintassi

• Riconosciuti durante la fase iniziale.
• In genere sono facilmente risolvibili.

Errori di esecuzione

• Il programma viene eseguito, ma termina in modo inatteso producendo un errore.
• Sono più complessi da gestire rispetto agli errori di sintassi, ma il messaggio di errore in genere dà un’idea del problema che si è verificato.

Errori logici

• Il programma viene eseguito senza errori ma produce un risultato inaspettato.
• Sono i più difficili da identificare e da risolvere, poiché spesso indicano un errore concettuale all’interno dell’implementazione.

Python: scrittura del codice

Per scrivere il programma si può usare un editor di testo o un ambiente di sviluppo integrato:

• Notepad++ (Windows), CotEditor (MacOS), Gedit (Ubuntu)
• Visual Studio Code
• PyCharm
• Tool online: Online-Python, Google colab

​

Per eseguire il codice si usa l’interprete Python: guida sul sito del corso.

Prima di partire...

Alcuni concetti importanti prima di iniziare a scrivere il codice:

• Attenzione alla distinzione tra maiuscole e minuscole: a è in genere diverso da A.
• Attenzione all’indentazione! L’indentazione indica l’aggiunta di un certo numero di spazi all’inizio di ogni istruzione.
• In genere l’indentazione è composta da blocchi di 4 spazi oppure 1 tab. Python supporta sia l’uso di spazi che l’uso di tab ma dovete essere consistenti nell’utilizzo (conviene impostare l’editor prima di iniziare a programmare).
• Le istruzioni all’interno dello stesso blocco devono avere la stessa quantità di spazio!

Vediamo nel dettaglio!

Per le lezioni su Python useremo un notebook realizzato su google colab e disponibile a questo link: notebook python.