Alcune domande di analisi degli algoritmi

[xneo]

ciao a tutti,
Il quesito è il seguente:

se un problema ha complessità intrinseca Omega(f(n)) è giusto affermare che allora esiste almeno un algoritmo risolutore che risolve il problema in O(f(n))? Cioè in pratica dato un problema esiste almeno un algoritmo risolutore ottimale?.

Io mi sentirei di rispondere in modo affermativo, poichè se non esistesse (per non esistenza non intendo non ancora inventato) almeno un algoritmo che risolve il problema in Teta(f(n)) (è questo implica O(f(n)) ) la complessità intrinseca allora sarebbe Omega(g(n)) con g(n)=Omega(f(n)).
E' giusto il ragionamento?

Altro dubbio:
sia f(n)=n^2 g(n)=nlog(n^n), f(n)=O(g(n))?
Secondo me si, in quanto g(n) si può scrivere come (n^2)*logn e quindi g(n) ha il fattore logaritmico che la rende maggiore a f(n); Però non so se è giusto.

Spero possiate aiutarmi, grazie.

[onlyReferee]

ciao a tutti,
Il quesito è il seguente:

se un problema ha complessità intrinseca Omega(f(n)) è giusto affermare che allora esiste almeno un algoritmo risolutore che risolve il problema in O(f(n))? Cioè in pratica dato un problema esiste almeno un algoritmo risolutore ottimale?.
Io mi sentirei di rispondere in modo affermativo, poichè se non esistesse (per non esistenza non intendo non ancora inventato) almeno un algoritmo che risolve il problema in Teta(f(n)) (è questo implica O(f(n)) ) la complessità intrinseca allora sarebbe Omega(g(n)) con g(n)=Omega(f(n)).
E' giusto il ragionamento?
[...]

Ciao xneo
L'esistenza di un algoritmo che risolva tale problema in modo ottimale non è sempre garantita poiché in teoria la complessità dell'algoritmo fornito potrebbe essere (faccio un esempio) $O(g(n))$ se arriva un determinato input allo stesso che rappresenta il caso peggiore che possa capitare o $O(f(n))$ nel caso in cui invece l'input ricevuto costituisca il caso migliore. Esempio di input nel caso peggiore potrebbe essere l'array già ordinato in un algoritmo di ordinamento come l'insertion sort: lo stesso non si accorge del fatto che il vettore in input è già ordinato ed esegue lo stesso degli inutili spostamenti dei valori.
Sostanzialmente ciò che sto affermando è che la complessità dell'algoritmo di solito si valuta sempre nel caso peggiore ($O(f(n))$) ma la stessa si può ridurre nei casi medio e migliore.

[...]

Altro dubbio:
sia f(n)=n^2 g(n)=nlog(n^n), f(n)=O(g(n))?
Secondo me si, in quanto g(n) si può scrivere come (n^2)*logn e quindi g(n) ha il fattore logaritmico che la rende maggiore a f(n); Però non so se è giusto.

Spero possiate aiutarmi, grazie.

Sì, giusto, per il semplice fatto che $\log(n)$ dipende da $n$ e pertanto non si può considerare come una costante ininfluente sulla complessità dell'algoritmo. Inoltre il termine $\log(n)$ non è aggiunto ma va a moltiplicare $n^2$. Sappiamo infatti che se invece i termini sono sommati tra loro "vince" la funzione che cresce più rapidamente all'aumentare della dimensione dell'input $n$. Questo significa che se avessi ad esempio $h(n) = n^2 + \log(n)$ allora si avrebbe $h(n) = O(n^2)$.
Spero di esserti stato d'aiuto nel risolvere i tuoi dubbi, in caso chiedi pure ancora.

[xneo]

Per quanto riguarda la prima domanda, facendo riferimento al problema dell'ordinamento basato su confronti, si sa che la complessità intrinseca è Omega(n*log(n) (intendo nel caso peggiore).
Supponiamo che algoritmi come heap sort, merge sort, quicksort non sono siano ancora stati inventati, si sarebbe potuto affermare che esisteva almeno un algoritmo che risolveva il problema in O(n*log(n))?

[onlyReferee]

Ti posso rispondere dicendo: no poiché non vorrei sbagliarmi ma escludendo gli algoritmi più performanti che tu hai citato relativamente al problema dell'ordinamento per confronti si ha che gli altri possono avere una complessità pari a $O(n \log (n))$ solo in determinati casi particolari quali quello medio o migliore ma non nella maniera più assoluta in quello peggiore.

[xneo]

Però merge sort ha nel caso peggiore complessità temporale O(nlog(n)).

Se io penso alla complessità intrinseca come un'asticella sotto la quale non posso scendere, se non ci fosse nessun algoritmo che sia in grado di "toccare" l'asticella, allora significa che l'asticella può essere messa più in alto.
Io ho quest'immagine nella testa. Magari è un modo sbagliato di visualizzare il problema...

[onlyReferee]

Sì, vero quello che mi hai scritto su mergesort ma prima me lo hai escluso esplicitamente nelle considerazioni assieme ad heapsort e quicksort .

[xneo]

Scusa se non mi sono fatto più sentire a causa di impegni stressantissimi.

Comunque riprendendo il discorso,
mi sa che mi sono espresso male, provo a riformulare il ragionamento.

