La formula di Legendre e la sua utilità nelle applicazioni

Premessa

Siamo partiti da un presupposto, siamo interessati ad un problema, che ci serve per sviluppare un algoritmo efficiente per i fattoriali: vogliamo trovare la massima potenza di 2 che divide n!. Questo significa che vogliamo estrarre tutti i due che possiamo e formare la massima potenza, cioè :

Ci viene in aiuto una famosa formula matematica. Appunto la formula di Legendre e ci da la massima potenza di 2 che divide n! In realtà questa formula  è anche più generale cioè è in grado di darci il 𝞶 (valutazione du-adica) anche per altre basi non soltanto per il 2. A noi ci interessa usare la massima potenza di due perché per il computer è un operazione immediata. Perché basta che setta un bit nella rappresentazione binaria di un numero. Quindi non deve fare nessun algoritmo o particolare procedimento. Deve soltanto impostare un bit e nessuno dispendio dal punto di vista computazionale.

In generale  la base può essere un primo qualunque, e l'esponente viene chiamato la valutazione p-adica di M, con M qualunque intero positivo.

La formula di Legendre ci risponde a questo problema generale, cioè dato un qualunque primo(primo) ci consente di trovare la massima potenza di quel primo che divide n!
Quindi dati n! ci da il 𝞶 cioè la massima potenza di p che divide n! e sara :

Algoritmi classici di manipolazione dei bit

Famigliarizziamo con gli operatori Bitwise

Un trucco nella manipolazioni Bitwise. Consideriamo un qualunque numero N ≥ 1, supponiamo che abbia una certa rappresentazione binaria,che rappresenta in binario(sequenza di bit es 1000100)un certo valore in questo caso il nostro N. Se fossimo interessati al seguente problema:

1) Determinare il valore del bit che si trova all'estrema destra, cioè il bit meno significativo(LSB (Least Significant Bit, bit con peso minore). Invece il bit all'estrema sinistra è il più significativo(MSB (Most Significant Bit, bit con peso maggiore).

Questo problema lo possiamo  risolvere utilizzando  gli operatori logici. Si vuole determinare il primo 1 partendo da destra (LSB) cioè il rightmost set bit. A questo scopo si utilizza l'AND con il numero 1,in modo da far venire tutti zeri  a sinistra del bit che voglio determinare. Quindi utilizzo : N AND 1 se utilizzo VBnet.
Invece in C# si usa N & 1.  Ed ottengo il valore del bit all'estrema destra(LSB) perchè  otteniamo 0 o 1, viene 0 se N aveva 0  all'estrema destra e viene 1 se N aveva all'estrema  1. In questo modo elegante riusciamo ad ottenere quanto richiesto con un semplice operatore  AND  & 1. Dal punto di vista pratico questo risultato può essere rappresentato in questo modo:

1) Se il numero all'estrema destra è 1 ⤍ Dispari

2) Se il numero all'estrema destra è 0 ⤍ Pari

Perché ciò che fa il numero( in questo caso N)pari o disapari è proprio l'ultimo numero, in quanto negli altri numeri posso sempre tirare fuori il 2 come fattore. Quindi i numeri a sinistra  del LSB sono sempre pari e diventano dispari proprio o rimangono pari proprio in virtù del valore che assume il bit all'estrema destra(LSB).

2) Determinare il conteggio dei bit = 1(set bit) nella rappresentazione binaria di N.

Cioè come in questo esempio fatto a mano, mi calcolo il numero di bit = 1. Vogliamo scrivere un algoritmo che sia in grado di restituirci questo risultato.

Una prima idea, più semplice e Naive è quella di andare a sfruttare questa capacità che abbiamo di andare a vedere qual'è il valore del bit all'estrema destra. E poi schiftiamo via via questo numero e controlliamo quanto vale quest cifra all'estrema destra se vale 1 cumuleremo una nuova unità se è zero non lo conteremo. Possiamo utilizzare l'operatore di shift verso destra e poi andare a vedere tra con l'AND  tra l'N e 1 il bit all'estrema destra. 

Alla fine mi ritroverò con tutti zeri. Quindi:

l'algoritmo Naive ⤍ consiste nel prende il numero, andare a fare l'And tra il numero e 1 ovvero N AND 1  per vedere se l'ultimo bit è 0 o 1 e via via shitfare verso destra fin quando arriviamo ad un N = 0.

Vediamo un modo più efficiente di contare i bit attraverso:

l'algoritmo di Kernighan ⤍  che utilizza N AND  N-1, riduce notevolmente il numero di passaggi, in quanto diventano pari al numeri di bit=1 che ci sono dentro al numero N. Non facciamo più un numero di passaggi pari al  numero totale di bit che ci sono nella rappresentazione binaria del numero, come nell'algoritmo Naive. Ma stiamo facendo un numero di passaggi che è uguale al 
numero di bit = 1 che ci sono nella rappresentazione binaria del numero. Quindi l'N AND  N-1 va a resettare il bit=1 più a destra e così via via in loop. Cioè significa fare  il loop dove faccio un    AND tra   N e N-1  e si fa un unset (resetta)  del bit = 1 che si trova nell'estrema destra. Quando gli ho azzerati tutti cioè N = 0,vuol dire che ho finito. Basta contare quante volte giro nel loop e  mi da il numero di bit = 1.

Un altro problema classico elegantemente risolto dagli operatori Bitwise è il seguente:

3)Determinare la più grande potenza di 2 esempio 2^k che divide N. Cioè vogliamo essere in grado di esprimere N nella seguente forma :

Come una certa potenza di due moltiplicato per l'intero dispari che  che residua come fattore. A questo scopo si utilizza l’operatore bitwise AND tra il numero N in questione e il numero NOT N-1. Cioè sarà:

Soluzione elegante, dove in un colpo solo andiamo a  risolvere questo problema senza nessun loop.

4)Determinare la massima potenza di 2 che divide un numero n fattoriale, dove n≥1 è un intero.

Cioè si vuole scrivere n fattoriale come: n! = 2^𝞶 * D, dove D è un numero dispari.

A tale scopo si utilizza la formula di Legendre che ci darà come risultato esattamente 𝞶 a cui siamo interessati.  𝞶  sarà la valutazione duatica di n!

Cioè dato un n!  ci da la massima potenza di p che divide n!. cioè ci da il proprio quel 𝞶 t.c

Una semplificazione si ottiene quando n è una potenza di 2 e quindi si ha che 𝞶 è esattamente n-1

Applicazione7

 Creare una applicazione winform in VB.NET che calcoli la retta di regressione di Y rispetto a X, il coefficiente di accostamento R² e la scomposizione della varianza da un dataset bivariato reale a piacere preso da Internet. Ad esempio, si può prendere dalla banca dati: https://data.world/datasets/multivariate o qualsiasi altra fonte si desideri. Possibilmente usare dei dati che vi interessano personalmente e trarre qualche conclusione personale dai risultati. Per il calcolo di media, varianza, covarianza, ovviamente utilizzare le formule di ricorrenza che abbiamo studiato (Knuth, Welford, ...) e non le formule naive.
 Riscrivere o tradurre l'applicazione in C# controllando la corrispondenza dei risultati e discutendo eventuali punti di interesse/attenzione e divergenza tra i linguaggi.

https://drive.google.com/file/d/1oqrEuznXy64t4C3TB3rRj4Y1Q2DWS4yW/view?usp=sharing

Gli operatori bitwise

 Gli operatori logici confrontano le espressioni Boolean e restituiscono un risultato Boolean. Vediamo prima gli operatori in VB.Net. Gli operatori And, Or, AndAlso, OrElse e  Xor sono binari perché accettano due operandi, mentre l’operatore Not è unario perché accetta un solo operando. Alcuni di questi operatori possono anche eseguire operazioni logiche bit per bit sui valori integrali.

L’ operatore Not esegue una negazione logica su un’espressione Boolean. Produce l’opposto logico del relativo operando. 
Se l’espressione restituisce True, Not restituisce False; Se l’espressione restituisce False, Not restituisce True. 

Tra gli operatori logici binari:

• L’ operatore and esegue una congiunzione logica su due espressioni Boolean. Se entrambe le espressioni restituiscono True, And restituisce True. Se almeno una delle espressioni restituisce False, And restituisce False.

• L’ operatore OR esegue una disgiunzione logica o un’ inclusione su due espressioni Boolean. Se una delle due espressioni restituisce True o entrambi restituiscono True, Or restituisce True. Se nessuna delle due espressioni restituisce True, Or restituisce False.

