Correttezza di algoritmi e programmi

di
Booster
il
6 risposte
B
Booster
Utente Attivo
Iscritto da
lug, 2017
Messaggi:
337

Correttezza di algoritmi e programmi

Sto per terminare lo studio degli algoritmi per quanto riguarda il primo esame di informatica su questi. Di ciò che ho studiato posso dire tre cose:

1) Ho implementato ogni singolo algoritmo, qualche volta sbirciando lo pseudocodice, qualche volta arrivandoci da solo a capire come farlo.

2) Imparato a calcolare la complessità computazionale degli algoritmi che ho studiato.

3) Avendoli implementati in c++, ho preso dimestichezza con il paradigma OOP e migliorato le mie conoscenze e capacità riguardo ad un linguaggio considerato tremendo, opinione che sinceramente non condivido

Arriviamo al dunque del thread. A monte di tutto ciò ho trascurato un aspetto dell'analisi degli algoritmi che non ho mai capito a fondo: la correttezza di questi. Ho cercato diversi materiali su internet, ma almeno in italiano ho trovato davvero poco. Non ho cercato libri a riguardo e sinceramente non credo ce ne siano. Da ciò che ho visto, in genere nei corsi di programmazione, si fanno vedere pochi casi in cui si analizza la correttezza e si fa in casi semplici. Dico di non var capito fino in fondo per il fatto che le dimostraioni che ho letto, non erano troppo formali e quindi mi è sempre sembrato che fosse una via di mezzo tra il giustificare il procedimento ( per esempio le invarianti di ciclo) e la pseudo descrizione matematica. Premetto che non sono mai riuscito a fare una dimostrazione formale della correttezza di un algoritmo autonomamente, al contrario in ambito matematico con l'analisi, algebra lineare, geometria sono riuscito qualche volta ad arrivarci da solo, trovando sempre e comunque abbastanza ragionevoli e intuitive le dimostrazioni. Quindi al di là di questa mia mancata capacità, mi sorgono un po di domande: quanto ha senso fare questo e fino a che punto è fattibile?

1) Il senso, è riferito al fatto che quando dovrò utilizzare un algoritmo che ho già studiato per inserirlo in un programma, avrò a dispozione diverse librerie che me lo predispongano per ciò che mi serve.
2) per fattibile intendo due cose: lavorando in un team, sviluppando programmi da centinaia di migliaia di righe di codice, quanto è fattibile per quanto riguarda i tempi necessari e la complessità in se di formalizzare ogni operazione? A qui si ricollega la domanda di prima, che senso avrebbe?

I sono di quelli che, anche se non trovano il senso del loro problema, non si da pace finchè non lo risolve.

Aspetto qualche delucidazione in merito da parte vostra. Dalla vostra esperienza da programmatori, che conclusioni traete e che consigli potete dare?

