Pages: [1]   Go Down
Print
Author Topic: Esercizi notazioni asintotiche  (Read 3634 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« on: 23-11-2011, 17:19:20 »

Ho cercato in tutto il forum, ho trovato le soluzioni di alcuni esercizi ma non riesco proprio a capire che tipo di ragionamento devo fare per svolgere questi esercizi:

-Quali delle seguenti affermazioni è vera:
a)n2=Omega grande((n+log n)2)
b)n2=Omega grande((n log n)2)
c)n2=Omega grande((n log n)2)
d) nessuna delle precedenti affermazioni è vera.


-Quali delle seguenti affermazioni è vera:
a)n=O (n sin2 n)
b)n=O(2log n)
c)n=O(log2n)
d)n=O(n–log n)


Potreste per favore spiegarmi tutto il ragionamento che devo fare per poi arrivare alla soluzione finale?grazie mille.
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #1 on: 24-11-2011, 09:26:16 »

bluegirl devi solamente andare ad applicare la definizione di Omega, e le funzioni prima del segno dell'uguale è la nostra f(n), quindi devi dimostrare se f(n)=Omega(g(n))..
Ciao
Logged
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #2 on: 24-11-2011, 11:15:21 »

si questo lo sò anche io, fin qui c'ero arrivata ma mi confondo nei confronti cioè nell'eseguire i calcoli per dimostrare  ed arrivare quindi alla soluzione finale. Qualcuno per favore mi può mostrare i singoli passaggi?
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 on: 24-11-2011, 13:35:53 »

Primo esercizio:

Vediamo prima di tutto la a)
 (n\ +\ lg n)^2\ =\ n^2\ +\ 2nlgn\ +\ (lgn)^2 quindi n^2 \ = \ \Omega(n^2);

Siccome è vera possiamo fermarci qui (analizzando la b e la c puoi vedere che sono false).

Secondo esercizio:

a) sin^2 è un numero compreso tra 0 e 1 quindi nsin^2n\ <=\ n  quindi n\ \not=\ O(n) per cui la prima è falsa;
b)2^logn\ =\ n^log2\ =\ n  quindi n\ =\ O(n) per cui la b) è vera. Potremmo fermarci qui avendo trovato l'affermazione vera. Però andiamo avanti.
c) banalmente  non è vera.
d)dovrebbe invece essere vera anche.


Ci sono quindi tre possibilità:
O hai sbagliato a copiare qualcosa;
O le risposte vere sono due;
O io sbaglio qualcosa (la più probabile).
Comunque il ragionamento è questo.
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!
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #4 on: 24-11-2011, 15:28:58 »

Grazie cock, chiarissimo...che mondo sarebbe senza il tuo aiuto :-) ahaha
cmq ho controllato ed il testo l'ho ricopiato corretto, quindi saranno 2 le risposte vere
Logged
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #5 on: 24-11-2011, 18:19:46 »

cock controllando però le solizioni, come soluzioni corrette sono segnate nella prima la d), e nella seconda la a...però mi sà che son sbagliate


EDIT: ok confermato, sono sbagliate le soluzioni e corrette le tue. fai finta che non abbia scritto nulla :-)
« Last Edit: 24-11-2011, 18:26:29 by bluegirl » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #6 on: 25-11-2011, 01:39:12 »

Grazie cock, chiarissimo...che mondo sarebbe senza il tuo aiuto :-) ahaha
[Emoticon] Asd

cock controllando però le solizioni, come soluzioni corrette sono segnate nella prima la d), e nella seconda la a...però mi sà che son sbagliate


EDIT: ok confermato, sono sbagliate le soluzioni e corrette le tue. fai finta che non abbia scritto nulla :-)

eheh meglio così!!! 
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!
Pages: [1]   Go Up
Print
Jump to: