Discussioni su argomenti di Informatica
03/05/2019, 15:18
Parto subito con un esempio.
Sono informazioni tratte dal libro Algoritmi e strutture dati, ed. 2, di Bertossi e Montresor.
C'è un algoritmo molto semplice, il seguente:
"il minimo di un insieme A è l'elemento di A che è minore o uguale ad ogni elemento di A".
Questa ricerca richiede che ogni valore sia confrontato con tutti gli altri, per un totale di n(n-1) confronti, dove n è la dimensione di A.
Viene abbozzato un algoritmo descritto così: si sceglie il primo elemento di A come minimo parziale, copiandolo in una variabile min. Si confronta min con gli elementi compresi fra le posizioni 2 e n; ogni volta che si incontra un elemento minore, si aggiorna il minimo parziale. Al termine, min contiene il minimo dell'insieme.
Più avanti si dice che questo algoritmo richiede n(n-1)/2 confronti.
Ma non è uguale al precedente (descritto solo in linguaggio naturale)?
La domanda che mi pongo è sostanzialmente come fare a capire quanti passaggi fa un algoritmo per arrivare alla soluzione, cioè da dove si ricava quel n(n-1).
Grazie.
03/05/2019, 15:42
La proprietà di essere minimo è transitiva, quindi se un elemento è maggiore di almeno un altro non può essere il minimo. Questo vuol dire che l'algoritmo seguente
- Codice:
m = A[1]
for i in 2:n {
m = min( m, A[i] )
}
calcola il minimo in \(\displaystyle (n-1) \) confronti. Nota che la funzione min fa un solo confronto. Non so dove tu ci veda un fattore n/2.
03/05/2019, 17:50
Dato un insieme di \(n\) elementi, quante sono le coppie di elementi di tale insieme? Possiamo pensare di scegliere un elemento a caso per il primo elemento della coppia e poi scegliere tra gli \(n-1\) rimanenti per il secondo. Abbiamo così ottenuto le coppie ordinate. Se non ci interessa l'ordine dovremo dividere tale numero per metà.
Ma il secondo algoritmo è lineare e molto diverso dal primo. Se ti dice che il numero di confronti è \(n\,(n-1)/2\) c'è un errore nel tuo libro di testo.
04/05/2019, 10:47
vict85 ha scritto:La proprietà di essere minimo è transitiva, quindi se un elemento è maggiore di almeno un altro non può essere il minimo. Questo vuol dire che l'algoritmo seguente
- Codice:
m = A[1]
for i in 2:n {
m = min( m, A[i] )
}
calcola il minimo in \(\displaystyle (n-1) \) confronti. Nota che la funzione min fa un solo confronto. Non so dove tu ci veda un fattore n/2.
Non sono io che ci vedo un fattore n/2, ho riportato quanto scritto nel libro, che appunto mi confondeva. Se c'è un errore però, non è stato segnalato perché non c'è nemmeno nell'errata corrige uscita successivamente. In ogni caso, a parte questo, mi interessava sapere come arrivare a trovare questo numero di confronti.
Secondo voi cosa bisogna padroneggiare della matematica per superare un esame di algoritmi e strutture dati?
Grazie.
04/05/2019, 11:03
apatriarca ha scritto:Dato un insieme di \(n\) elementi, quante sono le coppie di elementi di tale insieme? Possiamo pensare di scegliere un elemento a caso per il primo elemento della coppia e poi scegliere tra gli \(n-1\) rimanenti per il secondo. Abbiamo così ottenuto le coppie ordinate. Se non ci interessa l'ordine dovremo dividere tale numero per metà.
Ma il secondo algoritmo è lineare e molto diverso dal primo. Se ti dice che il numero di confronti è \(n\,(n-1)/2\) c'è un errore nel tuo libro di testo.
A quale secondo algoritmo ti riferisci?
04/05/2019, 15:25
L'errore nel libro c'è, quel \(n(n-1)/2\) è al più un limite teorico dell'algoritmo, ovvero qualsiasi algoritmo che faccia più confronti fa sicuramente lo stesso confronto \(2\) o più volte.
Riguardo a numero dei confronti nel mio algoritmo, quante volte viene ripetuto il ciclo? Quanti confronti ci sono per ripetizione del ciclo. Calcolati questi due valori li moltiplichi tra di loro.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.