6 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5887

    Re: Correttezza di algoritmi e programmi

    3) Avendoli implementati in c++, ho preso dimestichezza con il paradigma OOP e migliorato le mie conoscenze e capacità riguardo ad un linguaggio considerato tremendo, opinione che sinceramente non condivido
    Quindi non ti viene il mal di testa quando un template non compila, o quando implementi l'ereditarieta' multipla, oppure sai perfettamente quando usare "auto_ptr", "unique_ptr", "shared_ptr", quando usare un puntatore, o un reference, o quando devi decidere se usare dynamic_cast, static_cast, const_cast, reinterpret_cast o cast alla C?

    O non hai trovato difficolta quando devi allocare/deallocare struttre dati complesse in cui non c'e' un'evidente struttura gerarchica, e quindi non puoi usare gli smart pointer, ma devi gestire la memoria ""a mano""?

    Ci genuflettiamo al tuo cospetto

    Per quanto riguarda la parte ""formale"" degli algorimi, questa si usa SOLO quando inventi un NUOVO algoritmo per risolvere una certa categoria di problemi ""astratti"" e per il quale devi DIMOSTRARE che il tuo algoritmo ha proprieta' MIGLIORI degli algoritmi gia' esistenti.

    Ad esempio, ti inventi un NUOVO algortmo per ""il problema del commesso viaggiatore"": poic'e esistono gia' n-mila algoritmi, devi DIMOSTRARE che il tuo e' migliore o si comporta MEGLIO di altri almeno in certe situazioni.

    Queste attivita' le fai in ambito ""ricerca"", NON in ambito ""commerciale"" in cui non frega niente di trovare l'algoritmo migliore, ma basta uno che funzioni in modo non eccessivamente ""schifido"".
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Correttezza di algoritmi e programmi

    Chiaramente non ho incontrato tutti i problemi da te esposti, poic mi sono avvalso di alcune cose già pronte. Avevo solo implementato le parti principali, poi non ho detto che sono diventato un esperto di programmazione a basso livello, ho solo detto di essere migliorato rispetto a ciò che sapevo fare qualche mese/ annetto fa, nulla di stratosferico, ho ancora tanto tanto da imparare.
    In merito al mio problema, cosa mi diresti?
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Correttezza di algoritmi e programmi

    Forse non sono stato chiarissimo. Io non parlavo di analisi delle prestazioni, ma della correttezza. Dato un algoritmo X, il problema non è dimostrare che il tempo di esecuzione può essere O(n) piuttosto che O(n^3), ma stabilire che esso restituisca l'output atteso a prescindere dall'input.
  • Weierstrass
    Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi:
    2245

    Re: Correttezza di algoritmi e programmi

    1) cerca di ridurre il tuo codice a un ragionamento matematico, per quanto possibile. Non devi dimostrare tutto al 100%, se ci pensi bene non lo fai nemmeno negli esami di analisi e a un certo punto lasci spazio all'intuito. Le dimostrazioni formali complete sono lunghissime, chi le fa fa solo quello di lavoro

    2) fai molti test, se possibile testa tutto il dominio delle funzioni, altrimenti testa le porzioni significative

    3) continua a confrontarti con quello che fanno gli altri

    Infine, è brutto da dire, ma devi trovare il giusto compromesso tra pignoleria e produttività. Il piccolo errore nel caso marginale viene tollerato al lavoro nel 99% dei casi nelle aziende serie, poi viene corretto a posteriori. Nelle aziende meno serie vengono tollerate delle cose che è meglio non raccontare, quindi non essere scrupoloso più del necessario
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5887

    Re: Correttezza di algoritmi e programmi

    Come sai, la terminazione della macchina di turing, che poi e' in relazione 1:1 con il problema del capire se un algoritmo ritorna quello che dovrebbe ritornare, e' un problema "indecidibile".

    Quindi, in PRATICA, la ""correttezza" di un algoritmo la si implementa mediante una serie di ASSERZIONI sui valori di INGRESSO e sul risultato in USCITA. Un secondo metodo e' quello di fare un uso OCCULATO delle eccezzioni, della loro gestione e della relativa SEGNALAZIONE su un file di log.

    Ad esempio, REGOLA FONDAMENTALE: quando intercetti un'eccezione

    1) la PROPAGHI, cosi' come e' oppure cambiandone il tipo OPPURE
    2) la CONSUMI, MA ... LA SCRIVI SUL LOG

    MAI E POI MAI intercetti un'eccezione e la fai scomparire, cioe' non la registri da nessuna parte.

    Questo non ti assicura la correttezza del codice, ovviamente, ma ti aiuta nel caso in cui qualcosa non funzioni.

    Inoltre devi anche tenere presente che il malfunzionamento nel TUO codice potrebbe essere il risultato del malfunzionamento di UN'ALTRA parte del codice che non hai scritto tu, ma un tuo collega o una libreria di terze parti, e a sua volta potrebbe essere legato a qualche configurazione sbagliata, problemi hardware ed n-milioni di altre cose.

    Non sarebbe la prima volta che un programmatore inesperto si e' creato una libreria personale per i log che ha usato nell'applicazione, SENZA tenere conto del fatto che il log aumenta di dimensione in modo costante.
    MA, mentre durante lo sviluppo l'applicazione viene fermata e fatta ripartire n-mila volte al giorno, in produzione l'applicazione puo' rimanere in funzione per giorni/mesi/anni. Quindi, se il log non ha una dimensione massima, puo' riempire completamente lo spazio disco. E ti ritrovi con 10TB di storage completamente pieni e non capisci perche'!

    D'altra parte, NON HA SENSO gestire casi altamente improbabili, perche' rischi di incasinare il codice inutilmente per gestire una situazione che, in condizioni normali, non dovrebbe mai verificarsi.

    I classici esempi sono spazio disco e memoria. E' impossibile che un'applicazione ""normale"" consumi TUTTA la memoria del computer.
    Le applicazioni che lo fanno sono di due tipi:

    1) e' PREVISTO in fase di progettazione dell'applicazione, quindi si prendono in considerazione una serie di strategie e si conoscono anche quali sono le parti del codice che possono essere coinvolte. Ad esempio, un'applicazione di elaborazione di immagini puo' avere problemi di memoria SOLO nell'allocazione dello spazio per mantenere l'immagine in memoria, E BASTA.
    2) e' IMPREVISTO, nel senso che l'applicazione ha dei memory leak. In questo caso BISOGNA RISOLVERE I memory leak, NON applicare delle strategie per resistergli.

    Quindi, l'applicazione puo' essere realizzata SUPPONENDO spazio disco infinito, memoria infinita, potenza di calcolo infinita, transfer rate infinito, ecc. SE serve tenere conso dei limiti, questo va fatto SOLO dove serve e non in modo generalizzato.
  • B
    Booster
    Utente Attivo
    Iscritto da
    lug, 2017
    Messaggi:
    337

    Re: Correttezza di algoritmi e programmi

    @migliorabile, ti ringrazio per per dei consigli, come sempre con risposte esaustive. Ciò che mi hai detto è applicabile all'ambito lavorativo, quando si sviluppano grosse applicazioni e quindi ci si serve di questi strumenti come la gestione delle eccezzioni e i garbage collector. Tuttavia, il mio problema era per ora limitato a programmi piccoli quelli che si sviluppano come esercizi che servono per capire bene gli algoritmi e un particolare linguaggio. Per questo penso che la risposta di Weierstrass sia più adeguata, in quanto il mio problema risiedeva nel non riuscire nelle dimostrazioni formali della decidibilià degli algoritmi, problema che come hai descritto tu viene affrontato in maniera diversa quando si ha a che fare cn software grossi, in cui bisogna fare più test che dimostrazioni, che immagino siano fattibili fino ad un certo punto, a quello che mi attengo io.
Devi accedere o registrarti per scrivere nel forum
6 risposte