Newsgroup: it.scienza.informatica
Titolo: algoritmi

ciao a tutti premetto di non essere informatico ma chi di voi può 
darmi una definizione di algoritmo?
grazie
vitone
-- 
Fratelo! ricordati che devi morire!
Inviato da 
www.mynewsgate.net

Da 
it.wikipedia.org
 :
"Nella sua definizione piu' semplice ed intuitiva un algoritmo e' una
sequenza ordinata di passi semplici che hanno lo scopo di portare a
termine un compito piu' complesso."
Comuqnue se cerchi su google trovi tonnellate di definizioni.
 Raffaello


Io l'ho sentita enunciare cosě:
"Un algoritmo č una sequenza finita di passi (istruzioni) che portano da 
una sitauzione iniziale ad una situazione finale, appartenente ad un 
gruppo di situazioni desiderate"
Poi, come dice giustamente Raffaello, si possono dare molteplici (ed 
equivalenti o equivalentemente corrette) definizioni di algoritmo.
Ciao,
Davide

Davide
Saluti,
MARco
-- 
xref: 
http://mar.i.am/~u16803.34077/it.scienza.informatica/defalgoritmi,it
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14


A parte la punteggiatura incerta potrebbe andare se "appartenente" si riferisce
a "situazione finale"
Ciao,
Xenon.

 Direi come definizione non va proprio bene.
Sono daccordo, l'algoritmo *porta* una situazione verso un'altra... non i
singoli passi.
A questo punto potrei anche dire
Un giorno, dopo aver bevuto troppo, un tizio disse:
"E se desidero che trasformi la situazione iniziale in qualcosa di non
desiderato? Esiste quest'algoritmo?"
in vino veritas (parafrasando).

 
Non esiste una definizione _formale_ di algoritmo. Ci sono stati diversi
tentativi per formalizzare il concetto di algoritmo, qualcuno ha parlato di
macchine di Turing altri di funzioni intuitivamente computabili. La teoria
della computabilità (detta impropriamente anche calcolabilità) si occupa
(anche) di questi aspetti. Cerca con google per maggiori informazioni.
Una definizione _informale_ ma abbastanza intuitiva e generale (comprende
tutte le definizioni che trovi negli altri post) può essere:
"un insieme finito di istruzioni che vengono interpretate da una macchina"
Esempio: una ricetta di cucina è un algoritmo che viene interpretato da un
cuoco.
ciao
Marco

 "un insieme finito di istruzioni che vengono interpretate da una macchina"
    Più che "vengono interpretate", sarebbe meglio dire "interpretabili".
    In realtà, un algoritmo sarebbe meglio definirlo come un "insieme di 
istruzioni", senza aggiungere altro. Se diciamo che l'insieme è finito, non 
comprendiamo algoritmi di "auto-scrittura" del codice, che prevedono che sia 
l'algoritmo a riscrivere se stesso (ad esempio: un algoritmo genetico). Se 
parliamo di "raggiungere uno scopo", hanno già risposto altri. Si potrebe 
forse aggiungere "ordinato", nel senso che ad ogni istruzione ne segue 
un'altra, decisa dall'algoritmo stesso e dallo stato del problema. Così 
facendo, non sarebbe però possibile definire "algoritmi" tutti quelli che 
prevedono multitasking ed esecuzione in dipendenza da eventi esterni...
    Insomma, ogni insieme di istruzioni è un algoritmo, sia che faccia 
qualcosa di utile, sia che non serva a nulla. IMHO, ovviamente.
Stefano 

 cuoco.
e l'esempio contraddice la definizione visto che il cuoco non è , per 
definizione, una macchina.E' criticabile anche la definizione che parla 
di "stati" attraverso i quali passa l'esecutore dell'algoritmo. 
Un'algoritmo la cui unica funzione è quella di controllare due valori, 
non cambia lo stato dell'esecutore nè nessuna delle variabili, eppure si 
parla di un algoritmo. Credo che questa sia una delle migliori trovate: 
(A. Bertossi " Algoritmi e struttre dati") Il termine algoritmo, che 
significa procedimento di calcolo,deriva dal latino medioevale 
algorismus, termine che deriva a sua volta dal matematico usbeco 
Mohammed ibn-Musa al-Khowarismi. Tale termine indica la descizione 
precisa di una sequenza di azioni che un esecutore deve compiere per 
giungere alla soluzione di un qualsiasi problema computazionale. Mentre 
l'enunciato del problema specifica la relazione tra l'ingresso e 
l'uscita , l'algoritmo descrive la sequenza di azioni da eseguire per 
ottenere l'uscita desiderata a partire dall'ingresso."

qualcosa di utile, sia che non serva a nulla. IMHO, ovviamente.
Forse sarebbe meglio dire sequenza di istruzioni.
Personalmente definirei come algoritmo una "sequenza di istruzioni
finite che termina" (le procedure non terminano, ma un algoritmo deve
terminare per definizione).
-- 
Linux Registered User #181013
"La scienza e' un'equazione differenziale.
La religione e' una condizione al contorno."
(ALAN M. TURING)

 in vino veritas (parafrasando).
In tal caso quel tizio ubriaco sta "desiderando" di trasformare la
situazione iniziale in qualcosa di non desiderato.
Sembra un paradosso, ma è colpa del vino.
In tal caso quindi l'algoritmo di tizio rientra in quella definizione.
Al massimo in quella definizione non rientrano gli algoritmi buggati :))

 in vino veritas (parafrasando).
In tal caso quel tizio ubriaco sta "desiderando" di trasformare la


 terminare per definizione).
    Credo che sia molto facile confondere un algoritmo con un programma. 
Questo rende le cose ancor più difficili, quando si tenta di dare una 
definizione di algoritmo. Esistono però algoritmi che non terminano. Pensa 
all'algoritmo per il calcolo del seno o di e o, più semplicemente, 
all'algoritmo della divisione, in alcuni casi. Questi terminano, quando 
decidi di averne avuto abbastanza... di decimali ;)
Stefano 

 decidi di averne avuto abbastanza... di decimali ;)
lo traduco con
    if(ne hai abbastanza) restituisci valore
anche questa quindi č un istruzione (che determina proprio la "fine"
dell'algoritmo)
IMHO, l'algoritmo deve necessariamente avere un numero finito di passi,
altrimenti non sarebbe computabile. Non
risolverebbe un bel niente.
Inoltre sottolineo la seguente:
Che l'esecuzione del programma vada "in loop eterno" č una cosa,
tuttavia -ad esempio -l'algoritmo
     while(true) ;
ha una ed una sola istruzione.
Che qualsiasi insieme di istruzioni, che facciano qualcosa o meno, sia un
algoritmo non credo affatto.
A questo punto potrei considerare l'insieme vuoto delle istruzioni. Anche
quello sarebbe un algoritmo?
Semmai IMHO qualunque insieme di istruzioni semanticamente coeso potrebbe
essere un'algoritmo candidato, in quanto
tale insieme potrebbe considerarsi un *Sistema*.
Comunque sia, tali questioni sono materia di studio della logica, IMHO i
"pareri a limite" ( ovvero megaidee su base puramente intuitiva) sono troppo
spesso scorretti, almeno a causa dei fraintendimenti del linguaggio.
bye

 
Non sono daccordo, c'è differenza tra algoritmo ed implementazione
dell'algoritmo.
L'algoritmo descrive in maniera astratta i passi da compiere per ottenere un
determinato risultato.
L'algoritmo della divisione è quello che ci hanno insegnato alle elementari
e che (per gli irrazionali) potrebbe descrivere una serie infinita di
istruzioni.
E' evidente che non può esistere una macchina che mi risolve in un tempo
finito un calcolo di quel tipo. Per questo l'implementazione di
quell'algoritmo si dovrà necessariamente preoccupare di porre un termine
alla computazione. Anche se in teoria, grazie all'algoritmo, potremmo
continuare a calcolare all'infinito cifre decimali.
P.S. Leggo in continuazione "IMHO". Che vuol dire?
Ciao, Antonio
.

 P.S. Leggo in continuazione "IMHO". Che vuol dire?
    In my Hown Opinion, praticamente "secondo me". Serve per non sembrare
saccenti ;))))
Stefano

 P.S. Leggo in continuazione "IMHO". Che vuol dire?
In
My
Humble
Opinion
= "A mio modesto parere"
E' usato quando si vuol essere cauti nelle affermazioni.
Puoi trovare altri utili acronimi qui:
http://www.freewebz.com/iosononiubbo/vocabolario.html
 Raffaello

 determinato risultato.
infatti io non ho detto che l'algoritmo "descrive istruzioni", bensì le
determina, ossia, in parole spicciole:
l'algoritmo *è* un insieme finito ed ordinato di istruzioni che "fanno
qualcosa", ossia che può modificare (ed in genere lo fa) lo stato di
qualcosa. Si può avere la post-condizione degenere in cui questo qualcosa è
identicamente trasformato in se stesso (lo stato non varia). In tal caso
l'algoritmo degenera nel senso dei risultati, ma ciò non inficia la mia
pseudo definizione.
che poi le istruzioni siano astratte (dal punto di vista del linguaggio
utilizzato) è un'altra questione... non per niente nel citato
libro di Bertossi viene citata la parola computazione...eheh.
bye

Stefano Gemma wrote:

Sephirot intendeva IMHO questo:
un algorimo è una sequenza finita di istruzioni, in quanto finita ha una
fine ;)
l'esecuzione di un algoritmo invece può non terminare.
ciao

 bye
Il problema è che una definizione formale di algoritmo non è stata ancora
trovata, proprio per i problemi che sono emersi in questa discussione. Uno
propone una definizione, ma l'altro trova il caso particolare che non
rientra nella definizione generale.
ciao
Marco

 ottenere l'uscita desiderata a partire dall'ingresso."
Qui però cerca anche di definire informalmente il significato del termine
"problema", è un altro discorso.
ciao
Marco

 Stefano
Concordo, ma ribadisco che la parte dell'interprete comunque andrebbe messa.
Comunque sono piccole cose.
ciao
Marco

 bye

 funzionino così, ma non me ne intendo.
[...]
    Ripensandoci, il mio esempio potrebbe non essere perfettamente coerente. 
Nel caso di algoritmi genetici che riscrivono il proprio codice, abbiamo 
comunque un algoritmo iniziale finito (come numero istruzioni, non come 
tempo di esecuzione) che muta se stesso a runtime. Il codice riscritto 
potrebbe essere considerato un algoritmo diverso, rispetto a quello 
iniziale, se non addirittura un programma distinto.
    Comunque sia, gli algoritmi genetici non sono una classe ben definita e 
possono essere sfruttati per risolvere tipi diversi di problemi, con 
implementazioni diverse. Secondo me, si ha un algoritmo genetico quando usi 
gli elementi che sono tipici:
- l'esecuzione ripetitiva dell'algoritmo su un insieme di sequenze di 
informazioni (il "DNA")
- la generazione di sequenze "figlie" delle rpecedenti (con incrocio o 
altro)
    Poi ci puoi aggiungere la mutazione delle informazioni (modifica casuale 
di uno o più "geni") ed altro, ma questo credo che sia la base minima. Lo 
scopo dell'algoritmo e che cosa rappresentino queste "sequenze di 
informazioni", sono IMHO irrilevanti, per determinare se un algoritmo sia di 
tipo genetico o meno. Ciò significa che puoi benissimo costruire un 
algoritmo genetico in cui le sequenze di informazioni sono istruzioni di un 
programma... o passi di un algoritmo, perfino dell'algoritmo genetico 
stesso. Ciò non significa che sia stato realizzato e/o che sia utile farlo, 
solo che è perfettamente possibile ed implementabile.
    Dal mio punto di vista, anche le reti neurali possano essere viste come 
una forma di algoritmo genetico. Questo anche quando non si usa un AG, per 
determinare i nuovi pesi ad ogni iterazione. Quando si usa la 
retropropagazine dell'errore, per ricalcolare i pesi, si sta in realtà 
generando una rete figlia della precedente, in cui è intervenuta solo la 
mutazione, anche se non casuale. la rete figlia sarà più "esperta" della 
madre, ma ne erediterà buona parte della struttura e del comportamento.
Stefano
 

l'esecuzione di un algoritmo invece può non terminare.
Mi spiego meglio.
Sul fatto che un algoritmo e' una sequenza finita di istruzioni, penso
(spero) siamo d'accordo.
In piu' nella mia uni usano indicare come algoritmi solo quelle
sequenze finite di istruzioni la cui esecuzione termina, quindi la
sequenza "while (true) print 2" non e' chiamata algoritmo, bensi' si
usa il termine procedura.
Si tratta solo di convenzione.
"Some writers restrict the definition of algorithm to procedures that
eventually finish."
[ 
http://en.wikipedia.org/wiki/Algorithm
 ]
Tra l'altro e' la prima volta che leggo quella pagina, sembra molto
curata (poteva non esserlo?).


[CUT]
In effetti se come algoritmo genetico si considera qualsiasi algoritmo che
"imita" il comportamento di certi processi biologici, hai perfettamente
ragione. In effetti solo il 5% del DNA è codificante, il resto sono spesso
regioni di controllo che le puoi vedere come algoritmi.
Comunque la tua autocritica è fondata. Quindi gli algoritmi sono sequenze
_finite_.
ciao
Marco