Ordinamenti

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Non so quanto questo problema sia noto... non so quanto interessi... Solo che per quello che ho letto carpao si occupa di informatica (deadlock etc...)
Tra le altre cose, mi sono letto molti dei suoi vecchi problemi e devo dire che vi ho trovato molte cose belle (peccato non essere arrivato prima).
Adesso però è sempre impegnato a quanto pare e pure giù di morale, quindi ho pensato che magari un problemino "informatico" poteva dargli un pò di carica (e magari dargli l'input per proporre qualche nuovo e bel problema).
O magari fa filosofia e ho sbagliato tutto, ma oramai lo scrivo lo stesso:
"Se avete un vettore di n elementi tutti distinti, dimostrare che un algoritmo che fa solo confronti impiega almeno log_2(n!) operazioni per ordinarlo (ossia asintotiamente n*log_2(n))".
_________________
I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.

rama10 · Inviato: Mar Ott 16, 2007 2:28 pm Oggetto:

Ma questo non è un indovinello. L'algoritmo di cui stai parlando tu è un algoritmo di ordinamento chiamato heap sort. Io l'ho studiato qualche mese fa in un esame di programmazione C.
Sinceramente non te lo so dimostrare bene, non me lo ricordo, e poi dovrei farlo con carta e penna perchè non si possono scrivere segni matematici come la sommatoria.

Io invece ti propongo un'altro rompicapo. Dati n numeri INTERI compresi tra 0 e t (con n >> t ) riesci a trovarmi un algoritmo che riesca ad ordinarli senza fare nemmeno un confronto?

KitCarson · Inviato: Mer Ott 17, 2007 11:54 am Oggetto:

Scusa Rama,
E' da un pezzo che ho finito le scuole e temo di non ricordarmi qualche notazione: cosa significa " n >> t " ?

Ciao

Carson

rama10 · Inviato: Ven Ott 19, 2007 5:43 pm Oggetto:

n >> t significa con n "molto maggiore" di t.

Lo so che "molto maggiore" non è corretto in italiano, ma se voi chiedete ad un matematico vi risponde così....è un matematico....non un letterato....
_________________
<center>r@ma</center>