[python] Calcolare le soluzioni di un sistema lineare di primo grado utilizzando il metodo di Cramer (senza librerie aggiuntive)

Obiettivo: Vogliamo calcolare, utilizzando Python, tutte le soluzioni per un sistema lineare di primo grado utilizzando le matrici e il metodo di Cramer. Per farlo non utilizzeremo librerie aggiuntive, se non quanto disponibile nativamente dentro Python.

Ovviamente lo scopo dell’esercizio è l’utilizzo di Python, visto che si potrebbe risolvere agilmente con librerie come SciPy e NumPy.

Supponiamo di avere un sistema lineare come quello seguente (l’ho scopiazzato spudoratamente da YouMath, dove c’è anche un’esaustiva spiegazione sul metodo di Cramer):

\begin{cases}2x+y+z=1 \\ 4x-y+z=-5 \\ -x+y+2z=5 \end{cases}

La matrice associata ai coefficienti ed il relativo determinante sarebbe questo:

\mbox{D}=\left| \begin{matrix} 2 & 1 & 1 \\ 4 & -1 & 1 \\ -1 & 1 & 2 \end{matrix}\right|=-12

Mentre la matrice dei termini noti sarebbe:

\mbox{A}=\left| \begin{matrix} 1 \\ -5 \\ 5 \end{matrix}\right|

Giusto per curiosità la soluzione immediata con NumPy sarebbe la seguente:

Il risultato nel caso specifico darà: [-1. 2. 1.]

Noi vogliamo costruire qualcosa di simile in Python 2.7.

Cominciamo creando la base della nostra classe perché possa accettare i medesimi argomenti:

Fatto questo cominciamo a creare i metodi di cui avremo bisogno. Il metodo di Creamer con il calcolo del determinante implica, per matrici di dimensione superiore a 2×2, che si debba poter ridurre la matrice in sottomatrici.

Giusto per chiarezza, nel caso del determinante D della suddetta matrice, il calcolo si svolgerebbe in questo modo:

\mbox{D}=\left| \begin{matrix} 2 & 1 & 1 \\ 4 & -1 & 1 \\ -1 & 1 & 2 \end{matrix}\right|= 2 * \left| \begin{matrix} -1 & 1 \\ 1 & 2 \end{matrix}\right| - 1 * \left| \begin{matrix} 4 & 1 \\ -1 & 2 \end{matrix}\right| + 1 * \left| \begin{matrix} 4 & -1 \\ -1 & 1\end{matrix}\right| =\newline = 2*(-1*2-1*1)-1*(4*2-(-1)*1)+1*(4*1-(-1)*(-1)) = \newline = 2*(-3)-1*(9)+1*(3)=\newline =-6-9+3=-12

Ogni sottomatrice prende tutti i valori della matrice corrente eccetto quelli nella riga e nella colonna della posizione attuale. Scriviamo quindi la nostra funzione nella maniera seguente:

Per calcolare il determinante vogliamo fare due operazioni distinte: il calcolo per matrici 2×2 e il calcolo per riduzione delle matrici di dimensione superiore. Iniziamo scrivendo l’operazione per quelle 2×2:

Per calcolare gli altri determinanti procederemo invece con:

In particolare con (1-2*(c%2)) calcoliamo il segno per ogni elemento della prima riga. In particolare ricordiamo che gli elementi saranno calcolati in ordine da 0, 1, 2, 3, 4 ecc. Se calcoliamo il resto per ognuno di essi avremo 0, 1, 0, 1, 0 ecc. Eseguendo la suddetta operazione avremo quindi 1-0, 1-2, 1-0, 1-2, 1-0 ecc. Questo ci darà i segni come 1, -1, 1, -1, 1 ecc.

A questo punto ci manca solo un metodo che ci permetta di creare nuove matrici per calcolare i vari determinanti per x, y, z ecc. Ricordiamoci che i vari risultati saranno dati da:

x=\frac{\mbox{D}_x}{\mbox{D}}=\frac{12}{-12}=-1\\ \\ \\ y=\frac{\mbox{D}_y}{\mbox{D}}=\frac{-24}{-12}=2\\ \\ \\ z=\frac{\mbox{D}_z}{\mbox{D}}=\frac{-12}{-12}=1

Dobbiamo fare attenzione ad un dettaglio importante. In Python le liste vengono passate per riferimento, questo vuol dire che modificando ogni lista “copiata” si modifica in realtà la lista originale all’indirizzo di memoria. Per copiare una matrice multidimensionale è necessario quindi copiare i singoli valori nella nuova matrice, nella maniera seguente darebbe errore:

Quindi procediamo in questo modo:

La nostra funzione di sostituzione sostituirà quindi i termini noti nella colonna preselezionata.

A questo punto possiamo scrivere il metodo che calcolerà la soluzione, alla maniera seguente:

Infine implementiamo il metodo solve aggiungendo un paio di chiamate di errore, nel caso in cui la matrice non sia adatta.

Nel suo complesso la classe che avremo creato sarà la seguente:

Per utilizzarla sarà sufficiente scrivere:

Se abbiamo fatto tutto correttamente il risultato che otterremo sarà: [-1.0, 2.0, 1.0]

Vedi articolo

[python] Esercizio su utilizzo di socket e database

Proviamo a realizzare questo semplice esercizio: vorrei avere un server ed un client che possano comunicare tramite socket, in modo tale che il client possa richiedere al server dei dati, il server preleverà tali dati da un database MySQL e li invierà al client.

Lo schema dell’esercizio è approssimativamente questo:

Per svolgere l’esercizio utilizzerò un database con una tabella clienti costruita nel modo seguente:

In aggiunta utilizzerò una classe MySQLdb personalizzata, sviluppata nel modo seguente e messa nel file database.py:

La cartella dell’intero progetto sarà organizzata nella maniera seguente:

client.py
librerie
└── database.py
└── __init__.py
server.py

Fatte queste premesse andiamo anzitutto a creare il nostro file server.py. Nel codice ho inserito i commenti ai vari passaggi:

Adesso è il momento del client.py.

I risultati che dovremmo vedere sono rispettivamente:

1. Per il server vedo quando è stato avviato, da dove e da quale porta

2. Sul client vedo l’elenco presente sul database.

Vedi articolo

[python] Esercizio su funzioni ricorsive e calcolo tratte dei treni

Facciamo un piccolo programma in Python che ci permetta di gestire le distanze da percorrere tra due stazioni, di partenza ed arrivo.

Abbiamo le seguenti tratte:

Stazione A Stazione B Distanza
Firenze Bologna 100km
Firenze Roma 250km
Roma Napoli 200km
Bologna Milano 220km
Bologna Venezia 150km

Ogni tratta è percorribile sia in andata che in ritorno. Quello che vogliamo è che il programma ci permetta di inserire due città e calcolare la distanza minima da percorrere e le stazioni da attraversare.

Anzitutto vediamo come sono disposti i nodi dell’intero percorso:

Notiamo che in questa configurazione elementare solo Bologna ha 3 rami, mentre tutte le altre città hanno solo 2 rami ciascuna.

Potremmo affrontare l’esercizio lavorando sui nodi oppure sulle tratte. In questa soluzione lavorerò sulle tratte.

Cominciamo quindi creando anzitutto una classe che ci permetta di descrivere ogni tratta come abbiamo visto nel mandato dell’esercizio.

In questo modo dichiariamo 3 variabili private per registrare le due città della tratta e la rispettiva distanza.

Adesso registriamo tutte le tratte in una lista, nel modo seguente:

Ora cominciamo a pensare all’algoritmo che potrebbe permetterci di calcolare il percorso.

Immaginiamo anzitutto la soluzione più semplice, dove io penso di andare da Firenze a Napoli. Su questa tratta non ci sono diramazione e sostanzialmente il percorso che dovrà venire fuori sarà Firenze – Roma – Napoli.

Fase 1:

Faccio un ciclo su ogni elemento della lista tratte[] e cerco anzitutto dove è presente la città di partenza. Siccome la città può essere sia in A che in B, per ogni oggetto Tratta dovrò implementare un metodo all’interno dell’oggetto stesso che mi permetta di valutare se la città sia presente in modo comodo. Implementiamo quindi la classe nel modo seguente:

Il metodo presente(citta) mi permette di valutare se la città sia presente nella tratta.

Fase 2:

Se trovo la città di partenza su una tratta allora controllo se l’altra città della tratta sia quella di arrivo. Allo stesso tempo registro la città di partenza all’interno di una lista percorso[] in modo da metterla come partenza del percorso complessivo.

Quindi se l’altra città è quella di arrivo posso chiudere il percorso, altrimenti passo il controllo sull’altra città.

Quando mi trovo nella riga 10 capisco anche che ho trovato la fine del percorso, quindi posso salvare l’intero percorso da qualche parte. Siccome potrei avere molteplici percorsi possibili decido di salvare il percorso in una lista globale chiamata percorsi = []

Modifichiamo quindi il codice nel modo seguente:

Adesso analizziamo due aspetti dell’ultima istruzione, quella dove richiamo la funzione.

Anzitutto voglio tirare fuori dalla tratta l’altra città, rispetto alla città di partenza. Per farlo implemento la classe principale nel modo seguente:

In questo modo quando mi trovo per esempio sulla tratta Firenze – Roma posso passare all’oggetto tratta Firenze, che conosco essendo il punto di partenza e chiedergli di darmi l’altra città della tratta, in questo caso Roma.

Il secondo aspetto che voglio evidenziare è che passo la lista percorso[] alla funzione medesima in partenza dall’altra città, per farlo utilizzo l’istruzione []+percorso, in caso contrario percorso passerebbe per riferimento e qualora fosse passato su più rami verrebbe elaborato contemporaneamente da più rami. Io invece voglio che resti un oggetto singolo e lineare per ogni percorso.

Arrivati a questo punto del codice la situazione è la seguente:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. LOOP INFINITO!

Fase 3:

Devo evitare il loop infinito in cui il percorso possa tornare indietro. Per farlo modifico la mia funzione aggiungendo il seguente controllo all’inizio:

In questo modo controllo che il punto di partenza DA non sia già presente nel percorso[].

Adesso ricomincio a controllare il mio algoritmo da capo:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  11. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  12. Torno al punto 9
  13. In posizione 3 trovo Bologna – Milano dentro tratte[] dove appartiene il mio DA
  14. Questo pezzo di codice adesso si ripete uguale a quello tra 10 e 12 fino a chiudersi su Milano e Venezia che terminano il percorso
  15. Trono al punto 3
  16. In posizione 1 trovo la tratta Firenze – Roma a cui DA (Firenze) appartiene
  17. Controllo se A (Napoli) appartiene alla tratta
  18. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Roma e la passo come nuovo DA alla funzione medesima
  19. La funzione ricomincia e aggiungendo DA (Roma) al percorso[]
  20. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  21. Trovo che DA nella posizione 1 sulla tratta Firenze – Roma
  22. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  23. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  24. Torno al punto 20
  25. Trovo che DA nella posizione 2 sulla tratta Roma – Napoli
  26. Controllo se A (Napoli) appartiene alla tratta
  27. Napoli appartiene alla tratta nel pezzo di codice if t.presente(a)
  28. A questo punto aggiungo A (Napoli) alla fine di percorso[]
  29. Aggiungo il percorso[] ai percorsi[] con l’istruzione percorsi.append(percorso)

Fase 4:

Apporto ancora un paio di correzioni tecniche alla mia funzione per evitare inutili duplicati.

A questo punto posso scrivere la parte principale del mio programma con:

Per stampare il percorso faccio una join su ogni percorso che trovo dentro a percorsi[]

Fase 5:

Aggiungo soltanto un metodo per calcolare le distanze. Potrei farlo anche in modi più ottimizzato, ma per le finalità di questo esercizio ci accontentiamo di percorrere tutte le stazioni, esclusa l’ultima, e di calcolare la distanza tra la stazione corrente e la successiva sommandole tutte insieme.

A tale proposito aggiunto un metodo che mi permetta di valutare se 2 città appartengono entrambe alla tratta ed un getter per la distanza.

La funzione quindi sarà:

Fatto tutto questo posso completare il mio programma nella sua versione finale nel modo seguente:

Se volessimo complicare un po’ lo schema potremmo aggiungere altre tratte:

Ed ottenere una versione finale del programma in questo modo:

Il nostro nuovo programma genererà un output come questo:

Vedi articolo