Informatica - Appunti

La ricerca binaria

Bisogna quindi stare attenti a scrivere bene il programma perché non finisca in un ciclo infinito, ma se scritto bene evita molte righe di codice.

ESEMPIO

Proviamo a scrivere in questo modo un programma di ricerca binaria.

Base:

Dobbiamo come sempre prima definire una base, ossia deve rispecchiare il dato più semplice che ci possa capitare, ossia avere un intervallo minore o uguale di 2: se il mio intervallo ha lunghezza minore o uguale a 2, scelgo l'elemento cercato.

L'induzione prende il punto medio dell'intervallo e chiama la ricerca binaria ricorsiva sulla metà giusta.

Vediamo ora come scriverla in Fortran 90.

RECURSIVE FUNCTION RBINSEARCH (N, II, V) RESULT (POS)
IMPLICIT NONE
INTEGER, INTENT (IN):: N, II, V(N)
INTEGER:: POS
INTEGER:: IMID, NNEW, TMPPOS

POS=0

IF (N.LE.2) THEN
    IF (V(1).EQ.II) THEN
        POS=1
        RETURN
    END IF
    IF (N.EQ.2) THEN
        IF (V(2).EQ.II)THEN
            POS=2
            RETURN
        END IF
    END IF
ELSE
    !Induzione
    IMID= (N+1)/2
    IF (V(IMID).GT.II) THEN
        !Cerca nella metà
    

questo punto però mi troverei la posizione relativa a II nella seconda metà dell'intervallo, il quale però ha posizione 1 a IMID che non è la stessa dell'intervallo iniziale. Perciò devo aggiornare la posizione aggiungendo la metà dell'intervallo di cui non avevo tenuto conto.

POS=TMPPOS+IMID-1

SCRIVERE IN MANIERA RICORSIVA LA BUBBLE SORT

Devo ordinare il mio intervallo in maniera crescente o decrescente portando il valore minore (o maggiore) in cima. Perciò avrà una base secondo cui se la lunghezza del vettore è 1 esci.

L'induzione ci dice di portare l'elemento più piccolo in testa e chiamare BSORT sulla parte rimanente del vettore.

RECURSIVE SUBROUTINE RBSORT (N,VI)

IMPLICIT NONE

INTEGER, INTENT (IN) :: N

INTEGER, INTENT (INOUT):: VI(N)

INTEGER:: II

IF (N.EQ.1) THEN

!Base

RETURN

ELSE

!Ricorsione

!Porto l'elemento più piccolo in testa

Devo confrontare tutti gli elementi dal 2 all'ultimo con il

primo e qualora fosse più piccolo faccio uno scambio:

DO I=2,N
    IF (VI(I).LT.VI(I-1)) CALL SWAPI(VI(I), VI(I-1))
END DO
CALL RBSORT (N-1, VI(2:N))
ENDIF

END DO

SUBROUTINE RBSORT allocate staticamente:
Finora tutte le variabili che abbiamo considerato erano ossia al momento dell'inizializzazione il calcolatore sapeva esattamente la memoria necessaria alla memorizzazione della variabile.

DIMENSIONAMENTO DINAMICO DI VARIABILI ALL'INTERNO DELLA SUBROUTINE
Il compilatore crea un programma eseguibile che si riserva la quantità di memoria che gli serve dinamicamente: quando inizia l'esecuzione del main occupa una certa quantità di memoria. Nel momento in cui iniziamo l'esecuzione di una subroutine occupa un'altra sezione di memoria, quando si termina questa esecuzione questa parte di memoria viene liberata.

Istante dopo istante la quantità di memoria che il calcolatore occupa varia.

In realtà noi come utenti possiamo intervenire per decidere quando chiedere

1. memoria equando liberarla: questo viene fatto con le variabili allocabili: sono variabili la cui dimensione viene decisa dinamicamente durante l'esecuzione.
2. Vanno dichiarate esattamente come le variabili normali se non che:
• INTEGER, ALLOCATABLE:: NOME (:) – (:) è un vettore allocabile
• INTEGER, ALLOCATABLE:: NOME (:,:) – (:,:) è una matrice allocabile
3. L'unica limitazione che abbiamo è dire quante dimensioni hanno, dobbiamo specificare il rango.
4. Al momento dell'inizializzazione del codice non occupano memoria, per chiedere memoria dobbiamo usare il comando ALLOCATE (NOME(10), MATRICE (5,5), STAT= INFO).
5. È molto importante controllare lo stato dell'allocazione, perché può essere che il calcolatore non abbia memoria da concederci.
• Se l'allocazione va a buon fine allora INFO=0.
• Se non c'è abbastanza spazio per allocare tutte le variabili allora INFO è diverso da 0.
6. Mettiamo quindi un controllo:

IF (INFO.NE.0) THEN
    WRITE (*,*) 'Errore'

allocazione'END IF

Quando abbiamo finito di usare queste due variabili è buona norma liberare la memoria che esse occupano tramite il comando:

DEALLOCATE (NOME, MATRICE, STAT=INFO)

Anche qui possiamo fare un controllo dello stato di memoria dopo la deallocazione. Non dovrebbero esserci problemi perché stiamo liberando memoria, in realtà serve più a controllare se abbiamo sbagliato durante l'esecuzione a scrivere le variabili scrivendo fuori dallo spazio che avevamo assegnato.

ESEMPIOSupponiamo di fare un programma principale per fare un prodotto matrice vettore.

PROGRAM MAIN

IMPLICIT NONE

INTEGER:: N, INFO, I, J

REAL (KIND=8), ALLOCATABLE :: A(::), V(:), W(:), Z(:), T1, T2

OPEN (1,FILE= 'dati.dat')

READ (1,*) N

ALLOCATE (A(N,N), V(N), W(N), Z(N), T1(N), T2(N), STAT=INFO)

IF (INFO.NE.0) STOP

DO I=1,N

READ (1,*) (A(I,J),J=1,N)

END DO

READ (1,*) (V(I), I=1,N)

READ (1,*) (W(I), I=1,N)

CALL MATVET (N, N, A, N ,T1)

SUBROUTINE MATVET (N, NMAX, MAT, X, Y)

IMPLICIT NONE

INTEGER,

INTENT (IN):: N, NMAXREAL (KIND=8), 
INTENT (IN):: MAT(NMAX,N), X(N)REAL (KIND=8), 
INTENT (OUT):: Y(N)

DO I=1,N
    Y(I)=0.0
    DO J=1,N
        Y(I)= Y(I)+ MAT(I,J)*X(J)
    END DO
END DO

END SUBROUTINE MAT VET

CALL MATVET (N, N, A, W, T2)

DO I=1,N
    Z(I)= T1(I)+ T2(I)
END DO

WRITE (*,*) (Z(I), I=1,N)

DEALLOCATE (A, V, W, Z, T1, T2, STAT=INFO)

IF (INFO.NE.0)
END PROGRAM MAIN

In realtà si poteva dichiare un solo vettore temporaneo perchè potevo mettere il primo
prodotto direttamente in z e fare
Z= Z+T2

Possono esserci dei casi in cui la subroutine ha bisogno di una variabile interna, in questo
caso è possibile allocarlo internamente e disallocarlo prima di uscire dalla subroutine.

TIPI DI DATI DERIVATI
Finora abbiamo visto solo le variaili predefinite, standard che sono i soliti:
- Reali
- Interi
- Caratteri
- Variabili logiche

Ci sono poi dei tipi speciali che possono essere definiti dall'utente: degli oggetti che
servono a noi e che il linguaggio di programmazione non ha previsto. é

più comodo rappresentare dati complessi con tipologie che definiamo noi.

Il tipo derivato è sostanzialmente una macrovariabile che si compone di più tipi predefiniti.

La sintassi fortran è TYPE NOME_TIPO_DERIVATO. Dichiaro una serie di tipi predefiniti.

END TYPE NOME_TIPO_DERIVATO

Questa è la definizione del tipo derivato.

Poi dovrò utilizzare variabili del tipo derivato, dovrò definirle in questo modo:

TYPE (NOME_TIPO_DERIVATO) :: NOME VARIABILE

ESEMPIO

Definisco una variabile di tipo punto: è un insieme di due coordinate x e y quindi deve riservare spazio per ciascuna coordinata vista come l'insieme di due numeri reali.

TYPE PUNTO2D
REAL (KIND=8):: X
REAL (KIND=8):: Y
END TYPE

Con un'unica variabile riesco a contenere le informazioni dovute ad un'unica variabile.

Nel main questo lo richiamerò come:

TYPE (PUNTO2D):: P1,P2,P3

Ora proviamo a creare un programma che renda necessario l'utilizzo di questi punti in cui io leggo

le coordinate e calcolo il punto p3 come punto medio tra i due punti.

Per accedere alla coordinata x di p1 devo fare:

P1%X= 0.0

P1%Y=1.0

P2%X=2.0

P2%Y=2.0

Voglio calcolare la posizione del punto medio: devo calcolare le coordinate x e y di P3

P3%X=0.5*(P1%X+P2%X)

P3%Y=0.5*(P1%Y+P2%Y)

Si usano tipi derivati se determinati tipi di variabili sono usati molto spesso.

In questo caso è utile scrivere una function che utilizzi tipi derivati:

FUNCTION PMEDIO (PA, PB) RESULT (PM)

IMPLICIT NONE

Devo come prima cosa definire il tipo derivato anche all'interno della function:

TYPE PUNTO2D

REAL (KIND=8):: X

REAL (KIND=8):: Y

END TYPE

In questo caso abbiamo definito due volte la stessa cosa, non siamo obbligati ad usare gli stessi nomi. Sulla subroutine possiamo usare nomi diversi, l'importanza è che ci sia coerenza tra i tipi.

TYPE (PUNTO2D), INTENT (IN):: PA, PB

TYPE (PUNTO2D) PM

PM%X=0.5*(PA%X+PB%X)

PM%Y=0.5*(PA%X+PB%Y)

END FUNCTION PMEDIO

Se io dispongo di questa function posso richiamarla

direttamente e scrivere:PM=PMEDIO (P1,P2)

Se devo fare un programma che manipola la geometria mi conviene creare dei tipi derivati delle function che ci aiutino a manipolare delle tipologie geometriche in modo da fare un programma più facile da leggere e da gestire. L'inconveniente di questo tipo è dover sempre ripetere la definizione di un tipo derivato.

MODULI: i moduli sono raccoglitori che ci permettono si raggruppare definizioni di:

• tipi derivati
• function
• subroutine
• variabili
• parametri

Tutto quello che è stato inserito all'interno del modulo è messo automaticamente a disposizione di tutte le subroutine e le function che lo utilizzano.

Per creare un modulo scriviamo:

      MODULE NOME DEL MODULO
        IMPLICIT NONE
        >Dichiarazione di variabili e/o parametri: queste variabili e questi parametri sono accessibili a tutte le function e tutte le subroutine che utilizzano questo modulo.
        >Definizione tipi derivati
        CONTAINS
        SUBROUTINE
        FUNCTION
      END MODULE NOME MODULO