Category Archives: Gallery

Bit di Controllo (o Parità): funzionamento e spiegazione

Esercizio: Ricavare la parola di memoria contenente i bit di controllo (parola di codice) dalla parola a 8 bit 11000110:

Parola di memoria: 11000110

Per parole di 8 bit si utilizzano 4 bit di controllo che andranno a inserirsi nelle posizioni potenze di 2  da 1 fino a 2n-1 dove n equivale al numero di bit di controllo; quindi in questo caso le posizioni dei bit di controllo saranno 1(20),2(21),4(22),8(23). Per questo la parola di memoria diventerà di questa forma:

N° bit 1 2 3 4 5 6 7 8 9 10 11 12
Parola _ _ 1 _ 1 0 0 _ 0 1 1 0

Ora si deve capire quali valori dare ai bit di controllo; si darà valore 1 se il numero dei bit controllati dallo stesso che hanno valore 1 è dispari; si darà valore 0 se questo numero è pari. Perciò si guarda quali bit vengono controllati dai bit di controllo. “In generale il bit di posto b è controllato dai bit b1,b2,….,bj tali che b1 + b2 + … + bj = b. Per esempio il bit 5 è controllato dai bit 1 e 4 dato che 1 + 4 = 5. Il bit 6 è controllato dai bit 2 e 4 in quanto 2 + 4 = 6, e così via” (libro).

Bit 1: 1,3,5,7,9,11
Bit 2: 2,3,6,7,10,11
Bit 4: 4,5,6,7,12
Bit 8: 8,9,10,11,12

Poiché il numero di bit settati a 1 è 3 (dispari), al bit 1 assegneremo il valore 1. Bit 1 = 1

Si procede così per gli altri 3 bit.Poiché il numero di bit settati a 1 è 3 (dispari), al bit 1 assegneremo il valore 1. Bit 1 = 1
Bit 2 = 1

Bit 4 = 1

Bit 8 = 0

La parola si presenterà quindi in questa forma definitiva:

N° bit 1 2 3 4 5 6 7 8 9 10 11 12
Parola 1 1 1 1 1 0 0 0 0 1 1 0

Esercizio 2: Controllare la parola di memoria 111110100110 ed identificare se qualche bit è stato modificato da un errore di sistema. (ho usato la stessa parola dell’esercizio precedente prima ma dovete considerare che non conoscete la parola di partenza, quella giusta)

N° bit 1 2 3 4 5 6 7 8 9 10 11 12
Parola 1 1 1 1 1 0 1 0 0 1 1 0

(come potete vedere ho modificato il bit 7, vediamo però di riuscire a scoprirlo )

Bisogna semplicemente controllare i bit di controllo.

Bit 1 = 1 quindi ci aspettiamo un numero dispari di bit settati a 1 fra quelli controllati dal bit 1.

N° bit 3 5 7 9 11
Parola 1 1 1 0 1

Il numero di bit settati a 1 è pari, perciò il bit modificato è uno fra questi. Sono ancora 5 quindi adesso dovremo andare a restringere il campo. Perciò andiamo a controllare il bit di controllo 2 che controlla ben 3 di questi 5 bit. Poiché il bit 2 è settato a 1 ci aspettiamo un numero dispari di bit settati a 1.

N° bit 3 6 7 10 11
Parola 1 0 1 1 1

Invece sono 4 i bit settati a 1; questo restringe il campo a 3 bit (3,7,11).

Andando ora a controllare il bit di controllo 4, sapremo se il bit 7 è quello errato o è uno fra il bit 3 e il bit 11.

Il bit 4 è settato a 1 quindi ci aspettiamo ancora un numero dispari di bit settati a 1.

N° bit 5 6 7 12
Parola 1 0 1 0

Il numero di bit settati a 1 è 2. Perciò poiché i bit 3 e 11 non sono controllati dal bit di controllo 4 possiamo affermare che il bit alterato dall’errore è il bit 7.

Avvertenza 1: se trovate un solo caso in cui il valore del bit di controllo non combacia con la situazione dei bit settati a 1 allora il bit alterato sarà proprio il bit di controllo in questione.

Avvertenza 2: scrivete sempre il numero del bit sopra al valore perché sennò vi risulterà faticoso e difficile andare ogni volta a controllare il numero dei bit settati a 1.

Guida realizzata da Angelo Velardi

Binary Search Algorithm, written in C [with video example step-to-step]

In computer science, a binary search is an algorithm for locating the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element is equal to the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. This method halves the number of items to check each time, so it finds it or determines it’s not present in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
It is useful to find where an item is in a sorted array. For example, if you had an array for contact information, with people’s names, addresses, and telephone numbers sorted by name, you could use binary search to find out a few useful facts: whether the person’s information is in the array, what the person’s address is, and what the person’s telephone number is.
Continue reading Binary Search Algorithm, written in C [with video example step-to-step]

Linear Search in unordered array [with source code written in C and video example]

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1]
Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) may be much more efficient. Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster method. For example, one may sort the list and use binary search, or build any efficient search data structure from it.

This is an implementation of Linear Search in C Language, with Main structure.

Source Code


// © Codeido - www.codeido.com - Developed by Paolo Musolino

//Ricerca sequenziale in un array disordinato
#include <stdio.h>

int ricerca_Sequenziale(int a[], int n, int chiave)
{
	int i=0;
	
	while ((a[i]) && (i<n))
		   {
			   if (a[i]==chiave) 
			   {
				   return i;
				   
			   }
			   
			   if (i==n-1) 
			   {
				   return -1;
			   }
			   
			   if(a[i]!=chiave)
				   i++;
			   
		   }
	
}



int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int ris_ricerca;
	ris_ricerca = ricerca_Sequenziale(a, 14, 20);
	printf("\n");
	
	if (ris_ricerca==-1) {
		printf("L'elemento cercato non è presente all'interno dell'array\n");
	}
	
	if (ris_ricerca>=0) {
		printf("L'elemento cercato si trova nella posizione %d ", ris_ricerca);
	}
	
	return 0;
}

Non-uniform probabilities
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.
In particular, when the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1). If the table size n is large enough, linear search will be faster than binary search, whose cost is O(log n).[1]

Linear and Binary Searching

Studio dell’indice di condizionamento su alcune classi di matrici, rispetto alla norma 1 [FORTRAN 77]

Il condizionamento in matematica, in particolare nel calcolo numerico, riguarda il rapporto tra errore commesso sul risultato di un calcolo e incertezza sui dati in ingresso. Un problema è ben condizionato quando la soluzione del problema con delle piccole variazioni, non differisce molto dalla soluzione del problema originale; al contrario, un problema mal condizionato è un problema dove le soluzioni sono molto sensibili a piccole perturbazioni dei dati iniziali. In questo programma, scritto in FORTRAN 77, viene studiato l’indice di condizionamento delle matrici di Toepliz, Henkel, Vandermonde e Wilkinson rispetto alla norma 1.

Source Code:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
c 			  Realizzazione a cura di: 												   
c 			- Paolo Musolino			
c 			- Maria Emanuela Aricò
c 			- Armando Ruggeri
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

	PROGRAM main

	PARAMETER (n=4)
	REAL h(n,n), t(n,n), k(n,n), v(n,n), w(n,n), z(n,n), cond
	cond=0

c PREMESSA
	WRITE (*,*) '****************************************************'
	WRITE (*,*) 'Studio indice di condizionamento delle matrici'
	WRITE (*,*) 'di Toepliz, Henkel, Vandermonde e Wilkinson per la'
	WRITE (*,*) 'norma 1'
	WRITE (*,*) '****************************************************'
	WRITE (*,*)

c CREAZIONE MATRICI
	CALL hilbert(h, n)
	CALL toepliz(t, n)
	CALL toepliz2(z,n)
	CALL henkel(k, n)
	CALL vandermonde(v, n)
	CALL wilkinson (w, n)

c CALCOLO  E STAMPA CONDIZIONAMENTO
 	WRITE (*,*)
	WRITE (*,*) 'Indici di condizionamento' 
	CALL condz(h, n, cond)
	WRITE (*,*) 'Hilbert      :     ', cond
	CALL condz(t, n, cond)
	WRITE (*,*) 'Toepliz d.d  :     ', cond
	CALL condz(z, n, cond)
	WRITE (*,*) 'Toepliz n.d.d:     ', cond	
	CALL condz(k, n, cond)
	WRITE (*,*) 'Henkel       :     ', cond
	CALL condz(v, n, cond)
	WRITE (*,*) 'Vandermonde  :     ', cond
	CALL condz(w, n, cond)
	WRITE (*,*) 'Wilkinson    :     ', cond

	END

c SUBROUTINE DEL CALCOLO DELLE NORME
	SUBROUTINE norma (a, n, n1)

	INTEGER n
	REAL a(n,n), n1, x
	n1=0
	x=0

	DO j=1, n
	  DO i=1, n
	    x = x + abs(a(i,j))
	  ENDDO
	  IF(x .gt. n1) THEN
	      n1 = x
	  ENDIF
	  x = 0
	ENDDO

	END

		SUBROUTINE condz (a, n, cond)

	USE MSIMSL

	REAL a(n,n), ainv(n,n), cond, n1, n1inv
	PARAMETER  (lda=4, ldainv=4)
	CALL azzera(cond)
	n1 = 0
c CALCOLO INVERSA
	CALL LINRG (n, a, lda, ainv, ldainv)

c CALCOLO NORMA MATRICE
	CALL norma(a, n, n1)
c	WRITE (*,*) 'Norma 1        : ', n1
c CALCOLO NORMA MATRICE INVERSA
	CALL norma(ainv, n, n1inv)
c	WRITE (*,*) 'Norma 1 inversa: ', n1inv

