Pages: [1]   Go Down
Print
Author Topic: dubbio su notazioni  (Read 2200 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« on: 04-02-2010, 11:26:38 »

abbiamo questo esercizio:
sia f(n)=Ω(g(n)), quale delle seguenti affermazioni potrebbe essere non vera?
a. f(n)=Ω(2*g(n))
b. f(n)=Ω(4*g(n))
c. g(n)=Ω(f(n))
d. g(n)=O(f(n))

dunque, la a è vera, la b pure vera
la c e la d?
per me la d è anche vera e quella non vera è la c, ma studiando con altri colleghi mi hanno detto che quella vera è la c e la non vera è la d
qualcuno saprebbe darmi la risposta esatta spiegandomela?
grazie a tutti
 
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 04-02-2010, 14:49:09 »

abbiamo questo esercizio:
sia f(n)=Ω(g(n)), quale delle seguenti affermazioni potrebbe essere non vera?
a. f(n)=Ω(2*g(n))
b. f(n)=Ω(4*g(n))
c. g(n)=Ω(f(n))
d. g(n)=O(f(n))

dunque, la a è vera, la b pure vera
la c e la d?
per me la d è anche vera e quella non vera è la c, ma studiando con altri colleghi mi hanno detto che quella vera è la c e la non vera è la d
qualcuno saprebbe darmi la risposta esatta spiegandomela?
grazie a tutti
 

la risp giusta e' la c...

eccoti una semplice dimostrazione per assurdo dell'asserzione
se f(n)=\Omega(g(n)) e f(n)\neq\Theta(g(n)) allora g(n)\neq\Omega(f(n))

per ipotesi abbiamo che
f(n)=\Omega(g(n)) => \exists c , n_0  :   0\leq cg(n) \leq f(n) per n\geq n_0 e
 f(n) \neq\Theta g(n)

supponiamo per assurdo che
g(n)=\Omega(f(n)) => \exists c' , n_1  :   0\leq c'f(n) \leq g(n)  per n\geq n_1

allora essendo che  f(n) =\Theta c'f(n)
0\leq cg(n) \leq c'f(n)\leq g(n)
per la positivita' di c' abbiamo che
0\leq \frac{c}{c'}g(n) \leq f(n)\leq \frac{1}{c'}g(n)
da cui segue che
 f(n) =\Theta g(n)
il che e' assurdo avendo supposto che
 f(n) \neq\Theta g(n)
l'assurdo e' nato dall'aver supposto
g(n)=\Omega(f(n))

« Last Edit: 05-02-2010, 16:12:23 by shiny » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #2 on: 04-02-2010, 15:51:58 »

è la c e credo che shiny è stato abbastanza convincente.  ok
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #3 on: 04-02-2010, 18:06:52 »

per c e c' vanno scelti bene altrimenti  la quarta ultima potrebbe non essere vera.
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 04-02-2010, 23:59:45 »

per c e c' vanno scelti bene altrimenti  la quarta ultima potrebbe non essere vera.
Non devi sceglierli , ti basta sapere che esistono .
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #5 on: 05-02-2010, 09:56:36 »

per c e c' vanno scelti bene altrimenti  la quarta ultima potrebbe non essere vera.
Non devi sceglierli , ti basta sapere che esistono .

non sono ammessi tutti i valori positivi di c e c'
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #6 on: 05-02-2010, 15:10:17 »

per c e c' vanno scelti bene altrimenti  la quarta ultima potrebbe non essere vera.
Non devi sceglierli , ti basta sapere che esistono .

non sono ammessi tutti i valori positivi di c e c'
Non neghi quanto io ho detto. Anzi, quello che dicevi prima andava corretto meglio: in particolare la 4° è sempre vera, mentre tu dicevi di no.
Ciao .
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #7 on: 05-02-2010, 15:46:58 »

scusa io intendo la 4 dal basso, la diseguaglianza sotto la scritta "per la positività di c' abbiamo".

Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 05-02-2010, 16:20:23 »

per c e c' vanno scelti bene altrimenti  la quarta ultima potrebbe non essere vera.

scusa ma il linguaggio matematico non e' mica ambiguo... quando scrivo

\exists c' , n_1  :   0\leq c'f(n) \leq g(n)  per n\geq n_1

voglio proprio dire che a partire da un certo n_1 esiste una c' costante positiva tale che 0\leq c'f(n) \leq g(n)

non dico mica che per ogni c' positiva e per qualsiasi valore di n succede che 0\leq c'f(n) \leq g(n)

P.s. con quanto hai passato analisi?
Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #9 on: 05-02-2010, 16:47:45 »

ho detto semplicemente che nel momento in cui dividi per c'  0<= c/c' g(n)<= f(n)<= 1/c' g(n)  se c non vale esattamente 1 quella diseguaglianza potrebbe non essere vera.
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #10 on: 05-02-2010, 17:07:01 »

ho detto semplicemente che nel momento in cui dividi per c'  0<= c/c' g(n)<= f(n)<= 1/c' g(n)  se c non vale esattamente 1 quella diseguaglianza potrebbe non essere vera.

in R (insieme dei numeri reali) l'operazione \frac{x}{y} e' sempre possibile per y\neq 0 ed inoltre se  x,y \in R e  x,y > 0 allora se x > y vale che \frac{x}{y} > 1 e 0 < \frac{y}{x} < 1

Se non riesci a capire che quello che hai scritto e' veramente fuori dal mondo ti consiglio di prendere un qualsiasi libro di analisi e andare a vedere le disuguaglianze in R...
« Last Edit: 05-02-2010, 17:08:50 by shiny » Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #11 on: 05-02-2010, 17:27:33 »

non ti degno di risposta
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #12 on: 05-02-2010, 20:22:08 »

e poi tutto è nato dal non aver Huh???visto?Huh?   f(n) != Theta(g(n)) da dispositibo mobile
« Last Edit: 05-02-2010, 20:46:47 by Pandemia000 » Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Pages: [1]   Go Up
Print
Jump to: