Concetti Chiave
- La risoluzione di un problema richiede la comprensione dei dati iniziali (Input) e il risultato atteso (Output).
- Un algoritmo è un insieme di istruzioni con caratteristiche di finitezza, determinazione, terminazione, effettività e generalità.
- Gli esecutori di un algoritmo possono essere intelligenti, che usano conoscenze pregresse, o automatici, che seguono le istruzioni meccanicamente.
- L'efficacia di un algoritmo riguarda la sua capacità di risolvere un problema, mentre l'efficienza si riferisce alle risorse necessarie per la sua esecuzione.
- Il teorema di Jacopini-Bohm stabilisce che ogni algoritmo può essere rappresentato tramite sequenze, selezioni e iterazioni, semplificando la programmazione.
Problema: situazione da risolvere per ottenere un certo risultato.
Cosa prevede la risoluzione di un problema?
a) comprensione dati iniziali a disposizione (Input);
b) ciò’ che si vuole ottenere (Output).
Questa è l’analisi dei dati, ossia individuare i passi, o meglio, le operazioni che bisogna compiere (procedura) per ottenere il risultato atteso.
Analisi ---> Procedura ---> Risultato
Quali sono le caratteristiche di un algoritmo?
La procedura da seguire per risolvere il dato problema è in informatica universalmente nota con il termine algoritmo.
Algoritmo: è un insieme di regole (istruzioni) aventi le seguenti caratteristiche:
1. finitezza: un A. è composto da un numero finito di istruzioni (passi elementari);
2. determinatezza: deve essere definito e preciso (le istruzioni non devono essere ambigue);
3. terminazione: dopo l’esecuzione di un numero finito di passi, l’algoritmo deve terminare;
4. effettività: l’azione specificata in ogni passo dell’algoritmo deve essere effettivamente eseguibile dall’esecutore (*) preposto per l’esecuzione dell’algoritmo stesso; non avrebbe senso infatti prevedere in un algoritmo azioni che l’esecutore designato non è in grado di compiere;
5. generalità: un algoritmo dovrebbe essere progettato per risolvere non tanto uno specifico problema, quanto una classe di problemi simili.
Esecutori e complessità degli algoritmi
*esecutore: “chi” è preposto all’esecuzione dei singoli passi specificati in un algoritmo. In genere si usa classificare gli esecutori in esecutori intelligenti, che risolvono i problemi applicando le conoscenze acquisite nel corso della propria attività, ed esecutori automatici, che risolvono in problemi eseguendo meccanicamente i passi di un algoritmo senza acquisire nuove conoscenze.
In generale si può dire che non esiste un algoritmo univoco per risolvere un determinato problema.
Nel mondo della programmazione individuare un algoritmo adatto a risolvere un dato problema non è, in generale, cosa semplice. La questione non riguarda solo l’efficacia, cioè il fatto che l’ A. risolva il problema in esame. Un altro elemento critico è l’efficienza, ovvero quanto costa, in termini di risorse, l’esecuzione del nostro algoritmo (es, eccessiva occupazione della memoria).
Rappresentazione grafica degli algoritmi: flow – chart
Teorema di Jacopini-Bohm
Teorema di Jacopini –Bohm (1966):
“Un qualsiasi algoritmo può essere espresso usando esclusivamente le strutture di sequenza, di selezione e di iterazione”.
1. Sequenza: una o più azioni elementari sono eseguite una di seguito all'altra nell'ordine in cui sono scritte.
2. Selezione: l’esecutore sceglie tra l’eseguire una o più operazioni in alternativa ad altre in funzione del verificarsi o meno di una certa condizione logica, selezionando il “percorso” da seguire in dipendenza da quanto eseguito in precedenza nell'avanzamento del procedimento di soluzione.
3. Ripetizione o iterazione: l’esecutore ripete più volte una o più operazioni in funzione del verificarsi o meno di una condizione logica che controlla il numero di volte per cui tali istruzioni devono essere ripetute (ciclo).
Tipologie di cicli negli algoritmi
• ciclo determinato: in questo caso si conosce precisamente il momento in cui la ripetizione avrà termine, ossia si conosce a priori il numero delle volte che il ciclo verrà ripetuto;
• ciclo indeterminato: il numero dei cicli ripetuti dipende dal verificarsi o meno della condizione che ne controlla l’arresto. La condizione può essere espressa in testa o in coda al ciclo: nel primo caso il ciclo potrebbe anche non essere mai eseguito (se la condizione è inizialmente falsa), mentre nel secondo caso il ciclo sarà eseguito almeno una volta.
Domande da interrogazione
- Quali sono le caratteristiche fondamentali di un algoritmo?
- Chi sono gli esecutori di un algoritmo e quali sono le loro tipologie?
- Qual è la differenza tra efficacia ed efficienza di un algoritmo?
- Cosa afferma il teorema di Jacopini-Bohm riguardo agli algoritmi?
- Quali sono le tipologie di cicli negli algoritmi?
Un algoritmo deve possedere finitezza, determinazione, terminazione, efficacia ed generalità, per garantire che le istruzioni siano chiare, eseguibili e applicabili a una classe di problemi simili.
Gli esecutori di un algoritmo possono essere intelligenti, che applicano conoscenze acquisite, o automatici, che eseguono meccanicamente i passi senza acquisire nuove conoscenze.
L'efficacia si riferisce alla capacità dell'algoritmo di risolvere un problema, mentre l'efficienza riguarda le risorse necessarie per eseguire l'algoritmo, come la memoria.
Il teorema di Jacopini-Bohm stabilisce che qualsiasi algoritmo può essere espresso utilizzando solo le strutture di sequenza, selezione e iterazione.
Esistono cicli determinati, in cui il numero di ripetizioni è noto a priori, e cicli indeterminati, in cui il numero di ripetizioni dipende da una condizione logica che ne controlla l'arresto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
