Nella magnetostatica del vuoto,abbiamo a che fare con i momenti meccanici e magnetici delle spire percorsi da correnti e quindi in presenza di campo magnetico. In questo articolo lo vediamo più in dettaglio con una spira rettangolare.
Nella magnetostatica del vuoto,abbiamo a che fare con i momenti meccanici e magnetici delle spire percorsi da correnti e quindi in presenza di campo magnetico. In questo articolo lo vediamo più in dettaglio con una spira rettangolare.
Salve a tutti oggi si parla di heaps binari. Cosa sono e come vano creati.
Un heap è un array che può essere visualizzato come un albero binario quasi completo .
Quasi completo significa che tutti i livelli ,tranne l'ultimo,sono completi:possono mancare alcune foglie consecutive a partire dall'ultima foglia a destra
Esempio in immagine :
Un array che rappresenta un heap binario è un oggetto con
due attributi:
length[A] `e il numero di elementi (la dimensione) dell’array
heap-size[A] `e il numero di elementi dell’heap memorizzati
nell’array
Ci sono 2 cose fondamentali da sapere sugli heaps :
1. La radice dell’albero è A[1] (si trova in posizione 1)
2. Le operazioni per ricavare il padre Padre[i] ,il figlio destro destro[i] e il figlio sinistro sinistro[i] di un nodo i sono:
Padre[i]
return parte intera(i/2)
sinistro[i]
return 2i
destro[i]
return 2i+1
Ecco un esempio di heap binario con la sua visualizzazione in albero binario:
Esistono due tipi di heap binari: max-heap e min-heap
In entrambi i tipi di heap binario, i valori dei nodi soddisfano
una proprietà le cui caratteristiche dipendono dal tipo di heap
Proprietà del max-heap: in un max-heap ogni nodo i diverso
dalla radice `e tale che A[padre[i ]] >= A[i ]
Questa regola ha 2 conseguenze:
1: l’elemento più grande di un max-heap viene memorizzato nella
radice
2: un sottoalbero di un nodo u contiene nodi il cui valore non `e
mai maggiore del valore del nodo u
Il min-heap si comporta in modo duale ,quindi da ora in poi,parlando di heap,mi riferisco a max-heap.
Per costruire un heaps abbiamo bisogno di dell’algoritmo HEAPIFY.
Questo algoritmo ha per obbiettivo di mantenere la proprietà del heaps cioè
A[padre[i]] >=A[i]. Quindi come input abbiamo un array in un certo ordine e alla fine in output questo array sarà un heaps binario.
Prima si cerca il massimo fra il nodo i e i suoi figli ,poi si sostituisce il nodo i con il massimo trovato e si richiama ricorsivamente l’algoritmo per il figlio che ha appena scambiato valore con i. Praticamente si va verso il basso.
largest è la variabile che rappresenta il massimo fra i due figli.
Il costo di Heapify in un (sotto)albero di dimensione n è pari:
al tempo costante c necessario per stabilire il massimo fra gli
elementi A[i ], A[sinistro(i )] e A[destro(i )]
più il tempo per eseguire Heapify in un sottoalbero con radice
uno dei figli di i
La dimensione di ciascun sottoalbero non supera 2n/3 perché siamo in un albero quasi completo.
Il tempo di esecuzione di Heapify può essere espresso dalla
seguente ricorrenza
T(n)<= T(2n/3) + c
Per il teorema master, la soluzione di questa ricorrenza e O(log2 n)
Per la costruzione del heap utilizziamo Heapify su tutti i nodi fra
1 e parte intera(n/2). Perché?
Visto che tutte le foglie possono essere considerate heaps di dimensione 1,basta sistemare con Heapify tutti i nodi che non sono foglie in ordine decrescente.
Ogni chiamata costa O(log2n) ci sono O(n) chiamate quindi siamo a O(nlog2n)
Possiamo fare di meglio osservando che il tempo di esecuzione
di Heapify varia al variare dell’altezza del nodo nell’heap.
Un’analisi più rigorosa si basa sulle seguenti informazioni:
-uno heap di n elementi ha un’altezza di log2n
per ogni k = 0, . . . , log2n ci sono al più n/2k+1 nodi di
altezza k
-una chiamata di Heapify su un nodo di altezza k e O(k)
Il costo T(n) di Build-Heap e limitato da:
Dopo i calcoli ci rendiamo conto che il costo di Build-Heap è O(n).
Basta per oggi,Spero che hai imparato qualcosa leggendo questo articolo. Se hai dei dubbi o suggerimenti,lasca un commento qui sotto.
giorno 1:Forza di Lorentz
giorno 2: La prima legge di Laplace
giorno 3: La seconda legge di Laplace
giorno 4: La legge di Gauss
giorno 5:Momenti di una spira percorsi da corrente
giorno 6 :Spira rettangolare immersa in un campo magnetico
giorno 7: Legge di Ampere con dimostrazione
giorno 8:La legge di Faraday
giorno 9: Legge di Lenz
giorno 10: Legge di felici
giorno 11: Autoinduzione
giorno 12: Energia Magnetica
giorno 13: Vettore Magnetizzazione
giorno 14: Densità di corrente
giorno 15: Campo magnetico H
giorno 16: Legge di Ampere -Maxwell
giorno 17: suscettività e permeabilità magnetica nei mezzi lineari
giorno 19:Condizioni al contorno di B e H
giorno 20: classificazione dei materiali magnetici
giorno 21: circuito magnetico
giorno 22: Riluttanza magnetica
giorno 23: La legge di Hopkinson
Oggi vediamo più in dettaglio l’algoritmo di ordinamento per inserimento.
Come richiesto da l’Algor method ,eseguiro 4 passi.
1.Il Problema
Ordinare dei dati omogenei (dello stesso tipo) o in ordine crescente o decrescente dipendendo dell’applicazione specifica.
2.Struttura dati usata
Di solito si usa un array di interi. Ma questo può variare nelle applicazioni specifiche.
3.Pseudo codice
Praticamente l’algoritmo si comporta come un umane che vuole ordinare una mano di carta. Al ’inizio , tutte le carte sono sul tavolo,con la mono destra prendo una a una le carte e le metto sulla mano sinistra nel posto giusto. Per mettere la carta nel posto giusto ogni volta ,faccio un paragono con le carte della mano sinistra. Ora che sappiamo come fa l’algoritmo ,ecco lo pseudo codice :
INSERTION-SORT(A)
1. for j <-- 2 to length[A]
2. do key <-- A[J]
3. // inserire A[j] nella sequenza ordinata A[1..j -1]
4. i <-- j - 1
5. while i>0 and A[i]>key
6. do A[i + 1] <-- A[i]
7. i <-- i - 1
8. A[i + 1] <-- key
Notiamo che l’ordinamento usa un solo array per questo si parla di ordinamento in place.
Key rappresenta la nuova carta da inserire ogni volta nella mano sinistra.
A[1..j-1] rappresenta la mano sinistra cioè la parte de l’array già ordinata.
J serve ad indicizzare la variabile da inserire in A[1..j-1]
I permette di scorrere A[1..j-1] cioè da j-1 a 1.
il primo ciclo While è quello che fa prendere ogni volta una variabile key da inserire dentro A[1..j-1].
il secondo ciclo invece è quello che fa trovare il posto giusto a key paragonandolo ogni volta ad un elemento di A[1..j-1].
Ora che abbiamo capito come funziona l’algoritmo attraverso questo pseudo codice calcoliamo la complessità
4.Complessità
Per calcolare la complessità ,dobbiamo calcolare quante volte viene eseguita una istruzione. un istruzione presente in un ciclo viene eseguita un numero di volte pari a quanti indici il ciclo coinvolge con il contatore. Se associamo una costante cj ad ogni istruzione ,otteniamo qualcosa di questo tipo:
La somma è quindi c1*n+c2*(n - 1) + c4*(n - 1) + c5*£ + c6*(£ - 1) + c7*(£ - 1) + c8*(n - 1)
Ora vediamo di calcolare £. Il ciclo dalla riga 5 alla 7 va dell’indice 1 a j – 1, quindi il costo di ogni riga di questo ciclo diventa cj*(j – 1). Ma ognuna di queste righe si trovano nel grande ciclo che va dalla prima all’ultima riga (indice coinvolti sono di n - 1); quindi
Questo ci da un risultato dell’ordine di
Conclusione La somma totale è circa
La complessità nel caso peggiore è quindi una forma quadratica.
Spero che hai imparato qualcosa leggendo questo articolo. Se hai dei dubbi o suggerimenti,lasca un commento qui sotto.
1.Quale problema risolve il mio algoritmo?
2.Quali strutture dati usa il mio algoritmo ?
3.Qual è il pseudo codice del mio algoritmo ?
4.qual è la complessità del mio algoritmo?
Copyright 2010 L'università è facile
Designed by Free Wordpress Themes |
Bloggerized by Lasantha - Premiumbloggertemplates.com | customized by Willy
Top Web Hosts | Web Design by Ciplex | GetNetSet
Benvenuto caro Lettore!
UF è un blog di ingegneria informatica pieno di articoli più o menoo tecnici. Iscriviti per rimanere aggiornato all'uscità dei prossimi articoli.