4) Algoritmi studiati

Algoritmi di base: somma di N numeri, massimo di N numeri, metodo delle divisioni successive per il MCD, inversione delle cifre di un numero intero. Algoritmi con array: compattamento di un array, merging di due array ordinati. Algoritmi di ricerca: ricerca sequenziale, ricerca binaria.  Algoritmi di ordinamento: ordinamento per selezione, ordinamento per scambi, ordinamento per inserzione. Algoritmi di base per l'algebra lineare: trasposta di una matrice, prodotto matrice-vettore, prodotto matrice-matrice, verifica di una matrice a diagonale dominante, risoluzione di un sistema triangolare di ordine N. Algoritmi sull'aritmetica floating point: calcolo dell'epsilon macchina, calcolo della radice quadrata di un numero reale. Algoritmo di Horner per la valutazione di un polinomio (vedi anche la raccolta disponibile sul canale Teams del corso).

ATTIVITA' DI LABORATORIO

 

1) prima consegna (scadenza  10 MARZO 2024)

A)   scrivere una subroutine Fortran per la trasposta di una matrice quadrata di ordine N, con la seguente testata:

SUBROUTINE TRASPMAT(A, N, LD)

A:  matrice di reali (reale, input/output)

N:  ordine della matrice  (intero, input)

LD: leading dimension dell'array (intero, input)

Inserire nella propria cartella nomecognome di Dropbox solo il file traspmat.f90 che contiene la subroutine TRASPMAT ed eventuali altre subroutine da essa richiamate. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

B)  scrivere una subroutine Fortran  per il la fusione di due vettori ordinati (merging), con la seguente testata:

SUBROUTINE MERGING ( A, B, N, M, C)

 

A:  primo vettore ordinato (reale, input)

B: secondo vettore  ordinato (reale, input)

N: lunghezza del primo vettore (intero, input)

M: lunghezza secondo vettore (intero, input)

C: vettore ordinato di lunghezza M+N, risultato dalla fusione di A e B  (reale , output)

Inserire nella propria cartella nomecognome di Dropbox solo il file merging.f90 che contiene la subroutine MERGING ed eventuali altre subroutine da essa richiamate. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

risultati consegna A)                               risultati consegna B)

 

 

 

2) seconda  consegna (scadenza   1 aprile 2024)

 

b)   scrivere una subroutine Fortran per il prodotto "righe per colonne" tra una matrice A di N righe e M colonne e un vettore X di M componenti con la seguente testata:

SUBROUTINE MATVET(A, N, M, LDA, X, Y)

A:  matrice di N righe e M colonne (reale, input)

N:  numero di righe di A (intero, input)

M: numero di colonne di A (intero, input)

LDA: leading dimension di A (intero, input)

X: vettore di lunghezza M (reale, input)

Y: vettore di lunghezza N (reale, output)

Inserire nella propria cartella nomecognome di Dropbox solo il file matvet.f90 che contiene la subroutine MATVET ed eventuali altre subroutine da essa richiamate. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

B)   scrivere una subroutine Fortran per il prodotto "righe per colonne" tra una matrice A di N righe e M colonne e una matrice B di M righe e L colonne con la seguente testata:

SUBROUTINE MATMAT(A, B, C, N, M, L, LDA, LDB, LDC)

A:  matrice di N righe e M colonne (reale, input)

B: matrice di M righe e L colonne (reale, input)

C: matrice risultato (reale, output)

N:  numero di righe di A (intero, input)

M: numero di colonne di A e righe di B (intero, input)

L: numero di colonne di C (intero, input)

LDA: leading dimension di A (intero, input)

LDB: leading dimension di B (intero, input)

LDC: leading dimension di C (intero, input)

Inserire nella propria cartella nomecognome di Dropbox solo il file matmat.f90 che contiene la subroutine MATMAT ed eventuali altre subroutine da essa richiamate. Altri file verranno cancellati.

Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

C) scrivere una subroutine Fortran per la ricerca sequenziale della posizione di un numero in un elenco di reali di lunghezza N , con la seguente testata:

SUBROUTINE RICSEQ(A, N, NUM, POS)

A:  array di reali (input)

N:  lunghezza dell'elenco (intero, input)

NUM: numero di cui si vuole la posizione nell'elenco (reale, input)

POS:  posizione di NUM nell'array A (intero, output). POS vale -1 se il numero non e' presente nell'array

Inserire nella propria cartella nomecognome di Dropbox solo il file ricseq.f90 che contiene solo la subroutine RICSEQ ed eventuali altre subroutine da essa richiamate. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

D)   scrivere una subroutine Fortran per l'ordinamento di un array X di numeri reali mediante ordinamento per scambi  con la seguente testata:

SUBROUTINE ORDSCA (X, N, IT)

X: array  di lunghezza N  (reali, input e output)

N:  lunghezza dell'array (intero, input)

IT: numero di iterazioni effettuate nel ciclo principale  (intero, output.)

Inserire nella propria cartella nomecognome di Dropbox solo il file ordsca.f90 che contiene la subroutine ORDSCA ed eventuali altre subroutine da essa richiamate  . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

E)   scrivere una subroutine Fortran per l'ordinamento di un array X di numeri reali mediante ordinamento per selezione   con la seguente testata:

SUBROUTINE ORDSEL (X, N)

X: array  di lunghezza N  (reali, input e output)

N:  lunghezza dell'array (intero, input)

Inserire nella propria cartella nomecognome di Dropbox solo il file ordsel.f90 che contiene la subroutine ORDSEL ed eventuali altre subroutine da essa richiamate  . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

        F)   scrivere una subroutine Fortran per la ricerca binaria  della posizione di un nome (di al  piu' 10 char)  in un elenco di lunghezza N , con la seguente testata:

         SUBROUTINE RICBIN(A, N, NOME, POS)

          A:  array  di nomi ( character (len=10) , input)

          N:  lunghezza dell'elenco (intero, input)

         NOME: nome  di cui si vuole la posizione nell'elenco (character (LEN=10) , input)

POS:  posizione di NOME  nell'array A (intero, output). POS vale -1 se il nome  non e' presente nell'array

Inserire nella propria cartella nomecognome di Dropbox solo il file ricbin.f90 che contiene solo la subroutine RICBIN ed eventuali altre subroutine da essa richiamate . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

risultati consegna a)         risultati consegna b)                risultati consegna c)            risultati consegna d)             risultati consegna e)           risultati consegna f)

3) terza  consegna (scadenza  xx aprile 2024)

 

 a)   scrivere una function C per l'ordinamento di un array di numeri reali A  di lunghezza N mediante ordinamento per selezione , con la seguente testata:

void ordsel(int N, float  A[ ])

N:  lunghezza dell'elenco (intero, input)

A:  array  di numeri reali ( input)

Inserire nella propria cartella nomecognome di Dropbox solo il file ordsel.c che contiene solo la function ordsel . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

 

b)   scrivere una function C per la ricerca binaria  della posizione di un numero reale  in un array  di lunghezza N , con la seguente testata:

void ricbin(int N, float  A[ ], float  X, int *POS)

N:  lunghezza dell'elenco (intero, input)

A:  array  di numeri reali ( input)

X: numero  di cui si vuole la posizione nell'array (input)

POS:  indirizzo della posizione di X  nell'array A (intero, output).  POS vale -1 se il nome  non e' presente nell'array

Inserire nella propria cartella nomecognome di Dropbox solo il file ricbin.c che contiene solo la function RICBIN . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

c)   scrivere una function C per il prodotto tra due matrici  con la seguente testata:

void matmat(int LDA, int LDB, int LDC, int N, int M, int P, float  A[ ][LDA], float  B[ ][LDB], float C[ ][ LDC])

LDA, LDB, LDC, leading dimension delle matrici A, B, e C (interi, input)

N, M , P:  dimensioni delle matrici A, B, e C (interi, input)

A, B e C  matrici di numeri  reali ( input)

Inserire nella propria cartella nomecognome di Dropbox solo il file matmat.c che contiene solo la function matmat . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

d)    scrivere una function C  per massimo comun divisore con la seguente testata:

int macodi( int A, int B)

 

A, B:  numeri interi non entrambi nulli (interi, input)

 

valore di ritorno: il massimo comun divisore. Il volore di ritorno deve essere -1 se A e B sono entrambi =0 .

Inserire nella propria cartella nomecognome di Dropbox solo il file macodi.c che contiene solo la function macodi . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

 