c CALCOLO CONDIZIONAMENTO
	cond = n1 * n1inv

	END

	SUBROUTINE azzera (x)
	REAL x
	x=0
	END  

c MATRICE HILBERT
	SUBROUTINE hilbert (h, n)
	INTEGER n,i,j
	REAL h(n,n)
	DO i=1, n
	  DO j=1, n
	    h(i,j) = 1./(i+j-1)
	  ENDDO
	ENDDO
      WRITE (*,*) 'Matrice di Hilbert:' 
      DO i=1, n
	  WRITE (*,*) (h(i,j), j=1, n)
	ENDDO
	END

c MATRICE TOEPLIZ	DIAG. DOMINANTE
	SUBROUTINE toepliz (t, n)
	integer n,i,j 
	real vet(-(n-1):(n-1)),t(n,n)
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per Toepliz d.d.'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    t(i,j)=vet(j-i)
	  enddo
	enddo
	write(*,*)'La matrice di Toepliz:'
	DO i=1, n
	WRITE (*,*) (t(i,j), j=1, n)
	ENDDO	
	END

c MATRICE TOEPLIZ
	SUBROUTINE toepliz2 (t, n)
	integer n,i,j 
	real vet(-(n-1):(n-1)),t(n,n)
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per Toepliz non d.d.'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    t(i,j)=vet(j-i)
	  enddo
	enddo
	write(*,*)'La matrice di Toepliz:'
	DO i=1, n
	WRITE (*,*) (t(i,j), j=1, n)
	ENDDO	
	END

c MATRICE HENKEL
	SUBROUTINE henkel (k, n)
	integer n,i,j
	real vet(-(n-1):(n-1)),k(n,n) 
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per la matrice Henkel'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    k(i,j)=vet(i+j-(n+1))
	  enddo
	enddo
	write(*,*)'La matrice di Henkel:'
	DO i=1, n
	WRITE (*,*) (k(i,j), j=1, n)
	ENDDO	
	END

c MATRICE VANDERMONDE
	SUBROUTINE vandermonde (k, n)
	integer n,i,j
	real k(n,n),vet(n),a,b,x
	write(*,*) 'Inserire estremo a per la matrice Vandermonde'
	read (*,*) a
	write(*,*) 'Inserire estremo b per la matrice Vandermonde'
	read (*,*) b
	x = (b-a)/(n-1)
	do i=1, n
	  vet(i) = a + (i-1)*x
	enddo
	do i=1,n
	  do j=1,n
	    k(i,j)=vet(i)**(j-1)
	  enddo
	enddo
	write(*,*)'La matrice di Vandermonde:'
	DO i=1, n
	   WRITE (*,*) (k(i,j), j=1, n)
	ENDDO	
	END

c MATRICE WILKINSON
	SUBROUTINE wilkinson (w, n)
	integer n,i,j
	REAL w(n,n)
	DO i=1, n
	  DO j=1, n
	    IF (i .eq. j) THEN
	       w(i,j) = 1
		ELSE IF (i .gt. j) THEN
		   w(i,j) = (-1)**(j-i+1)
		ELSE IF ((i .lt. j) .and. (j .eq. n)) THEN
		   w(i,j) = (-1)**i
		ELSE
		   w(i,j) = 0
		ENDIF
	  ENDDO
	ENDDO
	WRITE (*,*) 'La matrice di Wilkinson:'
	DO i=1, n
	  WRITE (*,*) (w(i,j), j=1, n)
	ENDDO	
	END
 

Eseguendo il nostro programma, possiamo vedere che l’ indice di condizionamento, rispetto alla norma 1, è molto alto per la matrice di Hilbert. Sono stati restituiti degli alti valori anche per quelli della matrice di Henkel. E’ bene notare che se la Toepliz diagonale dominante e la Toepliz non diagonale dominante hanno gli stessi valori, la Toepliz non diagonale dominante presenta un indice di condizionamento peggiore di quella diagonale dominante. Possiamo affermare, infine, che la matrice di Toepliz diagonale dominante, insieme a quella di Wilkinson sono due esempi di matrici ben condizionate.

Leadsort written in C

The sorting algorithm “leadsort” is a variant of “bubblesort” that allows you to sort the array in reverse. Computational complexity= O(n^2).

Source Code written in C language:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void leadSort(int a[], int n)
{
	int i, j;
	
	for (i=n; i>1; i--) {
		for (j=1; j<i; j++) {
			if (confronto(a[j],a[j-1])<0) {
				swap(&a[j], &a[j-1]);
			}
		}
	}
	
}

int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	leadSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

Bubblesort written in C with example step-by-step

Source code of sorting algorithm “bubblesort” written in C. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Step-by-step example
Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

– First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
– Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.

Source Code in C:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void bubbleSort(int a[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++) 
	{
		for (j=n-1; j>i; j--) 
		{
			if (confronto(a[j], a[j-1])<0) 
			
				swap(&a[j], &a[j-1]);
			
		}
	}
}


//Main Function
int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	bubbleSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

[retweet]