Benvenuto!
Accedi
o
registrati
.
08-12-2019, 22:52:55
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
LAUREA TRIENNALE (D.M. 270/04)
»
II anno
»
Algoritmi, 9 CFU
(Moderator:
Domenico Cantone
) »
Come risolvere questa ricorrenza? (compito di oggi 08/03)
Pages: [
1
]
2
Go Down
« precedente
successivo »
Print
Author
Topic: Come risolvere questa ricorrenza? (compito di oggi 08/03) (Read 2105 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Edgarpoe
Apprendista Forumista
Offline
Gender:
Posts: 338
"Sorridi, domani sarà peggio"
Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
on:
08-03-2012, 19:22:19 »
T(n) = 3T(n/5) + T(n/2) + n
L'albero di ricorsione dovrebbe essere una cosa del genere:
n
/ \
/ \
/ \
3(n/5) n/2 ->11/10n
/ \ / \
3(n/25) n/10 3(n10) (n/4) ->77/100n
Sto sbagliando qualcosa? non mi riesce di stabilire una regola per il costo dell'iesimo livello.
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
Edgarpoe
Apprendista Forumista
Offline
Gender:
Posts: 338
"Sorridi, domani sarà peggio"
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #1 on:
08-03-2012, 19:33:31 »
Ho trovato dove sbagliavo:
n
/ \
/ \
/ \
3(n/5) n/2 ->11/10n
/ / \
3[(n/25) n/10] 3(n10) (n/4) ->121/100n
Il costo è n(11/10)^i
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
Offline
Posts: 114
Compila o non compila, questo è il problema!
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #2 on:
08-03-2012, 19:35:56 »
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..
EDIT: Come non detto :-)
Logged
Flyer
Apprendista Forumista
Offline
Posts: 100
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #3 on:
08-03-2012, 19:38:14 »
Quote from: ExEcUtIvE on 08-03-2012, 19:35:56
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..
EDIT: Come non detto :-)
Potresti scrivere i passaggi che hai fatto?
Logged
ExEcUtIvE
Apprendista Forumista
Offline
Posts: 114
Compila o non compila, questo è il problema!
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #4 on:
08-03-2012, 19:47:55 »
Quote from: Flyer on 08-03-2012, 19:38:14
Potresti scrivere i passaggi che hai fatto?
Credo che ti interessa sapere maggiormente il punto in cui si capisce che è lineare...Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..
«
Last Edit: 08-03-2012, 22:05:30 by ExEcUtIvE
»
Logged
Edgarpoe
Apprendista Forumista
Offline
Gender:
Posts: 338
"Sorridi, domani sarà peggio"
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #5 on:
08-03-2012, 19:54:27 »
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
Offline
Posts: 114
Compila o non compila, questo è il problema!
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #6 on:
08-03-2012, 19:55:49 »
Quote from: Edgarpoe on 08-03-2012, 19:54:27
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?
si scusa mi sono confuso un attimo il procedimento che ho fatto è per la serie con ragione >1 XD ...corretto!!
Logged
Edgarpoe
Apprendista Forumista
Offline
Gender:
Posts: 338
"Sorridi, domani sarà peggio"
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #7 on:
08-03-2012, 20:15:19 »
Quote from: ExEcUtIvE on 08-03-2012, 19:47:55
Quote from: Flyer on 08-03-2012, 19:38:14
Potresti scrivere i passaggi che hai fatto?
Credo ti interessa sapere maggiormente il punto in cui si capisce che è lineare...
Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..
E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
Offline
Posts: 114
Compila o non compila, questo è il problema!
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #8 on:
08-03-2012, 21:45:05 »
Quote from: Edgarpoe on 08-03-2012, 20:15:19
E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato
ecco qui quella parte, scritta bene..è lo svolgimento della serie..
http://www.image-share.com/ijpg-1338-66.html
non l'ho svolta tutta, però questo è il pezzo più "complesso"..
«
Last Edit: 08-03-2012, 21:47:33 by ExEcUtIvE
»
Logged
Edgarpoe
Apprendista Forumista
Offline
Gender:
Posts: 338
"Sorridi, domani sarà peggio"
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #9 on:
08-03-2012, 21:52:36 »
Grazie davvero
Logged
"Beauty of whatever kind, in its supreme development, invariably excites the sensitive soul to tears".
ExEcUtIvE
Apprendista Forumista
Offline
Posts: 114
Compila o non compila, questo è il problema!
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #10 on:
08-03-2012, 22:37:11 »
Quote from: Edgarpoe on 08-03-2012, 21:52:36
Grazie davvero
Figurati, se non ci si aiuta tra colleghi... ;-)
Logged
chernobyl
Matricola
Offline
Gender:
Posts: 79
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #11 on:
09-03-2012, 10:46:01 »
Ragazzi ma allora la risposta esatta è O(n)?
Logged
eLis
Apprendista Forumista
Offline
Gender:
Posts: 111
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #12 on:
09-03-2012, 10:50:01 »
No la risposta è
. La sommatoria dà
ma questa è moltiplicata per
Logged
The Man in Black fled across the desert, and the Gunslinger followed.
chernobyl
Matricola
Offline
Gender:
Posts: 79
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #13 on:
09-03-2012, 10:51:51 »
allora ho risposto giusto!
Logged
Vincenzo Cutello
Administrator
Forumista
Offline
Gender:
Posts: 600
Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
«
Reply #14 on:
09-03-2012, 17:51:03 »
Quote from: eLis on 09-03-2012, 10:50:01
No la risposta è
. La sommatoria dà
ma questa è moltiplicata per
Ok, finalmente qualcuno che corregge
Logged
Pages: [
1
]
2
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...