risultati consegna a)                    risultati consegna b)                    risultati consegna c)                risultati consegna d)                           

 

 

 

4) quarta   consegna (scadenza xx aprile 2024)

a)    scrivere una function C  per il calcolo dell'epsilon macchina, con la seguente testata:

float  epsilon( void )

 

la funzione non ha argomenti e  restituisce l'epsilon macchina

Inserire nella propria cartella nomecognome di Dropbox solo il file epsilon.c che contiene solo la function epsilon . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

b)  scrivere una function C  per verificare se una matrice A di dimensione N e' a diagonale dominante, con la seguente testata:

int   diagdom( int LD, int N, float A[ ][LD] )

 

LD: leading dimension della matrice A (intero input)

N:  ordine della matrice (intero, input)

A:  matrice  dei coefficienti (float, input)

 

la funzione   restituisce

-1  se la matrice e' a diagonale dominante

l'indice i della prima riga per cui la condizione di diagonale dominante non e' verificata

Inserire nella propria cartella nomecognome di Dropbox solo il file diagdom.c che contiene solo la function diagdom ed eventuali altre function da essa richiamate (ad es. quella per il valore assoluto). Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

c)    scrivere una function C  per la risoluzione di un sistema con matrice triangolare inferiore, con la seguente testata:

int  sistri( int LD, int N, float A[ ][LD], float B[ ], float X[ ] )

 

 

LD: leading dimension della matrice A (intero input)

N:  ordine della matrice (intero, input)

A:  matrice  dei coefficienti (float, input)

B: vettore dei termini noti (float, input)

X: vettore soluzione (float, output)

 

la funzione   restituisce

-1  se il sistema emmette soluzione

l'indice i dell'elemento tale che A[i][i] = 0

Inserire nella propria cartella nomecognome di Dropbox solo il file sistri.c che contiene solo la function sistri ed eventuali altre function da essa richiamate. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function.

 

 

 d)  scrivere una function C  per il calcolo della radice quadrata di un numero reale X, con la seguente testata:

float  sqroot( float X )

 

X:  numero reale (float, input)

 

la funzione restituisce

la radice quadrata di X (se X>= 0)

-1  (se X < 0)

Inserire nella propria cartella nomecognome di Dropbox solo il file sqroot.c che contiene la function sqroot ed eventuali altre function da essa richiamate (ad esempio la function  epsilon( ) ) . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

 

 

risultati consegna a)         risultati consegna b)                risultati consegna c)            risultati consegna d) 

 

 

 

3) nessuna  consegna (scadenza xx/xx/xxxx)

a)   scrivere una subroutine Fortran per l'ordinamento di un array X di numeri reali mediante ordinamento per selezione   con la seguente testata:

SUBROUTINE ORDSEL (X, N)

X: array  di lunghezza N  (reali, input e output)

N:  lunghezza dell'array (intero, input)

Inserire nella propria cartella nomecognome di Dropbox solo il file ordsel.f90 che contiene la subroutine ORDSEL ed eventuali altre subroutine da essa richiamate  . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

 

c) scrivere una subroutine Fortran per l'ordinamento di un array X di numeri reali mediante ordinamento per inserzione   con la seguente testata:

SUBROUTINE ORDINS (N, X)

X: array  di lunghezza N  (reali, input e output)

N:  lunghezza dell'array (intero, input)

Inserire nella propria cartella nomecognome di Dropbox solo il file ordins.f90 che contiene la subroutine ORDINS   ed eventuali altre subroutine da essa richiamate  . Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della subroutine

 

c)  scrivere una function C  per il merging di due vettori, con la seguente testata:

void merging( int N, int M, float  A[ ], float B[ ], float C[ ])

 

N, M:  lunghezza dei due vettori (interi, input)

A, B:  vettori  di reali (input)

C, vettore di reali (output)

Inserire nella propria cartella nomecognome di Dropbox solo il file merging.c che contiene solo la function merging ed eventuali altre function da essa richiamata. Altri file verranno cancellati. Assicurarsi della correttezza dei nomi del file e della function

 

 

 

risultati consegna a)         risultati consegna b)                risultati consegna c)            risultati consegna d)             risultati consegna e)           risultati consegna f)

BIBLIOGRAFIA GENERALE
 

[1] H. McGilton, R. Morgan - Il sistema operativo Unix System V - McGraw Hill, 1987. (Cap. 1, 2, 3, 7)

[2] M. Metcalf, J. Reid - Fortran 95 - Oxford science publ.

[3] B. Kerninghan, D. Ritchie - Il linguaggio C - Pearson ed.

[3] A. Murli - Approccio Computazionale nella Risoluzione di un Problema: Alcune Sorgenti di Errore - Rapporto Tecnico del Centro di Ricerche sul Calcolo Parallelo e i Supercalcolatori, TR-96-18, dicembre 1996. puoi trovarlo qui

[4] G.Giunta, G.Laccetti, A.Murli R.Rizzardi - Laboratorio di programmazione 1 - Liguori ed.

SLIDE (2019)

• Introduzione al corso
• la macchina di von neumann
• la rappresentazione dati (1)
• la rappresentazione dati (2)
• la rappresntazione delle istruzioni
• i sistemi operativi
• variabili e costanti
• strutture di controllo (1)
• variabili strutturate (array)
• strutture di controllo (2)
• le procedure
• la complessita' computazionale
• gli errori di round-off
• Introduzione al  sistema operativo Linux
• introduzione al linguaggio Fortran
• introduzione al linguaggio C

UNA COLLEZIONE DI ALGORITMI STUDIATI A LEZIONE QUI

UN ESEMPIO DI ALGORITMO ASSEGNATO DURANTE UNA PROVA SCRITTA  QUI

COME FARE PER L'ATTIVITA' DI LABORATORIO E PREPARARE LE CONSEGNE?

Parte del corso prevede la conoscenza e l'utilizzo del sistema operativo Linux. E' possibile fare attivita' di laboratorio e preparare le consegne in differenti modi:

1) Chi possiede un calcolatore con il sistema operativo Linux puo' tranquillamente utilizzare tale strumento, eventualmente installando il software Dropbox per le consegne (vedi dopo) e i pacchetti Numpy e Scipy.

2) Per chi possiede un computer con altro sistema operativo e' possibile creare, con l'aiuto di una persona esperta, una "seconda partizione" in cui installare il sistema operativo Linux. Tale soluzione permette di scegliere quale sistema operativo eseguire al momento dell'accensione della macchina. Si segnala che l'operazione di creazione di una seconda partizione all'interno del proprio computer e' particolarmente delicata e con un elevato rischio di perdere le informazioni presenti in esso.

3) Per chi possiede un computer con sistema operativo Windows o Mac OS, un strumento alternativo a quello descritto nel punto 2, e' rappresentato da un ambiente software che replica l'ambiente Linux disponibile nel  laboratorio didattico. Questa soluzione non altera la configurazione del proprio computer e non presenta i rischi descritti nel punto 2. In tale ambiente sono gia' presenti tutti gli strumenti software necessari al corso (compilatori e servizio Dropbox per le consegne). L'ambiente software da installare e' chiamata "macchina  virtuale", ed e' composta da due elementi:

• il supervisore, anche detto Virtual Machine player  (in pratica una interfaccia software tra il proprio sistema operativo Windows o McOs e il sistema operativo Linux)

• il sistema operativo Linux da installare nel supervisore

 passi per installare il Supervisore (sistema operativo Windows 64 bit. Es.: Windows 8 oppure 10)

·        A) Scaricare gratuitamente il supervisore ( VMware Workstation Player ) da http://www.vmware.com/go/downloadplayer/, selezionando il sistema operativo WIndows 64 bit

·         B) eseguire il  VMware Player’s Installer (doppio click sul file scaricato)

·         C) proseguire con l'installazione accetando le condizioni d'uso e proseguendo sempre con   Next.

 passi per installare il sistema Linux sul Supervisore (sistema operativo Windows 64 bit. Es.: Windows 8 oppure 10)

·        A) Scaricare gratuitamente  la macchina virtuale  wpage.unina.it/lapegna/educational/LABPROG/LabProgMachine.rar  Il file ha dimensioni maggiori di   1GB  e puo' richiedere qualche minuto a secondo della velocita' di connessione

·         B) Decomprimere il file (ad esempio sul Desktop). Risultera' disponibile una cartella di nome Lab Prog Machine 2020

·        C) Eseguire il supervisore  VMware Player (ad es. doppio click sul collegamento presente su desktop).  Se richiesti, accettare i termini di utilizzo e selezionare l'uso privato del prodotto.

