Alcune domande di analisi degli algoritmi
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.
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.
Risposte
"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?
[...]
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.
"xneo":
[...]
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.
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))?
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))?
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.
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...
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...
Sì, vero quello che mi hai scritto su mergesort ma prima me lo hai escluso esplicitamente nelle considerazioni assieme ad heapsort e quicksort 
.
.
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
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
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))$.
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.
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.
"xneo":
[...]
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.
"xneo":
[...]
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)$
"xneo":
[...]
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
.
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.
Si fin qui nulla da obiettare. Infatti sto dicendo che la presenza di un limite inferiore non ci fa trovare l' "ago" (l'algoritmo) ma ci permette solo di sapere che l'ago nel pagliaio c'è. Poi non è detto che ci sia un solo ago, ma almeno uno c'è.
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)$
Mea culpa. Sto ragionando solo per il caso peggiore.
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à.
Quindi ritornando all'enunciato iniziale, se la complessità intrinseca nel caso peggiore di un problema è Omega(f(n)) posso affermare che allora esiste almeno un algoritmo risolutore del problema che ha complessità O(f(n)) nel caso peggiore.
Quindi la non invenzione di un tale algoritmo (o di tali algoritmi) non implica la non esistenza.
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
Ti ringrazio per il tempo e la pazienza che mi stai dedicando.
"xneo":
[...]
Quindi ritornando all'enunciato iniziale, se la complessità intrinseca nel caso peggiore di un problema è Omega(f(n)) posso affermare che allora esiste almeno un algoritmo risolutore del problema che ha complessità O(f(n)) nel caso peggiore.
Quindi la non invenzione di un tale algoritmo (o di tali algoritmi) non implica la non esistenza.
[...]
Esattamente, ovviamente fatta salva l'ipotesi di complessità polinomiale che ti accennavo.
"xneo":
[...]
Ti ringrazio per il tempo e la pazienza che mi stai dedicando.
Di nulla, figurati, lo faccio volentieri
In un quesito d'esame c'era il seguente quesito.
Se un problema P ha complessità intrinseca Omega(2^n), dove n indica la dimensione dell'input, allora esiste almeno un algoritmo risolutore di P che ha complessità O(2^n).
Vero o falso?
visto che la complessità è esponenziale dovrei rispondere falso?
C'è anche quest'altro quesito..
La funzione f(n)=n+(2^n) è Omega(n)?
Credo che sia vero, infatti in base alla definizione n+(2^n) è Omega(n) se n+(2^n)>=c*n.
se c=1 e n0=0 la disuguaglianza è vera.
Se un problema P ha complessità intrinseca Omega(2^n), dove n indica la dimensione dell'input, allora esiste almeno un algoritmo risolutore di P che ha complessità O(2^n).
Vero o falso?
visto che la complessità è esponenziale dovrei rispondere falso?
C'è anche quest'altro quesito..
La funzione f(n)=n+(2^n) è Omega(n)?
Credo che sia vero, infatti in base alla definizione n+(2^n) è Omega(n) se n+(2^n)>=c*n.
se c=1 e n0=0 la disuguaglianza è vera.
Primo quesito.
L'affermazione è falsa proprio in virtù del fatto che la complessità intrinseca del problema è esponenziale. Se invece fosse polinomiale tale complessità poiché sappiamo che $P \subseteq NP$ (immagino tu sappia di che classi di problemi parliamo) allora l'affermazione sarebbe vera.
Secondo quesito.
E' falso anche questo. Per convincerti basta ricordarsi che:
\[
\text{per } n \to +\infty \quad \log_a n \leq n \leq x^n
\]
con $a, x > 1$.
L'affermazione è falsa proprio in virtù del fatto che la complessità intrinseca del problema è esponenziale. Se invece fosse polinomiale tale complessità poiché sappiamo che $P \subseteq NP$ (immagino tu sappia di che classi di problemi parliamo) allora l'affermazione sarebbe vera.
Secondo quesito.
E' falso anche questo. Per convincerti basta ricordarsi che:
\[
\text{per } n \to +\infty \quad \log_a n \leq n \leq x^n
\]
con $a, x > 1$.
per il primo quesito è tutto ok.
Per quanto riguarda il secondo quesito non capisco.
Per n->+inf n+2^n non è maggiore di n?
Per quanto riguarda il secondo quesito non capisco.
Per n->+inf n+2^n non è maggiore di n?
Attenzione, noi stiamo ragionando in termini di $O(...)$. Se al posto di quella somma $n + \log n$ avessi il prodotto $n \cdot \log n$ allora sarei d'accordo con te ma nel caso corrente no. Quando hai una somma all'infinito i termini che crescono meno rapidamente sono trascurabili (non è che si volatilizzano ma non ha più senso prenderli in considerazione perché quello che cresce più rapidamente "vince" ed è pertanto più rappresentativo).
E' come se scrivessi che $y = \log_2 x + x + x^2 + x^3 + x^4 + x^5$ è $O(x^5)$. In questa circostanza la serie di Taylor ed il confronto asintotico delle funzioni all'infinito dovrebbero venirti in aiuto per comprender meglio questo fatto.
E' come se scrivessi che $y = \log_2 x + x + x^2 + x^3 + x^4 + x^5$ è $O(x^5)$. In questa circostanza la serie di Taylor ed il confronto asintotico delle funzioni all'infinito dovrebbero venirti in aiuto per comprender meglio questo fatto.
scusami ma non continuo a capire.
Per n-> +oo, \(\displaystyle n+2^n \) si comporta come \(\displaystyle 2^n \). Giusto?
Ragionando in termini di \(\displaystyle \Omega \), \(\displaystyle 2^n \) è \(\displaystyle \Omega(n) \) ?
La funzione \(\displaystyle n \) non è dominata dalla funzione \(\displaystyle 2^n \)?
Per n-> +oo, \(\displaystyle n+2^n \) si comporta come \(\displaystyle 2^n \). Giusto?
Ragionando in termini di \(\displaystyle \Omega \), \(\displaystyle 2^n \) è \(\displaystyle \Omega(n) \) ?
La funzione \(\displaystyle n \) non è dominata dalla funzione \(\displaystyle 2^n \)?
"xneo":
scusami ma non continuo a capire.
Per n-> +oo, \(\displaystyle n+2^n \) si comporta come \(\displaystyle 2^n \). Giusto?
[...]
Esatto perché, come detto, $2^n$ vince.
"xneo":
[...]
Ragionando in termini di \(\displaystyle \Omega \), \(\displaystyle 2^n \) è \(\displaystyle \Omega(n) \) ?
[...]
Sì perché qui stai usando $\Omega$ al posto di $O$.
"xneo":
[...]
La funzione \(\displaystyle n \) non è dominata dalla funzione \(\displaystyle 2^n \)?
Appunto ma se vuoi dire ciò bisogna che scrivi che $n = O(2^n)$. Se trovi una qualche funzione che ha ordine di infinito superiore a $O(2^n)$, ad esempio $O(2^{n^2})$, potrai anche scrivere $n = O(2^n) = O(2^{n^2})$ o semplicemente $n = O(2^{n^2})$ e così via. Attento a non confondere le due notazioni $\Omega$ e $O$.
Se le funzioni hanno invece già lo stesso ordine di infinito allora posso anche usare $\Theta$. Ad esempio posso dire che $2n = \Theta(n)$.
Quindi \(\displaystyle n+2^n \) è \(\displaystyle \Omega(n)? \)
Mi sa che con tutte queste mie domande e confusioni ti sei confuso anche te, perchè mi hai risposto che è falso.
Perdonami ma sto solo cercando di capire...
Mi sa che con tutte queste mie domande e confusioni ti sei confuso anche te, perchè mi hai risposto che è falso.
Perdonami ma sto solo cercando di capire...
In effetti dopo tutti sti giri mi sono accorto che leggo $O$ anche quando c'è scritto $\Omega$ 
e pertanto il secondo quesito è vero. Sarà il caldo, sarà che sto scrivendo la tesi non lo so, sorry... Importante che il ragionamento ti sia chiaro al di là di tutto.
e pertanto il secondo quesito è vero. Sarà il caldo, sarà che sto scrivendo la tesi non lo so, sorry... Importante che il ragionamento ti sia chiaro al di là di tutto.
Non c'è problema. Ti ringrazio molto per tutte le risposte che hai dato.
Ce ne fosse di gente così disponibile.
Grazie mille ancora.
Ce ne fosse di gente così disponibile.
Grazie mille ancora.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo