Pages: 1 2 [3] 4 5   Go Down
Print
Author Topic: Domanda compito  (Read 9298 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #30 on: 07-03-2010, 00:05:21 »

Un grafo orientato fortemente connesso se solo se...

a)esiste un cammino da un dato vertice u a ogni altro vertice v
b)esiste un cammino da ogni vertice u ad un dato vertice v
c)esiste un cammino da un dato vertice u a un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

la risposta giustya è la d secondo me
si è la d.
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!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #31 on: 17-04-2010, 11:17:58 »

Data l'equazione di ricorrenza T(n) = T(n-1) + T(n-2) + n, la sua soluzione è ( scegliere il bound più stretto)

a.   O(n^2)

b.   O(n^2 log n)

c.   O(2^n)

d.  O(n^n)

Ho eseguito lo svolgimento attraverso l'albero di ricorsione e mi risulta la c (probabilmente mi sbaglio). Secondo voi?
Grazie.
« Last Edit: 17-04-2010, 11:20:24 by gam » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #32 on: 17-04-2010, 11:27:14 »

si dovrebbe essere giusta!
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!
peppe
Matricola
*
Offline Offline

Posts: 15



WWW
« Reply #33 on: 19-04-2010, 09:37:14 »

salve ragazzi.. ma questi testi d'esame dove li prendete? qualcuno può farmi avere delle copie?
(magari uppandole da qualche parte così che le possa scaricare)

bye 
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #34 on: 19-04-2010, 12:05:29 »

mandami la tua mail in pm
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!
miky
Apprendista Forumista
**
Offline Offline

Posts: 102


« Reply #35 on: 19-04-2010, 12:37:19 »

scusa cock86 potresti gentilmente inviarmi qualche copia anche a me???
Logged
Nova
Forumista
***
Offline Offline

Gender: Male
Posts: 567


-.-"


WWW
« Reply #36 on: 20-04-2010, 11:21:28 »

Ragazzi ma i testi dei compiti dove li avete trovati? Mi indichereste un link?

Grazie ^^
Logged

Ubuntu user:
#29872
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #37 on: 21-04-2010, 19:20:29 »

Sia T(i,n) una funzione che indica la complessità computazionale di Heapify quando chiamata a partire dall'elemento i-esimo, in una heap di n elementi. Allora, per 2i \leq n e costante c

a. T(i,n)=T(2i,n) + c

b. T(i,n)=2T(i,n) + c

c. T(i,n)=2T(2i,n) + c

d. T(i,n)=T(i/2,n) + c

Potrebbe essere la a secondo voi?
Grazie.
« Last Edit: 21-04-2010, 19:39:16 by gam » Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #38 on: 21-04-2010, 19:38:10 »

Vi viene data una lista di n numeri interi compresi tra 1 e 1000. Qual'è il miglior algoritmo di ordinamento possibile per ordinarli?

a. Bucket Sort

b. Insertion Sort

c. Quicksort

d. Mergesort

Non capisco come rispondere a questa domanda senza fare assunzioni sull'input. Voi che ragionamento fareste?
Grazie.
Logged
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #39 on: 21-04-2010, 20:07:53 »

>bucket Sort , quando c'è un range di input finito è sempre bucket sort


il motivo è che i bucket di bucket sort devono avere un range finito (ed essere molti  con pochi elementi)per applicare con tempo o(n) insertion sort!

ciaau Wink

Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #40 on: 22-04-2010, 14:12:21 »

Quali delle seguenti affermazioni non è vera:

a. n=O(n sin^2 n)

b. n=O(2^logn)

c. n=O(log^2 n)

d. n=O(n - log n)

come rispondereste?

EDIT: la b l'ho scritta male, la correggo con n=O(2^(logn))
« Last Edit: 22-04-2010, 15:20:25 by gam » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #41 on: 22-04-2010, 14:38:09 »

Quali delle seguenti affermazioni non è vera:

a. n=O(n sin^2 n)

b. n=O(2^logn)

c. n=O(log^2 n)

d. n=O(n - log n)

come rispondereste?
sicuro il testo sia giusto???
io ragionerei così...
intanto escluderei la b e la c perchè tanto sono uguali.

poi...
a. non è vera perchè n moltiplicato un numero comreso tra 0 e 1 è sempre minore di n quindi non è asintoticamente maggiore cioè O(n) di  n.
d. vera perchè O(n-lgn)=O(n) visto che lg n è polinomialmente minore.

poi se vogliamo ragionare sulle escluse...
log n è asintoticamente minore di n quindi non può essere minore di n e allora sarebbero false!
mi è venuto il dubbio che sia sbagliato il testo, però probabilmente ho sbagliato in qualcosa!

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!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #42 on: 22-04-2010, 15:01:04 »

Sia T(i,n) una funzione che indica la complessità computazionale di Heapify quando chiamata a partire dall'elemento i-esimo, in una heap di n elementi. Allora, per 2i <=n e costante c
non saprei però possiamo raggionarci...

il fatto che 2i<=n vuol dire solo che siamo nella prima metà del heap, e quindi almeno una chiamata possiamo farla.
L'heapify fa risalire da i ad n , quindi in n/2 perchè ci troviamo nella prima metà del heap, allora potrebbe essere la d.
Tu come sei arrivato alla A?!
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!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #43 on: 22-04-2010, 15:18:01 »

no, vabbè mi sn accorto che la a non poteva essere (ci ho pensato dopo); si cmq concordo con te per la d.
Grazie
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #44 on: 22-04-2010, 21:49:21 »

ti ho convinto? wow!!!  comunque se hai bisogno d'altro...
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 2 [3] 4 5   Go Up
Print
Jump to: