Informatica generale

J

+ + ⋯ + =

, , ,

Nell'algebra lineare, il rango/caratteristica di una matrice A è il massimo numero di colonne (o righe)

linearmente indipendenti in A.

Il modo più semplice per calcolare il rango di una matrice A è dato dall'algoritmo di Gauss. L'algoritmo

trasforma la matrice in una matrice a gradini con lo stesso rango, dato dal numero di righe non nulle, o

equivalentemente di pivot.

L'algoritmo di Gauss, attraverso l'applicazione di operazioni elementari sulle righe dette mosse di Gauss,

riduce la matrice in una forma detta a gradini.

Le mosse di Gauss sono operazioni che modificano una matrice in uno dei modi seguenti:

scambiando due righe

Ø moltiplicando una riga per un numero diverso da zero

Ø sommando una riga ad un multiplo di un'altra riga

Ø

L’algoritmo si applica nel seguente modo :

1. Se la prima riga (riga «0») ha il primo elemento nullo, scambiala con una riga che ha il primo

elemento non nullo. Se tutte le righe hanno il primo elemento nullo, passa al punto 3

2. Per ogni riga (eccetto la prima i > 0) cerca il primo elemento non nullo (colonna k),

à

.

moltiplica la prima riga per un coefficiente scelto in maniera tale che la somma tra la prima riga

56 !,#

e abbia l’elemento k-esimo nullo (coefficiente = ) . Sostituisci con la somma appena

. .

6 $,#

ricavata

3. Adesso sulla prima colonna tutte le cifre, eccetto forse la prima, sono nulle. A questo punto

ritorna al punto 1 considerando la sottomatrice che ottieni cancellando la prima riga e la prima

colonna

Fra le matrici, occupano un posto rilevante le matrici quadrate (le matrici n*n), le quali hanno la

caratteristica di originare un’altra matrice quadrata se moltiplicate fra di loro

L’elemento neutro della moltiplicazione di matrici quadrate è la matrice identica d’ordine n :

1 0…0

0 1…0

= P R

# …

0 0…1

In algebra lineare, il determinante è una funzione che associa ad ogni matrice quadrata A uno scalare che

ne sintetizza alcune proprietà algebriche.

Il significato geometrico principale si ottiene interpretando la matrice quadrata A di ordine n come

trasformazione lineare di uno spazio vettoriale a n dimensioni: il valore assoluto di det(A) è il fattore con cui

vengono modificati i volumi degli oggetti contenuti nello spazio.

Se è diverso da zero, il segno del determinante indica inoltre se la trasformazione A preserva o cambia

l'orientazione dello spazio rispetto agli assi di riferimento.

Per calcolare il determinante utilizzo :

Sviluppo di Laplace

Ø

Esempio :

Scrivere un programma che :

Legga una matrice

v Stampi a video una matrice

v Scambi due righe di una matrice

v Scambi due colonne di una matrice

v Sommi due righe di una matrice dopo averne moltiplicata una per uno scalare

v

#define NR 50

#define NC 50

#include<stdio.h>

void leggi_matrice(int mat[][NC],int ,int );

void stampa_matrice(int mat[][NC],int , int );

void scambia_righe_matrice(mat[][NC],int ,int ,int ,int );

void scambia_colonne_matrice(mat[][NC],int ,int ,int ,int );

void somma_moltiplica_matrice(int mat[][NC],int ,int ,int ,int ,float );

int main(){

int r=3, c=3;

float fattore=10; NC e NR sono costanti, non variabili. Non posso scrivere mat[n][m] e

à

int mat[NR][NC]; chiedere all’utente quanto siano n e m

leggi_matrice(mat,r,c);

stampa_matrice(mat,r,c);

scambia_righe_matrice(mat,1,2,r,c);

printf("Righe scambiate :\n");

stampa_matrice(mat,r,c);

scambia_colonne_matrice(mat,1,2,r,c);

printf("Colonne scambiate :\n");

stampa_matrice(mat,r,c);

somma_moltiplica_righe_matrice(mat,1,2,r,c);

stampa_matrice(mat,r,c);

} scrivendo [ ][NC] gli dico quanto è grande

à

void leggi_matrice(int mat[][NC],int nr,int nc){ la colonna, per poter scrivere nella

matrice mat[i][j]

int i, j;

for(i=0; i<nr; i++)

for(j=0; j<nc; j++){

printf("Elemento %d %d : ",i,j);

scanf("%d",&mat[i][j]);

}

}

void stampa_matrice(int mat[][NC],int nr, int nc){

int i, j;

for(i=0; i<nr; i++)

for(j=0; j<nc; j++){

printf("%d\t",mat[i][j]);

scanf("%d",&mat[i][j]);

}

}

void scambia_righe_matrice(mat[][NC],int r1,int r2,int nr,int nc){

int i, itmp;

for(i=0; i<nc; i++){

itmp=mat[r1][i];

mat[r1][i]=mat[r2][i];

mat[r2][i]=itmp;

}

}

void scambia_colonne_matrice(mat[][NC],int c1,int c2,int nr,int nc){

int i, itmp;

for(i=0; i<nr; i++){

itmp=mat[i][c1];

mat[i][c1]=mat[i][c2];

mat[i][c2]=itmp;

}

}

void somma_moltiplica_righe_matrice(int mat[][NC],int r1,int r2,int t,int s,float

fattore){

int i;

for(i=0; i<nc; i++){

mat[t][i] += fattore*mat[s][i];

}

}

Matrici e puntatori

Un array a due indici occupa in memoria 4 x 7 posizioni contigue lo si può considerare come un

à

a[4][7]

array unidimensionale di lunghezza 28

L’ordine nella memoria degli elementi dell’array segue la regola per cui l’indice più a sinistra di un array

multidimensionale cresce più lentamente questo comportamento è simile a come si muovono le cifre

à

del contachilometri di un’automobile

à à à à

a[0][0] a[0][1] a[0][2] a[0][3] …

Tuttavia possiamo considerare la dichiarazione di un array bidimensionale dal punto di vista della priorità

dell’operatore [ ], che compare due volte ed è valutato come sempre da sinistra a destra

Possiamo pensare quindi all’array come a un array di 4 elementi a [4] ogni elemento è un array

à

a[4][7]

di 7 elementi

Quindi oppure è un puntatore al primo elemento dell’array bidimensionale primo sottoarray di

à

a a[0]

lunghezza 7

oppure è un puntatore al secondo elemento dell’array bidimensionale secondo sottoarray di

à

a+1 a[1]

lunghezza 7 e così via…

*(a+1) non è un elemento dell’array ma è ancora un puntatore indirizzo del secondo sottoarray

à à

*(a+1)+1 ancora un puntatore indirizzo del secondo elemento del secondo sottoarray

à à

*(*a+1) primo elemento del secondo sottoarray a[1][0]

à à

Esempio :

double a[4][7];

à à à à à

a[0][0] a[0][1] a[0][2] a[0][3] … a[0][6]

oppure

a[0] a

à à à à à

a[1][0] a[1][1] a[1][2] a[1][3] … a[1][6]

a[1]

à à à à à

a[2][0] a[2][1] a[2][2] a[2][3] … a[2][6]

a[2]

à à à à à

a[3][0] a[3][1] a[3][2] a[3][3] … a[3][6]

a[3]

Come facciamo quindi a percorrere un array multidimensionale con un puntatore?

Dobbiamo rendere esplicito il punto di partenza, cioè usare &a[0][0] oppure *a (non a) come indirizzo

iniziale, e poi tenere conto della mappa di memoria, cioè del fatto che l’indice più a destra varia più

velocemente, quindi il secondo più a destra e così via.

Il codice che segue spiega quale algoritmo occore seguire

Esempio :

double a[4][7]; à

*(&a[0][0] + 1) = 3.14; a[0][1] = 3.14

à

*(&a[0][0] + 7) = 6.28; a[1][0] = 6.28

à

*(&a[0][0] + 7 + 1) = 2.73; a[1][1] = 2.73

Oppure… à

*(*a + 1) = 3.14; a[0][1] = 3.14

à

*(*(a + 1)) = 6.28; a[1][0] = 6.28

à

*(*(a + 1) + 1) = 2.73; a[1][1] = 2.73

In generale, avendo dichiarato un array multidimensionale possiamo dereferenziare un suo

a[N1][N2]

elemento scrivendo

a[i][j] *(&a[0][0] + N2*i + j)

oppure

*(*(a + i) + j)

Per poter conservare dati anche dopo l’esecuzione di un programma, è necessario renderli persistenti

ovvero archiviarli su memoria di massa.

Un file è una sequenza di registrazioni uniformi (dello stesso tipo), di dimensioni potenzialmente illimitate

(la sua dimensione dipende esclusivamente dal disco rigido), ed è ad accesso sequenziale. Allegoricamente

un file è un libro.

A livello di sistema operativo, un file è denotato univocamente dal suo nome assoluto, che comprende il

percorso e il nome relativo.

Per agire su un file dall’interno di un programma occorre stabilire una corrispondenza fra:

il nome del file come risulta al sistema operativo

Ø un nome di variabile definito nel programma

Ø

Questa operazione appartiene al modello di coordinazione e si chiama apertura di un file.

La corrispondenza può essere distrutta mediante l’operazione di chiusura del file.

Libro si apre Operazioni di lettura o scrittura sul libro Libro si chiude

à à

Il modello di coordinazione della Standard I/O Library è basato sul concetto di file che vede come

stream di byte.

In particolare, i tre stream:

standard input (stdin);

Ø standard output (stdout);

Ø standard error (stderr)

Ø

corrispondono a file già aperti.

Per gestire la corrispondenza fra il nome del file e una variabile del programma che rappresenta

uno stream, la Standard I/O Library definisce il tipo FILE.

Il tipo FILE è una struttura definita nella libreria stdio.h, che rimane trasparente all’utente e che spesso

cambia da un compilatore all’altro. Le strutture di

tipo FILE non sono mai gestite direttamente dall’utente, ma solo ed esclusivamente dalle funzioni della

Standard I/O Library. Nei suoi programmi, l’utente dovrà solo definire, ove necessario, dei puntatori a FILE :

FILE* f; FILE *fid; dichiaro il puntatore a file

à

fid = fopen( “nome del file”, “modalità di apertura” ); stdio.h dichiara la funzione fopen() per

à aprire un file

if( fid == NULL ) { mi controlla il risultato di fopen()

à

printf( “File non trovato” );

exit( 0 ); contenuta in stdlib.h, mi evita errori di memoria e fa terminare il

à

programma, restituendo al sistema operativo un codice di errore

Il valore restituito da fopen() è un puntatore a FILE, da usare in tutte le successive operazioni sul file. Tale

puntatore è NULL in caso di fallimento

Nell’aprire un file inserisco il nome del file completo Esempio : per un file di testo di una

à “matrice.txt”

matrice

Nell’aprire un file devo dichiarare una modalità di apertura :

“r” read, apertura di un file di testo in lettura

Ø à