Supponiamo che P sia un problema e ancor prima che si cerchi di scrivere un algoritmo si dimostra matematicamente che la complessità intrinseca è Omega(f(n)).

A questo punto dei ricercatori cominciano a scrivere degli algoritmi risolutori di P che hanno complessità O(g(n)).
La relazione che c'è tra f(n) e g(n) è che f(n)=O(g(n)).

Comunque l'obbiettivo dei ricercatori è di trovare un algoritmo che risolva P in Teta(f(n)).
Questo obbiettivo è raggiungibile (magari non in questa generazione, ma anche in un futuro remoto) aldilà della difficoltà del problema e dell'abilità dei ricercatori?

Cioè quest'algoritmo ottimale può essere paragonato ad un "ago in un pagliaio"?
Cioè non importa quanto tempo si impieghi per trovarlo (magari mai) però comunque l'ago si trova nel pagliaio

[onlyReferee]

In molte tipologie di problemi si può provare mediante la teoria della calcolabilità qual è il limite inferiore (o superiore, a seconda dei casi) di complessità che può avere un algoritmo per risolvere un problema ed in tali casi tutti i tentativi futuri sarebbero soltanto "aria fritta" (o semplicemente tempo perso). In altri casi invece non si riescono ad effettuare tali dimostrazioni e pertanto nulla vieta che un domani si riesca a trovare quell'algoritmo che tu chiami "ago in un pagliaio". Nel caso ad esempio degli algoritmi di ordinamento per confronti (o scambi che dir si voglia) tale limite inferiore è stato dimostrato a livello computazionale e pertanto per quanto i ricercatori si possano sforzare non riusciranno a determinare un tale algoritmo avente complessità inferiore a $n \log(n)$. Ciò vuol dire che qualsiasi algoritmo per risolvere tale problema sarà $\Omega(n \log(n))$. Nel caso del mergesort abbiamo nella fattispecie $\Theta(n \log(n))$.

[xneo]

si si, la tua risposta è molto chiara.
Se non si riesce a provare mediante dimostrazioni un limite inferiore, allora potrei sforzarmi (magari a vuoto) a trovare algoritmi sempre più efficienti.

Però dimostrare la presenza di un limite inferiore sotto il quale non si può scendere, essenzialmente significa aver dimostrato che l'"ago" è effettivamente nel pagliaio.

Nel caso dell'ordimento se il merge sort non fosse ancora stato inventato, dal punto di vista matematico si sarebbe potuto affermare che un algoritmo Teta(n log n) esiste?

Ad esempio sotto opportune ipotesi il Teorema di Weierstrass garantisce l'esistenza di massimo e minimo di una funzione.
Poi il fatto che magari non si sappia calcolarli (magari la funzione è difficile è non ci va di calcolare e studiare la derivata) non ne esclude l'esistenza.

[onlyReferee]

[...]
Però dimostrare la presenza di un limite inferiore sotto il quale non si può scendere, essenzialmente significa aver dimostrato che l'"ago" è effettivamente nel pagliaio.
[...]

In realtà la dimostrazione di un limite inferiore è una sorta di "barriera" che viene data. Dire che abbiamo trovato l'ago (l'algoritmo) nel pagliaio significa affermare che abbiamo determinato uno dei possibili algoritmi che stanno su tale barriera. In realtà il paragone con l'ago nel pagliaio regge fino ad un certo punto poiché potremmo scriverne anche molti di algoritmi che hanno una complessità pari a quella intrinseca del problema.

[...]
Nel caso dell'ordimento se il merge sort non fosse ancora stato inventato, dal punto di vista matematico si sarebbe potuto affermare che un algoritmo Teta(n log n) esiste?
[...]

In teoria sì perché la complessità intrinseca del problema è polinomiale e non esponenziale (qui però mi addentro in dettagli troppo avanzati relativamente a questa questione di cui stiamo ragionando). Credo comunque che prima che si inventasse il mergesort fossero già noti altri algoritmi di ordinamento per confronti (buon parte dei quali li conosciamo) che nel caso migliore o medio (ma non sicuramente nel caso peggiore) avessero una complessità pari ad $O(n \log n)$

[...]
Ad esempio sotto opportune ipotesi il Teorema di Weierstrass garantisce l'esistenza di massimo e minimo di una funzione.
Poi il fatto che magari non si sappia calcolarli (magari la funzione è difficile è non ci va di calcolare e studiare la derivata) non ne esclude l'esistenza.

Sì, diciamo (facendo un paragone) che l'ideale è sempre cercare di produrre enunciati quanto più generici possibile limitando pertanto al minimo indispensabile le ipotesi. Lo stesso che tu affermi citando il teorema di Weierstrass avviene quando si riesce a determinare la complessità intrinseca del problema: la calcolabilità ci permette (in vari casi ma non sempre) di calcolare questa ma non sappiamo quanto complicato può essere determinare un algoritmo avente tale complessità.
PS: tranquillo anche se usi espressioni come "ago in un pagliaio" quando fai delle considerazioni e degli esempi. Molto spesso (almeno secondo la mia esperienza) è proprio con gli esempi fatti diciamo "a basso livello" che si riescono a comprendere meglio i concetti .