Newsgroup: it.comp.ia
Titolo: Kolmogorov

Sto cercando della documentazione sulla complessita di Kolmogorov ma non
sono riuscito a trovare niente in italiano e tutto ciň che ho trovato in
inglese č un po' troppo riassuntivo e mi č abbastanza incomprensibile.
Qualcuno  saprebbe darmi qualche indicazione di dove posso trovare qualcosa
in italiano o in inglese ma che spieghi bene i concetti ?
Un' altra domanda : ho letto da qualche parte che l' "indice"  di
complessitŕ dato da Kolmogorov cioč il piů "piccolo" programma che
rappresenta i dati č un prolema incomputabile , ma queto č stato dimostrato?
se si dove posso trovarne la dimostrazione  o se magari c'č qualcuno che  me
la puň esporre .
Grazie.
Fl...@geocities.com

In aggiunta al mio messaggio precedente.
Proprio oggi ho visto il nuovo numero di "The Computer Journal"
che e` completamente dedicato all'argomento.
Per chi e` interessato:
http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_04/
-- Davide.

...


Pape' Satan, pape' Satan aleppe, comincio' FleX con voce chioccia:
F> programma di ordinamento che effettua un numero di confronti minore di
F> N*LogN il che non mi sembra molto corretto o per lo minimo mancano un bel
si', di confronti. Tutto corretto.
F> po' di ipotesi aggiuntive visto che mi sembra abbastanza semplice creare un
F> programma per ordinare che effettui un numero di confronti pari a KN dove K
F> è una costante basti pensare di utilizzare il valore dell' elemento del
F> vettore da ordinare come indice di un secondo molto più grande vettore
F>  tipo una HASH ) .
si chiama counting sort e non e' un algoritmo di ordinamento basato
sul confronto :-)
Richiede tempo lineare, come altri suoi colleghi (es. radix sort e
bucket sort).
-- 
ciao,
Claudio

Hai ragione il  problema stà proprio nel dover tornare a scorrere i dati nel
secondo vettore.
Ma in definitiva direi che si può affermare che non si riesce a ridurre la
complessità algoritmica massima perchè si parte  dall' ipotesi che non si fa
nessuna restrizione sui dati da ordinare altrimenti si potrebbero
raggiungere  complessità prossime allo zero basti pensare che conoscendo la
dimensione massima del vetore in ingresso da ordinare potrei fare uso di una
tabella gigante con già all' interno tutti i vettori pessobili di quelle
dimensioni per tutti i tipi possibili già ordinati, di conseguenza mi
basterebbe una sola istruzione per avere il vetore ordinato Es.
    VETTORE_ORDINATO=TABELLA_VETTORI [ VETTORE_INPUT ]
A questo punto mi sembrerebbe di aver fatto uno spostamento di complessità
da temporale a spaziale .
Qui sorgono un po' di quesiti :
   - E' sempre possibile effettuare uno spostamento di complessità mettendo
una limitazione di memoria come in questo caso?
   - E' stata trovata una legge che regoli gli spostamenti di complessità ?
cioè dato un algoritmo che utilizza una complessita temporale Ft1 ed una
complessità spaziale Fs1 variando la complessità temporale in Ft2 c'è una
legge che mi dice quale sarà la minima Fs2 di questo algoritmo ?
Ciao.
Flex.

   - E' stata trovata una legge che regoli gli spostamenti di complessità ?
Non ha senso, poiché dipende dal tipo di problema (oltreché dal tipo
di criterio adottato e dal tipo di macchina usata per implementare
l'algoritmo). Se ad esempio ti chiedo di creare un programma che sia
in grado di dirmi quanti numeri pari ci sono in un elenco, la
complessità minima è e rimarrà sempre lineare se si usano i normali
PC, eppure può essere ridotta a zero se si hanno particolari vincoli
sul numero dei dati (max N), sulla loro precisione (K bit) e si hanno
disponibilità finanziarie non trascurabili da sprecare: in questo caso
di può progettare un dispositivo in grado di analizzare fino a N
elementi da K bit in parallelo (in pratica si realizza una serie di N
coppie (cella di memoria)-(ALU)). Come vedi dipende molto anche dalla
creatività delle persone.
Ciao, Max.

creatività delle persone.
Eseguire processi in  parallelo è un altro paio di maniche , forse intendevi
dire che si potrebbero fare dei processori con delle istruzioni
specializzate per un determinato problema che mi facciano diminuire la
complessità algoritmica , ma anche qui si cade sempre nello stesso problema
di  dover utilizzare più memoria , se non fosse così la macchina di touring
non sarebbe universale , la complessità algoritmica di Kolmogorov non
esisterebbe ( la teoria di complessità di Kolmogorov si basa principalmente
sulla dimostrazione dell' indipendenza  della complessità di un problema dal
linguaggio in cui è formulato ) perchè la complessità di ogni problema
dipenderebbe dal linguaggio ( o elaboratore   )  uilizzato , ecc...
salterebbero un bel po' di teorie informatiche non trovi ?
Eseguire un analisi di N elementi in parallelo significa utilizzare N
processi in parallelo ed in definitiva lo si può pensare come utilizzare N
macchine di touring in parallelo.
Per cui direi che ha proprio molto senso cercare una legge di conversione di
complessità perchè sicuramente non dipende dalla  macchina utilizzata come
ho spiegato sopra  ,   non ho capito cosa intendi con il criterio adottato ,
sicuramente dipende da caratteristiche del problema .
Penso comunque che qualcuno abbia già formulato delle teorie in questo
seenso , se
qualcuno ne è a conoscenza mi farebbe piacere saperne qualcosa.
Ciao
Flex.