Ci occupiamo di problemi. Che cosa sarebbe un problema? Che definizione possiamo dare? Possiamo definirla come questione di carattere generale, come problema computazionale $\pi : I \rightarrow S$, di cui I come possibili assegnamenti e S insieme di possibili soluzioni. Quindi fondamentalmente una funzione.
Posso andare a classificare i problemi in base al tipo di risoluzione che ci restituiscono:
Anche la definizione di algoritmo potrebbe non essere così scontato da definire. Lo possiamo definire generalmente come procedura generale per risolvere un problema definito definito tramite una sequenza di passi finita, non ambigua, effettivamente realizzabile che una volta eseguita termina in nu tempo finito.
Al termine voglio arrivare ad avere un risultato, che sia qualcosa di utile o anche un errore. Non possiamo avere algoritmi che non terminano per definizione e perché, sempre da definizione, un algoritmo che non terminano non riuscirei nemmeno a farlo runnare.
A noi ci interessano gli algoritmi corretti e non è facile dimostrare che sia così. Devo fare sempre dimostrazioni per fare vedere che un mio algoritmo funzioni o che non riesca mai a terminare. Gli algoritmi è anche importante che siano efficienti. Voglio dei risultati che si possano ottenere in termini di risorse reali: tempo e spazio e possibilmente non infinite. Lo spazio lo posso andare a riutilizzare, mentre il tempo no.
Solitamente si usa il modello RAM, cioè uni processore che esegue tutte le istruzioni uno dopo l’altra, con operazioni logiche-aritmetiche e lettura-scrittura dalla memoria, con un program counter. Assumo di avere memoria infinita. Studio dopo la memoria praticamente. Stiamo su un trattamento semplice e sufficientemente aderente alla realtà.
Come posso andare a misurare l’efficienza?
Devo andare a misurare tempo e spazio. Tempo come numero di operazioni elementari necessari per andare a risolvere il problema nel caso in input sia data l’istanza peggiore, in funzione della dimensione dell’input. Non vado a contare i secondi perché dipendono dalla macchina su cui lo fai girare. Lavoriamo quindi sui worst case. Facciamo una stima per eccesso sull’esecuzione del nostro algoritmo.
Per quel che riguardo lo spazio vado a definire le celle di memoria in funzione della dimensione dell’output.
Come posso andare a definire la dimensione dell’input?
Possiamo definirlo come numero di bit per andare a definire l’input. Ma possiamo definirlo anche come numero di oggetti che ha un determinato input, quindi diamo una definizione più generale.
Noi ci concentriamo sul numero di elementi. Se andiamo a lavorare con numeri singoli e voglio capire chi è primo, allora dobbiamo andare a lavorare con i bit. Devo capire dove sta la variabilità di dimensione del nostro input perché se ho pochissimi elementi, o addirittura uno, allora sicuramente dovrò cercare la variabilità al suo interno e lavorare probabilmente con i bit. Questa è una questione di granularità in base al tipo di problema che andiamo ad affrontare.
Voglio andare a definire in termini di tempo e spazio soprattutto nel caso peggiore. Per ogni algoritmi cerco di andare a vedere il caso peggiore e faccio una analisi dell’algoritmo.
L’algoritmo serve per andare ad approcciare e risolvere un problema, ma anche il problema stesso lo posso andare a studiare in termini di costi. Posso cercare di capire il costo massimo e minimo per andare a risolvere un determinato problema. Posso andare a cercare due upper bound: uno per il costo per risolvere e un lower bound. Dato nu problema voglio poter dire che esiste un algoritmo che al massimo arrivo a tot e al minimo posso andare a tot.
Da un lato un algoritmo e capire quando può andare peggio e dell’altro un problema che può avere un costo minimo e massimo di computazione per essere risolto. Ho quindi una finestra in cui vado a prendere algoritmi risolutivi che mi interessa.
Upper bound del problema lo posso trovare dando un algoritmo che mi riesce a risolvere il problema. Ogni algoritmo che trovo per risolvere un problema mi dice praticamente un upper bound per andare a risolvere il problema. Per fare vedere un lower bound è più difficile, perché devo dimostrare che meno di tot non ci si possa mettere. In questo caso devo andare a fare un discorso generale sul problema, senza fare alcuna ipotesi sull’algoritmo specifico, su un caso peggiore.