Benvenuto!
Accedi
o
registrati
.
06-12-2019, 09:12:21
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
Vecchi ordinamenti ad esaurimento
»
Laurea Triennale (D.M. 509/00)
»
Algoritmi 1
(Moderator:
Vincenzo Cutello
) »
risposte esatte
Pages: [
1
]
2
3
...
12
Go Down
« precedente
successivo »
Print
Author
Topic: risposte esatte (Read 30487 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
danilotrix
Matricola
Offline
Posts: 46
risposte esatte
«
on:
19-02-2009, 16:24:11 »
qualcuno sa le risposte esatte del compito B?
saluti
Logged
Syco
Matricola
Offline
Gender:
Posts: 31
Re:risposte esatte
«
Reply #1 on:
19-02-2009, 17:04:35 »
se postate anche le domande qualche anima pia potrebbe risolverli...così possono rispondere solo quelli che c'erano e se le ricordano...
Logged
www.axelfilm.com
danilotrix
Matricola
Offline
Posts: 46
Re:risposte esatte
«
Reply #2 on:
19-02-2009, 17:14:12 »
sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata
a)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i)
con j=size[x]
b)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i)
con j=size[left[x]]+1
c)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i-j)
con j=size[left[x]]+1
d)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i-j)
else
return Select(right[x],i)
con j=size[left[x]]+1
grazie
Logged
info
Guest
Re:risposte esatte
«
Reply #3 on:
19-02-2009, 17:21:35 »
e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad 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 ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v
grazie
ciao
Logged
rob
Apprendista Forumista
Offline
Posts: 104
Re:risposte esatte
«
Reply #4 on:
19-02-2009, 17:40:43 »
Quote from: info on 19-02-2009, 17:21:35
e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad 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 ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v
grazie
ciao
Risposta giusta d
Logged
"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
rob
Apprendista Forumista
Offline
Posts: 104
Re:risposte esatte
«
Reply #5 on:
19-02-2009, 17:46:24 »
Quote from: danilotrix on 19-02-2009, 17:14:12
sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata
a)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i)
con j=size[x]
b)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i)
con j=size[left[x]]+1
c)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i)
else
return Select(right[x],i-j)
con j=size[left[x]]+1
d)
Code:
if(i=j)
then return x
else if i<j
then return Select(left[x],i-j)
else
return Select(right[x],i)
con j=size[left[x]]+1
grazie
risposta esatta c
Logged
"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
info
Guest
Re:risposte esatte
«
Reply #6 on:
19-02-2009, 18:13:41 »
ok grazie cm pensavo...cmq ormai che ci siamo, posto anche qste due su cui ho avuto dubbi:
======= ======= ======= ======= =======
si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n
======= ======= ======= ======= =======
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
grazie ciao
Logged
rob
Apprendista Forumista
Offline
Posts: 104
Re:risposte esatte
«
Reply #7 on:
19-02-2009, 18:20:57 »
Quote
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
grazie ciao
risposta esatta d
L'altra ancora non l'ho risolta.....è abbastanza rognosa
Logged
"Se posso riposare all'ombra di un albero è perchè qualcuno lo ha piantato"
Yngwie
Forumista
Offline
Gender:
Posts: 849
Maestro! mi dia un MI in chiave di SOL!
Re:risposte esatte
«
Reply #8 on:
19-02-2009, 18:25:20 »
Quote from: info on 19-02-2009, 18:13:41
si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n
sono quasi sicuro che è la b...infatti sbagghiai
Logged
Link Immagine
♪ ♪♫♪ ♪ ♫ ♪ ♪ ♪ ♪ ♪ ♪♫♪
FIRMA ANCHE TU LA PETIZIONE PER REINTRODURRE SUL MERCATO IL WINNER TACO-ALGIDA!!!
info
Guest
Re:risposte esatte
«
Reply #9 on:
19-02-2009, 19:01:29 »
grazie Yngwie, cmq vediamo se qlcuno conosce la risposta certa.
ciao
Logged
bakks87
Apprendista Forumista
Offline
Posts: 162
Re:risposte esatte
«
Reply #10 on:
19-02-2009, 19:58:34 »
ragazzi ma per il compito A ?
qualcuno che abbia verificato le domande da fonti attendibili?
Logged
bakks87
Apprendista Forumista
Offline
Posts: 162
Re:risposte esatte
«
Reply #11 on:
19-02-2009, 20:21:57 »
ad esempio nel compito A, domanda 8:
"Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?
a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort
io ho messo la b, poichè Insertion Sort è efficiente per piccoli input; a questo punto, la proposizione "piccoli numeri interi compresi tra 0 e 1000" , soddisfa la condizione *per piccoli input* ??
ho un dubbio in questo punto...forse la risposta esatta è una tra c) e d)
Logged
info
Guest
Re:risposte esatte
«
Reply #12 on:
19-02-2009, 20:28:24 »
ma perchè hai escluso il Bucket Sort che è in tempo lineare?
Logged
bakks87
Apprendista Forumista
Offline
Posts: 162
Re:risposte esatte
«
Reply #13 on:
19-02-2009, 20:29:09 »
mmm
ho escluso la risposta esatta?
Logged
goblin
Guest
Re:risposte esatte
«
Reply #14 on:
19-02-2009, 20:42:24 »
Quote from: bakks87 on 19-02-2009, 20:29:09
mmm
ho escluso la risposta esatta?
Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..
Logged
Pages: [
1
]
2
3
...
12
Go Up
Print
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...