·         D) Nella finestra di VMware Player selezionare Open a Virtual Machine, e accedere alla cartella Lab Prog Machine 2020  ottenuta precedentemente

·         E) Selzionare il file Lab Prog Machine 2020 e poi Apri.

·         F) Nella finestra principale del supervisore selezionare Play Virtual Machine (Ignorare eventuali richieste di installazione di altro software). Aspettare qualche istante (circa 30 sec) e immettere user come password dell'utente mostrato

 Dopo la prima installazione, le volte successive sara' sufficiente eseguire solo il passo F).

 passi per installare il Supervisore (sistema operativo McOS)

·        A) Scaricare gratuitamente il supervisore ( VirtualBox ) da https://www.virtualbox.org/wiki/Downloads selezionando il sistema operativo OS X host

·         B) eseguire il il programma di installazione (doppio click sul file scaricato)

·         C) proseguire con l'installazione accetando le condizioni d'uso e proseguendo sempre con   Next.

 passi per installare il sistema Linux sul Supervisore (sistema operativoMacOS)

·        A) Scaricare gratuitamente  la macchina virtuale  wpage.unina.it/lapegna/educational/LABPROG/LabProgMachine.rar  Il file ha dimensioni maggiori di   1GB  e puo' richiedere qualche minuto a secondo della velocita' di connessione

·         B) Decomprimere il file (ad esempio sul Desktop). Risultera' disponibile una cartella di nome Lab Prog Machine 2020

·        C) Eseguire il supervisore  VM VirtualBox (ad es. doppio click sul collegamento presente su desktop).  Se richiesti, accettare i termini di utilizzo e selezionare l'uso privato del prodotto.

·         D) Nella finestra di del Supervisore selezionare Nuova. Nella finestra seguente inserire come Nome "Lab Prog Machine 2020", Tipo del S.O. "Linux" e versione "Ubuntu 64bit". Selezionare "Non aggiungere disco fisso virtuale" (importante). Quindi selezionare: Crea

·         E) Nella finestra seguente, selezionare tra le impostazioni della macchina virtuale ottenuta, la sezione Archiviazione. Selezionare il'icona "aggiungi disco fisso" al controller SATA. Nella finestra ottenuta selezionare l'icona aggiungi e selezionare il file Lab Prog Machine 2020 nella cartella Lab Prog Machine 2020 ottenuta al passo B.

·         F) Nella finestra principale del supervisore selezionare Avvia. Aspettare qualche istante (circa 30 sec) e immettere user come password dell'utente mostrato

 Dopo la prima installazione, le volte successive sara' sufficiente eseguire solo il passo F).

4) Chi possiede un calcolatore troppo vecchio, per cui le soluzioni precedenti non funzionano puo' utilizzare numerose piattaforme online che realizzano un sistema Linux virtuale in cui sviluppare i programmi. Tali ambienti permettono poi differenti modi per salvare il proprio lavoro, o nella stessa piattaforma oppure su sistemi cloud di larga diffusione (ad es. google drive). A solo titolo di esempio si riportano:

·         Codinground all'indirizzo  https://www.tutorialspoint.com/online_c_ide.php

·         Repl all'indirizzo https://repl.it/

·         Codeboard all'indirizzo https://codeboard.io/

Dopo lo sviluppo dell'elaborato e' necessario poi copiarlo in Dropbox per la consegna (vedi dopo).

PER LE CONSEGNE ( IMPORTANTE ! )

Le consegne avverranno,  attraverso il servizio  cloud Dropbox, gia' installato nella macchina virtuale LabProgMachine

operazioni da esegure 1 sola volta !

1)  Se non lo si dispone, crearsi un account Dropbox su  www.dropbox.com e accedere

2)  nel menu a destra cliccare su "Nuova cartella condivisa"  e poi su "Avanti"

3)  dare alla cartella condivisa il nome CognomeNome  ovviamente usando il proprio nome e cognome senza spazi!!

4)  invitare come membro con cui condividere la cartella  marco.lapegna@unina.it

6) Nella macchina virtuale, avviare Dropobox (dalla sezione internet del menu principale) e collegare la macchina virtuale con Dropbox, inserendo  le credenziali  definite al punto 1)