• L’ operatore Xor esegue l’ esclusione logica su due espressioni Boolean. Se esattamente un’espressione restituisce True, ma non entrambi, Xor restituisce True. Se entrambe le espressioni restituiscono True o entrambe restituiscono False, Xor restituisce False.

In C# abbiamo gli operatori corrispondenti a quelli visti per VB.Net che sono:

• Operatore unario ~ (complemento bit per bit) o ! (operatore logico booleano);
• Operatori di spostamento binari ≪(spostamento a sinistra) e ≫ (spostamento a destra);
• Binario: & (AND logico), | (OR logico)e ^ (OR esclusivo logico).

I principali operatori in VB.NET e C#

Premessa

Vogliamo fare una classificazione dei principali tipi di operatori che sono disponibili. Una prima classificazione si può fare considerando il numero  di operandi che l'operatore coinvolge. Parliamo di:
1) operatori Unary → coinvolge 1 operando
2)operatori Binary → coinvolge 2 operandi 
3) operatori Ternary →  coinvolge 3  operandi

Per quanto riguarda un inquadramento circa le funzionalità, possiamo distinguere operatori in base a  diverse categorie:
1) operatori di tipo aritmetico →  sono il +,-,/,*. Per quanto riguarda l'operatore modulo in C# è a%b  mentre in VB il modulo si indica con a mod b. Ci sono operatori  bitwise(interi) di tipo artimetico come lo shift → < > shift a sinistra e a destra, servono per uno scorrimento a sinistra a destra dei bit del numero a cui vengono applicati.
2) operatori logici (booleani) o bitwise(interi) →  not, and,or,xor.
3) operatori di comparazione(relazionali) → il simbolo diverso vengono indicati : <> in VB.Net e != in C#. L'uguale : = in VB.Net e == in C#confronto: < , >, <=, >=, Is ,IsNot.
4) operatori condizionali →AndAlso e  OrElse in VB.NET e && e || in C#.

Differenza  tra gli  operatori condizionali e logici

Gli operatori condizionali implementano il così detto short circuiting, ovvero quando si utilizzano tra due condizioni, la seconda viene valutata soltanto se è strettamente necessario. Invece negli operatori logici And e Or i due operandi vengono valutati in ogni caso.

Scomposizione della varianza nella regressione lineare

La varianza totale può essere scritta come  somma della varianza dei residui più la varianza spiegata.  Questa due quantità le abbiamo trovate grazie alle due proprietà:

1) la varianza dei residui viene dall'aver minimizzato i residui
2) e la  varianza di regressione la otteniamo  sfruttando la proprietà  che y medio teorico è uguale ad y medio osservato.

Partiamo dalla varianza totale, sommando e sottraendo il valore y* teorico si ottiene la varianza  facendo i prodotti incrociati,  ci viene in questo modo:

Che è la relazione che voglia, se dimostriamo che i doppio prodotto della varianza totale sia uguale a zero.

Ricordando le due proprietà derivanti dalle due derivate della funzione da minimizzare, rispetto ad 𝛃 e 𝞪 cioè :

Ed avendo come riferimento la seguente  retta di regressione :

Sostituiamo il valore di y* della retta al secondo  termine del doppio prodotto, e otteniamo l'uguaglianza con le due relazioni delle derivate. Quindi il doppio prodotto si annulla. E così si dimostra che la varianza totale è  uguale alla somma della varianza spiegata più la varianza dei residui.

Regressione lineare

Premessa

Il coefficiente di correlazione, è  un indice che ci può servire per valutare il grado di interdipendenza tra due caratteri x ed y. E' compreso tra  -1 e 1, ed   indica se c'è un legame di proporzionalità diretta o inversa tra le due variabili considerate x ed y. La cosa interessante è cercare di stabilire se  è possibile intravedere una relazione matematica tra le due variabili. A questo scopo fittiamo dei modelli matematici ai dati.


Regressione lineare

La più semplice relazione che si può cercare di intravedere tra le due variabili statistiche, è il legame lineare. Cosa ci interessa vedere?
Se è possibile rappresentare la relazione tra y e x con un modello di tipo lineare, ovvero sia rappresentabile con una retta. Ovviamente il modello lineare, potrebbe non essere adeguato per la rappresentazione dei dati. Perché i dati hanno un andamento che mal si adatta ad essere rappresentato  da una relazione lineare. Ed è questo proprio lo scopo dell'analisi lineare: vedere se è possibile stabilire una relazione di tipo  lineare e con che grado di  accuratezza è possibile farlo.  Se prendiamo un data set (x_i,y_i) con i = 1,...,n osservazioni relative a due variabili statistiche x e y. Siamo interessati a determinare una certa retta  Y = βx + 𝞪 che sia il più possibile  rappresentativa del legame lineare che c'è tra queste due variabili. Voglio una retta che sia la pi vicina possibile alla nostra nuvola di punti.

Prendiamo un punto generico y_i  e x_i e si considera il corrispondente punto sulla retta cioè y✷ e cosa è ?
E' il valore che assumerebbe y nel caso in cui tra i due caratteri ci fosse veramente questa relazione lineare. Mentre  invece y_i osservato  è quello che abbiamo osservato nella realtà. Quindi y✷ è il valore che avremmo se questo modello ideale lineare rappresentasse esattamente la relazione tra i due caratteri.  Mentre  y_i osservato è quello  che abbiamo osservato.

Obiettivo

Determinare quella particolare retta,con quei particolari parametri di β e 𝛂, che sono tali  per cui risulta minima la  somma delle distanze tra queste due quantità.

Nella regressione lineare quello che si considera come distanza è semplicemente il quadrato delle differenze tra queste due osservazioni. Quindi tra le infinite rette, prendiamo quella che se esiste  minimizza questa quantità.

Quindi la funzione da minimizzare è appunto :

Facciamo la derivata di s rispetto ad β e 𝛂 e poi 

risolviamo il sistema nelle due incognite e le vogliamo  determinare t.c sostituiti dentro al sistema mi diano zero. Svogliamo i passaggi fino ad  ottenere:
Abbiamo trovato  i due valori di  β e 𝛂 t.c questa retta  che esprime la relazione lineare tra le due variabili, sia la più vicina possibile alla nostra nuvola di punti.
    

Sostituendo questi valori ottenuti all'interno della retta,otteniamo:

Se sostituiamo ad y ed x rispettivamente il valore medio di y e di x, otteniamo la relazione 0 = 0. Cioè il punto  che corrisponde al punto medio di x e di y si trova sulla retta di regressione. La retta passa per questo punto speciale. Dato dalle medie delle due variabili. Questo punto è detto baricentro  della nuvola dei punti, cioè il centro di gravità della nuvola di punti.

Quindi questa proprietà  sta ad identificare il fatto che la nostra  retta passa vicino alla nuvola di punti.

Un altra proprietà  è la seguente :

cioè la media delle teoriche è uguale alla media di quelle osservate, questo ci assicura sulla bontà della nostra interpolazione.

Possiamo ottenere la varianza totale  come varianza di regressione(o spiegata)  più varianza dei residui ( o non spiegata) cioè:

Il rapporto tra RSS e TSS cioè tra la  (regression sum square )e la (total sum square)  mi da  il coefficiente di determinazione cioè L' R² :

identifica quanta parte della devianza totale è spiegata dal modello, questo indice è compreso tra 0 e 1. Vale 1  se tutti i punti osservati stanno sulla retta. E vale 0 se la variabilità dovuta alla regressione sia nulla. Quando le y_i teoriche  coincidono tutte quante con la media con la retta orizzontale.

Nel caso particolare della regressione lineare,  il coefficiente di determinazione è uguale al coefficiente di correlazione di Pearson al quadrato.

applicazione6

Creare una applicazione winform che utilizzi la struttura BigInteger e il meccanismo Try Catch Finally

https://drive.google.com/open?id=162WCCu1q5uI18yntYFwKGDpbGtAibqRs

applicazione5

 Creare una applicazione winform  che calcoli le medie e varianze degli interi pari e dispari (2n, 2n-1), n=1,2,... e poi calcolare la covarianza tra le due liste di valori.   https://drive.google.com/open?id=1hZSa565wTCO9RU4-7k-sZsHA1vbLb_IY

Tipi numerici a precisione arbitraria e la Struct BigInteger di System.Numerics

 Reference e DLL

Vediamo il concetto di Reference  e le  librerie linkate dinamincamente  cioè le cosi dette  DLL.  La  Reference è un elencazione di riferimenti, a moduli o  librerie che fanno parte dell'ambiente di sviluppo. Le funzionalità dell'ambiente di sviluppo sono state suddivise in tanti file, generalmente di tipo DLL.  Ciascuno dei quali contiene le funzionalità  che noi via via andiamo ad utilizzare. Con la Reference creiamo un link che può essere una libreria sviluppata in Visual Studio, o sviluppata da terzi, o dai noi stessi precedentemente al quale possiamo riferimento per linkare le corrispondenti funzionalità.







 Proveremo a linkare la libreria System.Numerics  che è una libreria di Visual Studio, ma non è linkata tra le librerie di default. La dobbiamo linkare noi per avere accesso ai tipi e alle funzionalità messe a disposizione da questa libreria. Ci mette a disposizione questa libreria,  due tipi importanti che sono il tipo Big Integer che consente  di memorizzare interi di grandezza arbitraria  con precisione arbitraria per esempio il fattoriale. Un altro tipo che ci mette a disposizione la libreria è  il tipo  Complex che serve per la rappresentazione e manipolazione di numeri complessi. A ciascuna libreria è associata un nome.space univoco! Quando si aggiunge una libreria, bisogna importare il Nomespace. Oppure la si importa sul Form cioè utilizzando  Imports System.Numeric che vale solo al livello del file.

Gli algoritmi per il calcolo del fattoriale

Premessa

Come abbiamo visto nei precedenti articoli, il numero di n permutazioni di n elementi, è pari al fattoriale di n. 

Possiamo vedere la formula calcolata dal basso all'alto facendo slittare l'indice da 1  a  n, oppure viceversa dall'alto al basso.

Esistono cinque tipi  algoritmi che possono calcolare il fattoriale:

1) L'algoritmo SplitRecursive , perché è un algoritmo semplice e veloce che non utilizza la scomposizione in fattori  primi.

2) L'algoritmo PrimeSwing  ed è il più veloce  per calcolare n !, si basa sul  "Swing Numbers" e calcola n! tramite la scomposizione in fattori primi.

3) L'algoritmo di  Moessner che utilizza solo addizioni! Sebbene non abbia importanza pratica.

4) L' algoritmo di Poor Man che non utilizza alcuna libreria Big-Integer e può essere facilmente implementato in qualsiasi linguaggio del computer.

5) L' algoritmo ParallelPrimeSwing , che è l'algoritmo PrimeSwing con prestazioni migliorate utilizzando metodi di programmazione concorrenti e sfruttando così più processori mutlipli

La struttura Try Catch e la gestione delle eccezioni

Premessa

Abbiamo visto fin'ora strutture condizionali, tipo l'if e strutture di loop tipo il do e il for. Ci rimane da vedere la struttura Try Catch, che serve per gestire gli errori o le eccezioni sollevate dai nostri programmi. Quindi le exception cosa sono?  Quando il nostro programma gira, può capitare che  incappi in situazioni dal quale  non può più dipanarsi. Esempio divisione per zero, o un file che  non trova sull'hard disk. Allora non potendo più  andare avanti solleva un eccezione, questo tipo di eccezione può essere intercettata con la struttura Try Catch. Il programmatore può intercettare questa situazione di errore e  gestirla al meglio, può mandare un messaggio di errore all'utente oppure la può sopprimere se non è un eccezione che rileva ai fini del programma. Quindi questo nuovo tipo di struttura che serve per intercettare e gestire le eccezioni. 


Sintassi

Vediamo la sintassi in VB: tra il try ed il catch si mettono le istruzioni che possono generare l'errore. Tra il catch ed il Finally si possono mettere le istruzioni nel caso si verifichi un errore cioè un eccezione.  Il linguaggio permette di distinguere tra diverse eccezioni. Quindi si possono per l'appunto definire vari catch con le rispettive eccezioni. La struttura si chiude  con End Try, c'è una sezione Finally che viene eseguita ogni caso, è una parte opzionale, che viene eseguita a tutti i costi.

Per quanti riguarda C# la sintassi è la seguente:

Quindi ricapitolando l'exception  → condizione di errore per il quale il programma non può più andare avanti. Quindi è costretto  ad interrompersi. Invece  la Call Stack → è la pila delle chiamate a partire dalla funzione corrente e via via a risalire alle funzione che l'hanno chiamata. Esempio se partiamo da una certa funzione principale:

Se abbiamo un Exception come rappresentato in figura, se c'è una struttura Try Catch ci presenta questa struttura e gestisce questa eccezione. Se non c'è  il Try Catch l'eccezione risale la Call Stack e sale su e vede se c'e' un Try Catch,altrimenti risale utta la Call Stack.

Differenze

 In VB viene semplicemente generato il primo form come punto di entrata cioè il newform1, dove c'è proprio un gestore di eccezione non gestite  chiamato MyApplication. Cioè viene istanziata la classe MyApplication che si incarica dell'avviamento del primo form e fornisce una serie di servizi, come  gestore degli eventi come :

1) le eccezioni non gestite

2) disconnessione internet ecc.

Questo comportamento è controllato nei setting di progetto. Si può disabilitare e potremmo fare quello che fa C# cioè partire da una funzione principale Main e poi procedere. In C# dunque hanno obbligatoriamente un punto di entrata cioè una funzione void chiamata Main(), cioè arriva fino alla main per gestire una eccezione che non è stata gestita. Cioè risale fino alla prima funzione se non ci sono Try Catch.

Coefficienti binomiali e loro proprietà

Premessa

Per quel che riguarda la struttura di dati, abbiamo fin'ora visto alcuni esempi con array, e le liste. Dove anch'esse hanno come gli  array indici automaticamente associati alle celle, solo che le liste sono migliori in quanto di consentono di lavorare molto più facilmente e di ridurre il rischio di fare meno errori. Adesso il nostro scopo è di utilizzare le sorted list che è una struttura di dati molto simile ad una dictionary. Nel senso che è  una lista di chiavi valore, cioè coppie di chiavi valore. Ed è anche indicizzata come una lista, queste celle sono assegnati le posizioni dalla zero  alla count -1. Per fare  un esempio che abbia qualche significato statistico della sorted list, sia utile calcolare le probabilità della distribuzione binomiale o della distribuzione ipergeometrica. Perché ci consentono di avere un esempio significativo di utilizzo della sorted list per immagazzinare una distribuzione statistica.

Coefficiente binomiale 
Introduciamo le combinazioni perché ci serviranno per introdurre il concetto di coefficiente binomiale. Qual'è la differenza tra permutazioni e combinazioni? Noi consideriamo diverse due permutazioni, se differiscono, anche per l'ordine. Invece per quanto riguarda le combinazioni, due configurazioni che hanno gli stessi elementi sarebbero uguali anche se avessero segno diverso.

1) Permutazioni → fanno riferimento agli elementi e all'ordine
2) Combinazioni → fanno riferimento agli elementi non all'ordine.

Il significato della formula qui sopra posta, sta ad identificare  la combinazione di n oggetti su k posti. L'ultima formula dell'uguaglianza è la formula esplicita del coefficiente binomiale. Si chiamano coefficienti binomiali proprio perché sono stati studiati nell'ambito dello studio delle potenze del binomio.

Cioè tra gli n fattori ne prendiamo k, stiamo parlando delle combinazioni di n elementi su k posti. La combinazione  è il fattore di replicazione di a^k. I coefficienti sono ottenuti attraverso  il triangolo di tartaglia:

Esiste una relazione di ricorrenza tra i coefficienti binomiali che fa in modo che ci possiamo calcolare i coefficienti in modo semplice:

Questa relazione di ricorrenza che giustifica la struttura del triangolo d tartaglia, ci interessano perché le utilizzeremo per le nostre applicazioni. Ora vogliamo trovare altre due relazioni che ci leghino a questi due coefficiente. Partendo dal fattoriale tronco tirando fuori l'n iniziale  per il primo elemento, invece per  il secondo abbiamo estratto il termine  del fattoriale tronco di coda. Abbiamo scorporato il primo e l'ultimo termine del fattoriale tronco. 

Tutto ciò ci è servito ai fini computazionali  per l'implementazione di algoritmi efficienti per il calcolo di  probabilità.