Algoritmi e strutture di controllo

Informatica (Fisica - Informatica - Statistica)

• Corso di Laurea Magistrale a Ciclo Unico in Medicina Veterinaria.
• Anno Accademico 2024/2025.
• Docente: Dr. Luigi Vesce ([email protected]).
• Coordinatore del Corso Integrato: Prof. Nicola Toschi.

Formalizzazione dell'Informazione - Algoritmi

• La formalizzazione dell'informazione e la descrizione degli algoritmi sono trattati in questo corso.
• Il Dr. Luigi Vesce è il docente.

Problema

• Descrizione del problema.
• Individuazione della soluzione.
  • Identificazione dei dati necessari.
  • Scelta delle metodologie/tecniche.
  • Definizione dell'ordine delle operazioni.

Fase dell'Analisi

• Dalla specifica del problema al linguaggio macchina.
• Comprensione del problema.
• Modellazione del problema.
• Ricerca della soluzione.

Problema - Comprensione

• Eliminare ambiguità nella formulazione.
• Focalizzare gli obiettivi.
  • Identificazione degli obiettivi reali del problema.
  • Definizione di regole.
  • Definizione di dati espliciti e impliciti.
• Eliminare dettagli superflui e poco chiari.

Problema - Soluzione

• La soluzione è espressa come sequenza di operazioni.
• L'esecuzione della sequenza porta alla soluzione del problema, ovvero all'algoritmo risolutivo.
• Dati iniziali sono trasformati in dati finali (soluzione) tramite algoritmo.

Algoritmo - Definizione

• Sequenza di azioni elementari e non ambigue.
• Trasformazione dei dati iniziali in un risultato finale.
• Validità per un insieme ben definito di dati iniziali.
• Eseguibilità tramite un esecutore opportuno.

Algoritmo - Proprietà

• Finitezza: numero finito di passi elementari.
• Non ambiguità (determinismo): lo stesso input genera lo stesso output.
• Realizzabilità: i passaggi sono eseguibili con le risorse disponibili.
• Efficienza: minimo numero di operazioni possibili.

Esempio - Cottura Uovo al Burro

• Problema: come cucinare un uovo al burro?
• Soluzione:
  • Sciogliere burro nel tegamino.
  • Quando il burro assume un colore dorato rompere il guscio dell'uovo.
  • Far scivolare delicatamente albume e tuorlo nel tegamino.
  • Salare.
  • Quando l'albume è ben rappreso spegnere il fuoco.

Procedura Non Chiara

• Tutte le operazioni devono essere eseguibili dall'esecutore.
• Scomposizione di problemi complessi in problemi più semplici.
  • Esempio: rompere il guscio come sottoproblema.

Esempio - Scomposizione Problema

• Descrizione di un esempio di scomporre un problema (geometrico).
• Soluzione dei sottoproblemi per ricomporre la soluzione finale.

Esempio - Gestione Biblioteca

• Libri disposti su scaffali fissi.
• Posizione di ogni libro identificata da scaffale e posizione sullo scaffale.
• Schedario di catalogazione per autore e titolo.
  • Cognome e nome autore.
  • Titolo libro.
  • Data di pubblicazione.
  • Numero scaffale.
  • Posizione libro sullo scaffale.

Scheda della Biblioteca (Esempio)

• Autori: Sciuto, Donatella; Buonanno, Giacomo; Fornaciari, William; Mari, Luca.
• Titolo: Introduzione ai Sistemi Informatici, II Edizione, 2002.
• Scaffale: 22
• Posizione: 11

Formulazione Algoritmo

• Decidere il libro da richiedere.
• Prelevare il libro richiesto.
• Dettagliare i passi incomprensibili tramite algoritmi successivi.
  • Procedimento Top-Down/Raffinamenti Successivi

Algoritmo per il Prelievo Libro

• Decidere il libro da richiedere.
• Cercare la scheda del libro richiesto.
• Segnarsi numero scaffale e posizione.
• Cercare lo scaffale indicato.
• Accogliere alla posizione indicata e prelevare il libro.
• Scrivere i dati sulla scheda di prestito.

Sotto-Algoritmo

• Prendere la prima scheda.
• Esaminare titolo e autore per verificare coincidenza.
• Caso positivo, termina ricerca.
• Altrimenti, passare alla scheda successiva, ripetere.
• Se schede esaurite, libro non esiste.

Sotto-Algoritmo Migliore

• Esaminare la scheda centrale dello schedario.
• Corrispondenza con il libro cercato? Termina ricerca.
• Altrimenti, ripeti i passi nell'altra metà dello schedario.
  • Procedere nella metà superiore o inferiore in base al libro cercando in base alla posizione della scheda.
• Terminazione quando non esiste il libro o la parte di schedario da consultare è vuota.

Ulteriore Miglioramento

• Termine ricerca se libro trovato nella scheda centrale.
• Terminazione ricerca quando lo schedario è vuoto.

Il crivello di Eratostene

• Eratostene e la sua importanza come intellettuale.
• Metodo per individuare i numeri primi compresi tra 2 ed n.

Esempio (Il setaccio di Eratostene)

• Sequenza iniziale di numeri compresi tra 2 e 20.
• Eliminazione multipli di numeri primi scoperti.
• Identificazione numeri primi rimanenti.

Miglioramento

• Settacciare la lista fino a n/2.
• Analisi del problema e formalizzazione algoritmo per migliorare efficienza e condizione di terminazione dell'algoritmo.

Osservazioni

• Analisi accurata del problema e individuazione di invarianti importanti.
• Algoritmo parametrico adattabile a diversi valori.
• Elaborazione dei dati via via.
• Caratteristiche comuni nelle analisi e risoluzioni algoritmiche dei problemi.

Esempio - Algoritmo del Risveglio

• Passaggi nell'algoritmo del risveglio.
• Sequenza di operazioni.
• Importanza dell'ordine delle istruzioni.

Variante if

• Passaggi con l'inclusione della condizione "Se piove".
• Aggiunta di istruzioni condizionali nell'algoritmo.

Variante if 2

• Passaggi con l'inclusione della condizione "Se piove".
• Sostituzione con la scelta per prendere la macchina se piove o utilizzare l'autobus, altrimenti.

Variante while

• Passaggi nell'algoritmo mentre piove.
• Condizione ciclica "Mentre piove" nel risveglio.

Strutture di controllo - Sequenza

• Esecuzione delle istruzioni nell'ordine stabilito.
• Esempio di algoritmo basato su operazioni sequenziali (solleva ricevitore, compone numero).

Strutture di controllo - Iterazione

• Esecuzione ripetuta delle istruzioni finché non è soddisfatta una determinata condizione.
• Esempio di algoritmo ciclico (Ripeti - compone cifre del numero - fino al completamento del numero).

Strutture di controllo - Condizione

• Valutazione della condizione per determinare l'esecuzione di istruzioni in alternativa.
• Esempio di algoritmo condizionale (SE il numero è libero, ALLORA attendi la risposta, conduci la conversazione deponi il ricevitore; ALTRIMENTI deponi il ricevitore).

Algoritmo (di nuovo)

• Sequenza finita di istruzioni comprensibili per un esecutore.
• Descrizione di come realizzare un compito.
• Esempi (montaggio elettrodomestico, terminale Bancomat, calcolo massimo comun divisore).

Esecutori e linguaggi

• Elementi che definiscono un esecutore: azioni possibili, specificazione o linguaggio delle istruzioni, semantica.
• Linguaggio macchina dei calcolatori.

Soluzione per l'esecutore

• Problemi semplici sono svolti direttamente dall'esecutore.
• Problemi complessi devono essere scomposti in sottoproblemi e operazioni elementari.
• Soluzione effettiva: comprensibile e attuabile dall'esecutore.

Azione elementare: proprietà

• Finitezza: azione deve terminare in tempo finito.
• Osservabilità: l'azione deve avere un effetto osservabile.
• Riproducibilità: stessa azione con lo stesso stato iniziale produce sempre lo stesso risultato.

Realizzazione di una soluzione automatica

• Definizione dei requisiti (cosa).
• Progettazione (come)
• Soluzione: algoritmo

Algoritmi - Proprietà

• Correttezza: algoritmo porta alla soluzione del compito senza errori.
• Efficienza: algoritmo utilizza la minima risorsa possibile per risolvere il problema.

Algoritmi - Proprietà (Continuazione)

• Ingresso specificato: algoritmi corretti per input diversi.
• Uscita specificata: ogni algoritmo deve dare un risultato preciso.
• Determinatezza/univocità: lo stesso input produce lo stesso output.
• Efficacia: operazioni eseguibili meccanicamente.
• Terminazione: algoritmo termina in un numero finito di passi.

Verifica algoritmo (Esempio)

• Ricetta del Biancomangiare.
• Verifica delle proprietà dell'algoritmo della ricetta.

Concetti - Riepilogo

• Algoritmo: descrizione di come risolvere un problema.
• Programma: algoritmo scritto per un calcolatore.
• Linguaggio macchina: linguaggio compreso da calcolatori con istruzioni semplici.
• Compito dell'informatico: formulare algoritmi e codificarli in programmi per calcolatori.

Questo quiz esplora i concetti fondamentali legati agli algoritmi, incluse le loro caratteristiche principali e le strutture di controllo essenziali. Testa la tua comprensione di cosa rende un algoritmo efficace e approfondisci il concetto di sotto-algoritmo. Scopri anche l'importanza del crivello di Eratostene nella teoria degli algoritmi.