Appunti di Statistica

Algoritmi

25 febbraio

Lezione 1

Esame: Progetto da fare a gruppo o da soli e consegnarlo.

Orale con domande su esercizi fatti a lezione e per casa.

Consegna progetto su Moodle, entro la data di chiusura delle iscrizioni per l’esame su sol.

Gli orali vengono programmati con data e ora con calendario, per esigenze specifiche mandare email.

Chi fa il progetto a coppie deve fare l’orale insieme.

Introduzione

Python traduce “letteralmente” le cose in linguaggio di computer (binario) come un traduttore che traduce ad un politico che parla.

C, Java, PHP … leggono tutto e poi traducono, ottimizzando quindi e rimuovendo e eliminando sezioni inutili, quindi ottimizzano lo script, come uno che traduce un libro: prima lo legge in lingua originale, lo capisce e poi lo traduce.

Anaconda

Consiglio installare Anaconda per usare Python.

Immediate mode

Posso operare Python in 2 modi: ogni volta che scrivo una riga poi la invio ed esegue, avvio ogni volta a fine di ogni riga.

Script mode: scrivo tutto lo script e poi quando ho finito viene eseguito tutto insieme, sempre una riga per volta, ma “avvio” una volta sola.

Dati semplici

Algoritmo: un algoritmo è una lista di istruzioni senza ambiguità.

Programma (fase 2): scrivere l’algoritmo in modo giusto.

Esecuzione (fase 3): l’algoritmo viene eseguito.

Bugs di programmazione, che non fanno “girare” l’algoritmo.

Debugging

Processo di ricerca e correzione dei bugs è detto debugging.

3 tipi di errori:

• Errore semantico: algoritmo funziona ma il “risultato” (numero) è sbagliato e non sappiamo perché. Tendenzialmente difficile da trovare e risolvere. Per evitare, scrivo un paio di righe e le provo, quando sono sicuro che funziona scrivo altro. Evitare di scrivere tutto e poi farlo girare. Vanno testate le “parti” di codice. Capita perché quello che abbiamo scritto non è quello che volevamo scrivere.
• Errore di sintassi: Si riferisce alla struttura del programma e alle regole per scriverlo correttamente. Esempio: scambiare e inserire un punto invece di una virgola, non chiudere una parentesi…
• Errori di esecuzione: Appaiono solo quando il programma viene eseguito, detti anche eccezioni perché indicano che qualcosa di eccezionale e negativo è accaduto.

Python è un linguaggio tipato dinamicamente: se assegno un nome o un valore a qualcosa poi posso cambiarlo.

N=2 e poi N=Nato.

Questo è certamente più comodo ma pericoloso, potremmo non accorgerci di eventuali errori commessi.

Su altri programmi, staticamente programmati, questo non si può fare: se ad una cella viene inserita una stringa, allora poi deve rimanere tale, devo quindi specificarlo subito all’inizio.

N=2 N=3 kay. No N=casa.

Mercoledì 26 febbraio

Lezione 2

Ci sono alcuni nomi e simboli che non possono essere usati per nominare celle perché usati da Python per altre funzioni.

X=7: “x prende 7”, nomino la cella x con 7.

Su R invece x->7.

Su Python non stampa in automatico, sono solo azioni che il computer fa.

Espressioni: 2+2 mi fa ritornare un valore ovvero 4, ma non mi viene mostrato, resta interno. print.

Istruzione, ordini o procedure: esempio la print. Sono ordini, non azioni che ritornano qualcosa.

Operandi e operatori si assegnano a espressioni: / divisione intera, // divisione con virgola.

Funzioni di conversione

Tradurre e converte in un intero.

Int(2345a) non passa e dà errore.

Uguale per fruit.

Posso anche prendere un intero e trasformarlo in stringa.

2+3 interi fa 5 e vale anche per le parole, le unisce quindi.

2+3 stringhe fa 23.

Operatore di modulo restituisce il resto della divisione.

Aggiornamento di variabile

X=6.

X=X+1 fa 7.

Variazione di variabile: se ho a=5 b=3 e voglio scambiarle allora faccio: c=a a=b b=c, se ho copiato bene.

Tartarughe comunica all’esterno tramite l’interfaccia. Dipende quindi dallo stato di un oggetto, in questo caso una tartaruga.

Sono funzioni “normali”, le altre dette statiche.

Ciclo for

For: per ogni valore di f fai questa operazione, ogni operazione è detta iterazione, quindi ripete.

Range

Esempio: range(1, 5) restituisce 1234, non 5.

Range(1, 5, 2): il 2 rappresenta il passo, by di R.

range(10, 0, -1): 10 9 8 7 6 5 4 3 2 1, non 0.

Il numero finale del range non viene mai reso.

Modulo Math e Modulo Random

Modulo Math: sono funzioni statiche, ovvero che non dipendono da oggetti.

Modulo Random: vengono generati numeri da una distribuzione uniforme fra 0 e 1, non compreso, con media 0.5.

Come con R posso settare il seme per replicare il risultato: random.seed(171), sto dettando il seed a 171.

Se non metto il seed viene preso da Python con la data e ora fino al millisecondo, questo numero viene usato come seed.

Lezione 3. Giovedì 27 febbraio

Funzioni

La print fa azioni ma non restituisce un qualcosa, nel senso che non calcola e non fa altre azioni, mi mostra semplicemente.

Main: è una funzione che avviene sempre.

Def: è una funzione che avviene solo se viene invocata.

Parametri formali: li inserisco e stanno lì (t, s, z).

Parametri attuali: quando poi do effettivamente un valore a (t s z).

Vedi ch04_1.

Funzioni che ritornano un valore

print: funzione, azione.

2+2: espressione, chiedo qualcosa e attendo che il computer calcoli.

In Python in realtà sono tutte funzioni.

abs rende il valore assoluto.

ch04_square: def. La riga 123 non eseguono perché sono poi a riga 5 si dà un valore alla X e alla riga 6 si mette in pausa e il controllo passa alla riga 1 e calcola, poi alla riga 3 ritorna y, che corrisponde al risultato.

Poi ripassa alla riga 7, bloccanti o sincrone.

In questo caso sono dette funzioni per cui il programma si mette in pausa e torna su e ricalcola, poi riprende al punto in cui era, come qui da 6 torna e calcola 123 e salta 56 e riparte a 7.

La print è diversa dal return perché la print stampa sullo schermo e basta. Il return calcola e “salva” quel valore, se non lo scrivessi, in automatico Python inserisce un return None.

Variabili e parametri sono locali

Nella CodeLens1(bad-local) c’è errore perché il print(y) non può eseguirlo, non esiste una y perché senza il return quel risultato sopra non si è salvato, quindi è come se non esistesse più.

Mai usare variabili globali.

CodeLens: 2 (cl-power-bad): qui il valore di power=3 che viene salvato nel sistema è 3 ma il calcolo viene effettuato con power=2 quindi solo per l’operazione usa 2 ma per il resto varrà 3.

Accumulazione

Funzioni che chiamano altre funzioni

Detto stick, pila, perché si impilano una sopra l’altra.

Composizione

Scriviamo funzioni isolate e poi le combiniamo insieme.

Valori booleani e espressioni booleane

Utili per prendere decisioni.

Su Python il valore TRUE e FALSE devo scriverlo True con T maiuscola e False altrimenti viene preso come valore “stringa”.

Operatori logici

and: vero se tutti veri. OR: vero se almeno 1 lo è. NOT nega il valore, quindi rende T se è falsa.

Precedenza degli operatori

Esecuzione condizionale: selezione binaria

Sono espressioni che ritornano True o False.

Omettere else

Condizioni annidate

Meglio evitarle, potrebbero portare a errori.

Catene condizionali

El viene eseguita se nessuna delle precedenti è vera, segue quindi la prima che trova vera, se le successive sono anche vere, non vengono eseguite. Prova il Activcode1(sel4) inserendo X=7.

(Sel4it5) mi mostra cosa stampa, se inserisco gli if, else, elif bene, posso stampare alcune righe sapendo che se stampa riga 2 allora anche riga 1 è vera.

if dentro al else si possono usare ma si deve stare attenti perché fanno confondere e ci portano a errori, perdiamo il conto di dove siamo.

elif è un’abbreviazione di else if.

Lezione 4. Martedì 3/3/26

Lezione 4. Martedì 4 marzo

5==5 fa la verifica T o F come R. X != Y: X diverso da Y.

Verifica di proprietà di sequenza

Scandisce cercando quello che voglio, ho una Flag che parte F e poi diventa T appena trova quello che cerco e rimane a T.

Valori booleani

Espressioni booleane: espressioni che ritornano valori booleani ovvero T o F.

Se non la sai bocci all’esame. Fondamentale.

Quando si parla di proprietà si parla di proprietà booleane.

Es1: appena trova il pari la Flag si setta su TRUE. Ne basta quindi 1 sui 4.

Errore è impostare che valuta solo l’ultimo numero e non 1 sui 4.

Es2 valuta che tutti gli elementi rispettino qualcosa, pari. La FLAG parte TRUE e si mette in FALSE appena trova il controesempio, elemento dispari.

Errore: mettere Else: Flag=False.

Matematicamente, se un insieme è vuoto, dire che per l’insieme vuoto vale una certa proprietà è giusto, qualunque proprietà sia.

Legge di De Morgan

Si basano su questo le cose viste sopra.

Il ciclo for rivisitato

WHILE esegue qualcosa fino ad ottenere un qualcos’altro stabilito prima.

Nel while tocca a noi incrementare la variabile. Altrimenti si crea un loop.

Quindi anumb=anumb+1.

Il ciclo si ferma perché abound è fisso, mentre anumb si incrementa.

Sequenza 3n+1

Termina quando n!=1.

Si può dimostrare che termina per un n specifico, basta sostituire e calcolare, ma non posso dimostrarlo per un n qualunque.

Non può esistere un programma che controlla e dice se termina o meno, ma l’unico modo che ho per analizzarlo è eseguirlo, quindi se non termina non avrò mai una soluzione, magari termina fra 100 anni, oppure non termina. Però so che se termina subito, allora termina.

Non posso quindi scrivere un programma che dice se un altro programma termina: problema della terminazione.

Problema della correttezza: uguale a sopra, se è corretto allora ho una risposta e funziona, ma se non termina potrebbe essere sbagliato oppure serve più tempo, non posso saperlo.

Metodo di Newton

Migliorare un’approssimazione, tipo Taylor.

Nel Activecode1 nel print della 9 e 10 riga non cambia, perché cambierebbero i decimali dopo, ma non sono presi in considerazione, quindi non va oltre. Questo è un esempio, in realtà i numeri decimali usati sono molto più di questi.

Posso aggirare, mettendo un while ma rischio il loop.

Questa uguaglianza non è quasi mai una buona idea, perché rischio il rimbalzo in loop quando arrivo a numeri con tantissimi decimali che vengono poi approssimati dal sistema in automatico sull’ultima cifra decimale.

Quindi come si fa? Si scrive l Better - Approxe l < di un certo valore.

Cosa è la ricorsione

È una funzione che chiama se stessa, definita quindi in termini di sé stessa.

Lezione 5. Mercoledì 4 marzo

Lezione 5. Mercoledì 5 marzo

Ricorsione: funzione che richiama se stessa.

Fattoriale

Una funzione è detta ricorsiva se all’interno richiama se stessa. Il chiamante si congela nel momento in cui chiama, aspettando il risultato della chiamata, questo accade ad esempio con la Def.

Ad esempio il fattoriale di n è il fattoriale di n(n-1)!.

Devo poi definire il caso quando arrivo a 0 e deve darmi 1: if n==0 return 1.

Nel modellino, il chiamante è la riga 7 ed il factorial di 4 viene eseguito sostituendo 4 a n.

Calcola il factorial di 4, si mette in pausa, diventa bianco, e poi calcola il factorial di 3, si mette in pausa, …. Arriva a n=0 ed entra nel if e dà 1.

A questo punto può eseguire riga 5 che esegue: 1x1 che fa 1 e viene ritornato al 2, quindi fa 2x1 che fa 2 e viene ritornato a 3 e fa 3x2 …

Conversione binaria

Interattivo 2: conversione di un numero in binario.

19=10011.

19=2x9+1.

9=2x4+1.

4=2x2+0.

2=2x1+0.

Quindi 19=10011, li metto dal basso verso alto.

1=2x0+1. 1.

(2*4)+0(2*3)+0(2*2)+1(2*1)+1(2*0)=19.

116 192 +0+ ++ 0 =.

Non è casuale che il fattoriale di 9 sia 1001. Conversione binaria:

Fibonacci

25-Fib(s) sono passi.

1- chiamerei qui.

Calcolerei Fib(4), sistema le dimentica le cose già sistemate quindi ma e, fin(2) ricalcolare .fib(3) Ed() FID(d)· gFb(2) fib(2) YTib(i).

Quindi devo scriverlo bene iterativo, senza ricorsivo. Ovvero:

Def b(n).

If n==0:

Return 0.

If n==1:

Return 1.

Quindi fa un numero di passi che è circa N, sopra faceva 2^N.

Old=1.

Oldold=0.

For I in range(2, n+1).

New=old+oldold.

Oldold=old.

Old=new.

Return new.

Torre di Hanoi

Va risolta con sistema ricorsivo, perché scriverla in iterativo sarebbe lunghissima.

Pseudocodice: scrittura non ambigua del codice, che poi posso riscrivere in Python, Java…

Def hanoi(n, p1,p2,p3).

If n==1: print(“sposta da”, P1,”n”, p2).

Else: hanoi(n-1, p1, p3, p2) #da P1 a P2 usando P3. Print(“sposta…. Come sopra).

Def hanoi(n,P1, P2, P3): Hanoi(n-1, p3,p2,p1).

If n==1: Print (“sposta da” + P1 + “a” +P2).

Else: Hanoi(n-1, P1, P3, P2). Print (“sposta da” + P1 + ”a” + P2). Hanoi(n-2, P3, P2, P1).

Chiamiamola: hanoi(4, “A”, “B”, “C”), quindi sposta 4 dischi da A a B usando come perno C.

Ci vorranno (2ⁿ)-1 passi e non è possibile scrivere un algoritmo migliore.

Problema decidibili: per il cui posso scrivere un algoritmo.

Problema non decidibile: non posso scrivere un algoritmo.

Stringhe come collezioni di caratteri

Sequenza di caratteri, quindi l’ordine conta, possono avere ripetizione, quindi non sono insiemi. Gli indici di Python partono da 0, quindi il primo carattere si trova in posizione 0.

Posso usare anche gli indici negativi, riferendomi all’ultimo valore della stringa chiamandolo -1.

Operazioni su stringhe

Posso chiedere ad una stringa di darmi il suo n-esimo carattere. Per ottenere la lunghezza della stringa uso len().

Confronto fra stringhe è lessicografico, in ordine alfabetico ma le maiuscole vengono prima delle minuscole.

Regola generale di Python: in un intervallo, l’ultimo valore è sempre escluso: se dico di prendere valori da 1 a 3 lui prende 1 2, e non 3. Se voglio il 3 devo fare da 1 a 4.

Di una stringa posso vedere se c’è una sequenza continua oppure se ci sono gli elementi singoli anche sparsi: voglio vedere se c’è la combinazione esatta.

Intera sequenza.