Massimo 30 - Wiki

indice - versione precedente ripristinata

gsdefender — Mon, 05 Jul 2010 08:37:44 +0200

Questa è la pagina principale della wiki di Massimo 30, una struttura di incubazione per alcuni contenuti la cui produzione richiede la partecipazione simultanea di più utenti o per i quali siano richiesti strumenti di non facile gestione per l'utente medio (ad esempio, è possibile scrivere formule matematiche con la sintassi di \TeX senza che l'autore debba averlo installato sul proprio computer).

Tutti i contenuti possono essere visualizzati liberamente online, ma non possono essere modificati se non da un gruppo di utenti molto ristretto, scelto dagli amministratori volta per volta; data la natura estremamente volatile degli stessi, è altamente probabile che, nel momento in cui vengono visualizzati, siano contenuti degli errori che verranno corretti dopo pochissimo tempo. Gli esiti del lavoro collaborativo saranno resi disponibili, in futuro, a tutti gli utenti della community, tramite apposite entry della sezione Download.

Al momento ospitiamo progetti collaborativi per:

Programmazione 2 (corso tenuto dall'Ing. Daniele Peri presso la sede di Palermo della facoltà di Ingegneria Informatica dell'Università di Palermo): cerchiamo di mettere insieme gli appunti disponibili onde pervenire ad un testo di studio organico onnicomprensivo.

N.B. Il corso è stato tenuto dall'Ing. Peri fino all'anno accademico 2008/2009. Il materiale pubblicato, per quanto comunque utile, non è indicativo del contenuto del corso tenuto in anni successivi.

programmazione_2:grafi:indice

gsdefender — Wed, 03 Feb 2010 20:03:30 +0200

programmazione_2:ordinamento:algoritmi_non_basati_sui_confronti:radixsort

ordeal — Sun, 24 Jan 2010 04:45:36 +0200

#include <math.h>
#include <stdlib.h>
#include "queue.h"
#include <stdio.h>
 
void radixsort(Record* a[],int n,int k,int base)
{
register int t;
int iterations=log(k)/log(base);
 
for(t=0;t<iterations;t++)
	bucketsort(a,n,t,base);
}
 
void bucketsort(Record* records[],int n,int t,int base)
{
     register int i;
     Queue** queues=calloc(base,sizeof(Queue*));
     for(i=0;i<base;i++)
     	queues[i]=init_queue();
 
	enqueue_records(records,queues,n,t,base);
	dequeue_records(records,queues,base);
	free(queues);
}
 
 
void enqueue_records(Record* record_array[],Queue** queue_array,int n,int t,int base)
{
	register int i;
	for(i=0;i<n;i++)
	{
		int digit=t_digit(record_array[i]->key,t,base);
		queue_array[digit]=enqueue_record(queue_array[digit],record_array[i]);
	}
}
 
void dequeue_records(Record* record_array[],Queue** queue_array,int base)
{
  register int i,z=0;
 
  for(i=0;i<base;i++)
  {
	while(queue_is_empty(queue_array[i]) == FALSE)
		record_array[z++]=dequeue(queue_array[i]);
 
		queue_free(queue_array[i]);
   }
}
 
int t_digit(int number,int t,int base)
{
	return (number/(int)pow(base,t))%base;
}

Il radix sort è un algoritmo di ordinamento che permette di ordinare un insieme di n record con chiavi intere comprese tra 1 e k con un costo computazionale pari a O(n(1+\frac{\log k}{\log n})).

L’algoritmo utilizza un altro algoritmo di ordinamento per chiavi intere, chiamato Bucketsort; in particolare, il Radix sort effettua un numero di chiamata di Bucketsort pari al numero di cifre in cui si può esprimere la chiave più grande della collezione in una data base. Il radix ordina le chiavi a partire dalla loro cifra meno significativa. Quest'approccio bottom-up, è preferibile al classico approccio top-down, in quanto se pensassimo di ordinare ricorsivamente numeri aventi la stessa cifra iniziale, ci troveremmo ad operare su sottoproblemi di dimensione molto diversa l'uno dall'altro. L'algoritmo eredita la proprietà di stabilità dal Bucketsort essendo quest'ultimo invocato per ogni cifra i-esima.

L'algoritmo esegue \log_{k}{n} volte una chiamata a BucketSort di costo n, partendo dall'assunzione b=\Theta(n) (dove b è la base numerica) e usando la proprietà di cambiamento di base dell'algoritmo arriviamo al costo d'esecuzione O(n(\frac{\log(k)}{\log(n)})); ma poichè anche per k«n è almeno eseguita una lettura degli n elementi dell'istanza, aggiungiamo n al costo, che risulta quindi essere: O(n(1+\frac{\log k}{\log n}))

Nell’implementazione in C dell’algoritmo si è fatto uso di una coda disponibile tra le implementazioni della sezione strutture dati.

programmazione_2:tavole_hash:concatenazione

gsdefender — Thu, 27 Aug 2009 00:55:30 +0200

N.B. Per la concatenazione si utilizzano liste.

sc_ht_list.h

#ifndef _SC_HT_LIST_H
#define _SC_HT_LIST_H

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef void* void_ptr;

typedef struct sc_ht_node_t {
	void_ptr key, value;	/*chiave e valore*/
	size_t key_size, value_size; /*dimensione della chiave e del valore*/
	struct sc_ht_node_t * prev;    /*puntatore al nodo precedente*/
	struct sc_ht_node_t * next;    /*puntatore al nodo successivo*/
} sc_ht_node;

typedef sc_ht_node* sc_ht_node_ptr;

typedef struct sc_ht_list_t {
	unsigned int items;  /*numero di elementi della lista (>=0) */
	sc_ht_node_ptr first;  /*puntatore al primo elemento della lista */
} sc_ht_list;

typedef sc_ht_list* sc_ht_list_ptr;
typedef enum { CHAR_PTR, INT_PTR, UINT_PTR, LONG_PTR, ULONG_PTR } type_id;

sc_ht_node_ptr sc_ht_node_alloc(size_t, size_t);      /* alloca la memoria necessaria ad un nodo vuoto (usato internamente da sc_ht_list_insert(sc_ht_list_ptr, void_ptr, void_ptr)) */
void sc_ht_node_free(sc_ht_node_ptr);   /* libera la memoria allocata per il nodo passato come argomento */
sc_ht_list_ptr sc_ht_list_alloc();      /* alloca la memoria necessaria ad una lista vuota */
void sc_ht_list_free(sc_ht_list_ptr);   /* libera la memoria allocata per la lista passata come argomento */
sc_ht_list_ptr sc_ht_list_insert(sc_ht_list_ptr, void_ptr, size_t, void_ptr, size_t); /* inserisce una coppia chiave-valore in cima alla lista */
void_ptr sc_ht_list_search(sc_ht_list_ptr, void_ptr);  /*cerca un valore, data una chiave, in una lista */
sc_ht_list_ptr sc_ht_list_delete(sc_ht_list_ptr, void_ptr); /*cancella una coppia chiave-valore da una lista */
void sc_ht_list_print(sc_ht_list_ptr l, type_id t); /* stampa il contenuto di una lista nel formato chiave=valore, seguita da una freccia se c'è un elemento successivo.*/

#endif

sc_ht.h

#ifndef _SC_HT_H
#define _SC_HT_H

#include <stdio.h>
#include "sc_ht_list.h"

typedef sc_ht_list_ptr* sc_ht_table_ptr; /* Un vettore di liste è una hash table */

typedef struct _sc_ht_t {
	sc_ht_table_ptr table;
	uint items;
} sc_ht;

typedef sc_ht* sc_ht_ptr;

typedef unsigned int uint;

int hash(void_ptr, uint, type_id); /* Calcola l'hash della chiave fornita */
sc_ht_ptr sc_ht_alloc(uint); /* Alloca memoria per una tabella hash */
void sc_ht_free(sc_ht_ptr); /* Libera la memoria allocata per la tabella hash passata come argomento */
void _sc_ht_insert(sc_ht_ptr, void_ptr, size_t, void_ptr, size_t, type_id); /* Inserisce una coppia chiave=valore in una tabella hash */
void sc_ht_delete(sc_ht_ptr, void_ptr, type_id); /* Cancella, data la chiave, anche il corrispondente valore dalla tabella hash */
void_ptr sc_ht_search(sc_ht_ptr, void_ptr, type_id); /* Cerca l'elemento corrispondente alla chiave data nella tabella: restituisce NULL se la chiave non viene trovata */
void sc_ht_print(sc_ht_ptr, type_id); /* Stampa il contenuto della tabella */

/* Lunghezza del vettore */
#define sc_ht_insert_c_string(a, b, c) _sc_ht_insert(a, b, (1+(strlen(b))), c, (1+(strlen(c))), CHAR_PTR)

#endif

sc_ht_list.c

#include "sc_ht_list.h"

sc_ht_node_ptr sc_ht_node_alloc(size_t ks, size_t vs)
{
	sc_ht_node_ptr n=(sc_ht_node_ptr)(calloc(1, sizeof(sc_ht_node)));  /*Memoria per l'intera struttura */

	if(n && (vs>0) && (ks>0))
	{
		n->key=calloc(1, vs); /*Memoria per la chiave */
		n->value=calloc(1, ks); /*Memoria per il valore */
		n->key_size=ks;
		n->value_size=vs;
		n->next=NULL; /* Non c'è alcun elemento successivo o precedente un nodo staccato */
		n->prev=NULL;
	}

	return n;
}

void sc_ht_node_free(sc_ht_node_ptr n)
{
    if(n)
    {
	if(n->next) n->next->prev=n->prev; /* Se non ci troviamo alla fine della lista, L'elemento che precede il nodo che segue quello corrente sarà quello che precede il nodo corrente */
	if(n->prev) n->prev->next=n->next;  /* L'elemento che segue il nodo che precede quello corrente sarà quello che segue il nodo corrente */
 	free(n->value);
	free(n->key);
	free((void*)n);
    }
}

sc_ht_list_ptr sc_ht_list_alloc()
{
	sc_ht_list_ptr l=(sc_ht_list_ptr)(calloc(1, sizeof(sc_ht_list))); /*Memoria per la lista: spazio per numero degli elementi e puntatore al primo */

	if(l)
	{
		l->items=0;
		l->first=NULL;
	}

	return l;
}

void sc_ht_list_free(sc_ht_list_ptr l)
{	
    sc_ht_node_ptr _n=l->first; /* Puntatore alla testa della lista */
	
    if(_n) /* Se il puntatore è valido */
    {
	    while(_n->next) _n=_n->next; /* Arriviamo alla fine della lista, */

	    while(_n->prev)	 /* quindi retrocediamo di un nodo alla volta liberando la memoria. */
	    {			 /* (sarebbe stato più efficiente tenere un puntatore all'ultimo elemento della lista) */
		_n=_n->prev;
		 sc_ht_node_free(_n->next);
		 l->items--;
	    }	
	    free((void*)l);
    }
}

sc_ht_list_ptr sc_ht_list_insert(sc_ht_list_ptr l, void_ptr k, size_t ks, void_ptr v, size_t vs)
{
	sc_ht_node_ptr _n=NULL;

	if(v && l && k)
	{
		_n=sc_ht_node_alloc(ks, vs);  /* Alloco memoria per il nodo */
		if(_n) /* Allocazione avvenuta */
		{
			memcpy(_n->key, k, ks); /* Copio chiave e valore nelle loro locazioni */
			memcpy(_n->value, v, vs);
			_n->prev=NULL; /* Inseriamo in testa: un nuovo nodo sarà sempre il primo */
			_n->next=l->first; /* Dopo il nuovo nodo ci sarà quello che era il primo fino all'esecuzione dell'operazione di insert */
			if(l->first) l->first->prev=_n;  /* Se il nuovo nodo non è l'unico nodo della lista, va aggiornato anche il puntatore al precedente*/
			l->first=_n; /* Colleghiamo in testa */
			l->items++; /* Un nodo in più */
		}
	}

	return l;
}

void_ptr sc_ht_list_search(sc_ht_list_ptr l, void_ptr k)
{
	unsigned int _i = 0;
	sc_ht_node_ptr _n=l->first; /*Puntatore al puntatore alla testa */

	if(l && k)
	{
		while(memcmp(_n->key,k,_n->key_size)!=0 && _i<l->items) /* Finchè le chiavi non corrispondono... */
		{
			if(_n->next)  /* Se c'è un nodo successivo, andiamoci */
			{
				_n=_n->next;
				_i++;
			}
			else /* Siamo all'ultimo nodo, l'elemento non c'è */
				return NULL;
		}
		
		return _n->value; 
	}
	return NULL; /* Per sicurezza */
}

sc_ht_list_ptr sc_ht_list_delete(sc_ht_list_ptr l, void_ptr k)
{
	sc_ht_node_ptr _n=l->first; /* Puntatore al puntatore alla testa */
	unsigned int _i=0;

	if(k && l)
	{
		while(memcmp(_n->key,k,_n->key_size)!=0 && _i<l->items) /* Finchè le chiavi non corrispondono... */
		{
			if(_n->next)  /* Se c'è un nodo successivo, andiamoci */
			{
				_n=_n->next;
				_i++;
			}
			else /* Siamo all'ultimo nodo, l'elemento non c'è */
				return l;
		}
		sc_ht_node_free(_n);
		l->items--; /* C'è un elemento in meno. */
	}	
	return l;
}

void sc_ht_list_print(sc_ht_list_ptr l, type_id t)
{
	unsigned int _i=0;
	sc_ht_node_ptr _n=l->first;

	if(l)
	{
		for(_i=0; _i<l->items && _n!=NULL; _i++)
		{
			switch(t)
			{
				case CHAR_PTR: printf("%s=%s", (char*)(_n->key), (char*)(_n->value)); break;
				case INT_PTR: printf("%d=%d", *(int*)(_n->key), *(int*)(_n->value)); break;
				case UINT_PTR: printf("%u=%u", *(unsigned int*)(_n->key), *(unsigned int*)(_n->value)); break;
	    /* Nota: richiedono compatibilità C99.
	     *			case LONG_PTR: printf("%l=%l", *(long*)(_n->key), *(long*)(_n->value)); break;
	     *			case ULONG_PTR: printf("%ul=%ul", *(unsigned long*)(_n->key), *(unsigned long*)(_n->value)); break;				 
	    */
				default: break;
			}
			_n=_n->next;
			if(_n) printf(" => ");
			else break;
		}
		printf("\n");
	}
}

sc_ht.c

#include "sc_ht.h"

/* Avendo adottato una tipologia di progettazione bottom-up, tutte le funzioni di gestione
 * della lista si riducono a poco più che wrapper. Infatti, una hash table sarà un vettore
 * di liste, per il quale.
 *
 * 1) Si individua la posizione utile, richiamando la funzione hash(chiave, tipo_della_chiave)
 * 2) Si verifica che tabella, chiave, valore ed hash siano ammissibili
 * 3) Si richiama la funzione implementata per una singola lista.
 * 4) Si restituisce (se necessario) il risultato all'utente.
 *
 * L'unica funzione su cui occorre dire qualcosa è hash(chiave, tipo_della_chiave). Vedere 
 * più in basso.
*/

void _sc_ht_insert(sc_ht_ptr ht, void_ptr k, size_t ks, void_ptr e, size_t es, type_id t)
{
	int index=0;
	
	if (ht && e && (es>0) && k && (ks>0))
	{
		index=hash(k, ht->items, t);
		if(index>=0) ht->table[index] = sc_ht_list_insert(ht->table[index], e, es, k, ks);
	}
}

void sc_ht_delete(sc_ht_ptr ht, void_ptr k, type_id t)
{
	int index=0;
	
	if(ht && k)
	{	
		index=hash(k, ht->items, t);
		if(index>=0) ht->table[index] = sc_ht_list_delete(ht->table[index], k);
	}
}

void_ptr sc_ht_search(sc_ht_ptr ht, void_ptr k, type_id t)
{
	int index=0;

	if(ht && k)
	{
		index=hash(k, ht->items, t);
		if(index>=0) return sc_ht_list_search(ht->table[index], k);
	}

	return NULL;
}

sc_ht_table_ptr sc_ht_table_alloc(uint m)
{
	unsigned int i=0;
	sc_ht_table_ptr t=NULL;

	if(m>0)
	{
		t=(sc_ht_table_ptr)(calloc(m, sizeof(sc_ht_list)));

		if(t)
		{
			for(i=0;i<m;i++) t[i]=sc_ht_list_alloc();
		}
	}

	return t;
}

sc_ht_ptr sc_ht_alloc(uint m)
{
	sc_ht_ptr ht = NULL;

	if(m>0)
	{
		ht=(sc_ht_ptr)(calloc(1, sizeof(sc_ht)));
		
		if(ht)
		{
			ht->items=m;
			ht->table=sc_ht_table_alloc(ht->items);
			if(!ht->table) sc_ht_free(ht);
		}
	}

	return ht;
}

void sc_ht_free(sc_ht_ptr ht)
{
    unsigned int i=0;
    
    if(ht)
    {
	for(i=0;i<ht->items;i++) sc_ht_list_free(ht->table[i]);
	ht->items=0;
	free(ht->table);
	free(ht);
    }
}

int hash(void_ptr k, uint m, type_id t)
{
/* La funzione di hashing adottata è molto semplice (e primitiva): [chiave] modulo M. M è prefissato
 * con una direttiva di preprocessore e deve essere abbastanza lontano da una potenza di 2
 *
 * Quello di cui si occupa questa funzione è essenzialmente di effettuare correttamente il casting
 * della chiave, che è un puntatore a void, rendendo possibile la dereferenziazione e quindi l'operazione
 * di modulo.
*/
	if(k)
	{
		switch(t)
		{
			case INT_PTR: return *((int*)k)%m; break;
			case UINT_PTR: return *((unsigned int*)k)%m; break;
			case LONG_PTR: return *((long*)k)%m;  break;
			case ULONG_PTR: return *((unsigned long*)k)%m; break;
			case CHAR_PTR: return (int)(*(char*)k)%m; break;
			default: break;
		}
	}
	return -1; /* Hash non valido: le posizioni di un array cominciano da 0, per cui si saprà che c'è stato un errore. */
}

void sc_ht_print(sc_ht_ptr ht, type_id t)
{
	unsigned int i = 0;

	if(ht)
	{
		for(i=0;i<ht->items;i++) 
		{
			printf("[%d] ", i);
			sc_ht_list_print(ht->table[i], t);			
		}
	}
}

main.c

#include <stdio.h>
#include "sc_ht.h"

int main()
{
	sc_ht_ptr ht=NULL;
	printf("Alloco memoria per la tabella:\n");
	ht=sc_ht_alloc(80);
	printf("Inserimento nella tabella:\n\nchiave: ABCDEFGHIJKLMNOPQRSTUVWXYZ\nvalore: PRECIPITEVOLISSIMEVOLMENTE\n");
	sc_ht_insert_c_string(ht, "A", "P");
	sc_ht_insert_c_string(ht, "B", "R");
	sc_ht_insert_c_string(ht, "C", "E");
	sc_ht_insert_c_string(ht, "D", "C");
	sc_ht_insert_c_string(ht, "E", "I");
	sc_ht_insert_c_string(ht, "F", "P");
	sc_ht_insert_c_string(ht, "G", "I");
	sc_ht_insert_c_string(ht, "H", "T");
	sc_ht_insert_c_string(ht, "I", "E");
	sc_ht_insert_c_string(ht, "J", "V");
	sc_ht_insert_c_string(ht, "K", "O");
	sc_ht_insert_c_string(ht, "L", "L");
	sc_ht_insert_c_string(ht, "M", "I");
	sc_ht_insert_c_string(ht, "N", "S");
	sc_ht_insert_c_string(ht, "O", "S");
	sc_ht_insert_c_string(ht, "P", "I");
	sc_ht_insert_c_string(ht, "Q", "M");
	sc_ht_insert_c_string(ht, "R", "E");
	sc_ht_insert_c_string(ht, "S", "V");
	sc_ht_insert_c_string(ht, "T", "O");
	sc_ht_insert_c_string(ht, "U", "L");
	sc_ht_insert_c_string(ht, "V", "M");
	sc_ht_insert_c_string(ht, "W", "E");
	sc_ht_insert_c_string(ht, "X", "N");
	sc_ht_insert_c_string(ht, "Y", "T");
	sc_ht_insert_c_string(ht, "Z", "E");
	printf("\nStampa della struttura della tabella\n");
	sc_ht_print(ht, CHAR_PTR);
	printf("\nRicerca del valore corrispondente alla chiave O: ");
	printf("%s\n", (char*)sc_ht_search(ht, (void_ptr)"O", CHAR_PTR));
	printf("\nRimozione del valore corrispondente alla chiave O.");
	sc_ht_delete(ht,(void_ptr)"O", CHAR_PTR);
	printf("\nRicerca del valore corrispondente alla chiave O: ");
	if(sc_ht_search(ht, (void_ptr)"O", CHAR_PTR))
		printf("%s\n", (char*)sc_ht_search(ht, (void_ptr)"O", CHAR_PTR));
	else
		printf("NON TROVATO\n");
	printf("\nStampa della struttura della tabella\n");
	sc_ht_print(ht, CHAR_PTR);
	printf("\nLibero la memoria allocata per la tabella\n");
	sc_ht_free(ht);
	return 0;
}

programmazione_2:tavole_hash:indirizzamento_aperto

gsdefender — Thu, 27 Aug 2009 00:50:57 +0200

oa_ht.h

#ifndef _OA_HT_H
#define _OA_HT_H

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef unsigned int uint;
typedef void* void_ptr;
typedef enum { true=0, false=1 } boolean;
typedef enum { CHAR_PTR, INT_PTR, UINT_PTR, LONG_PTR, ULONG_PTR } type_id;

typedef struct _oa_ht_item_t {
	void_ptr key, value;
	size_t key_size, value_size;
} oa_ht_item_t;

typedef oa_ht_item_t* oa_ht_item_ptr;
typedef oa_ht_item_ptr* oa_ht_table_ptr;

typedef struct _oa_ht_t {
	uint items;
	oa_ht_table_ptr table;
} oa_ht;

typedef oa_ht* oa_ht_ptr;

int hash(void_ptr, uint, uint, type_id);
int _oa_ht_insert(oa_ht_ptr, void_ptr, size_t, void_ptr, size_t, type_id);
int _oa_ht_delete(oa_ht_ptr ht, void_ptr k, type_id t);
oa_ht_ptr oa_ht_alloc(uint);
void_ptr _oa_ht_search(oa_ht_ptr, void_ptr, type_id);
void oa_ht_print(oa_ht_ptr ht, type_id);
void oa_ht_free(oa_ht_ptr);
boolean oa_ht_is_cell_free(oa_ht_item_ptr);
boolean oa_ht_was_cell_emptied(oa_ht_item_ptr);

#define CANC ((char*)"[[CANCELLATO]]")
#define CANC_SIZE (1+strlen(CANC))

#define oa_ht_insert_c_string(a, b, c) _oa_ht_insert(a, (char*)b, (1+strlen(b)), (char*)c, (1+strlen(c)), CHAR_PTR)
#define oa_ht_search_c_string(a, b) (char*)_oa_ht_search(a, b, CHAR_PTR)
#define oa_ht_delete_c_string(a, b) _oa_ht_delete(a, (char*)b, CHAR_PTR)

#endif

oa_ht.c

#include "oa_ht.h"

/* Alloca memoria per un elemento del vettore */

oa_ht_item_ptr oa_ht_item_alloc()
{
	oa_ht_item_ptr i=(oa_ht_item_ptr)(calloc(1, sizeof(oa_ht_item_t)));

	if(i)
	{
		i->key=i->value=NULL;	
		i->key_size=i->value_size=0;
	}

	return i;
}

/* Libera la memoria occupata da un elemento del vettore */

void oa_ht_item_free(oa_ht_item_ptr i)
{
	if(i)
	{
		if(i->key) free(i->key);
		if(i->value) free(i->value);
		i->key_size=i->value_size=0;
		free(i);
	}
}

void oa_ht_table_free(oa_ht_table_ptr t, uint i)
{
	uint j=0;

	if(t && (i>0))
	{
		for(j=0;j<i;j++) oa_ht_item_free(t[j]);
		free(t);
	}
}

oa_ht_table_ptr oa_ht_table_alloc(uint i)
{
	oa_ht_table_ptr t=NULL;
	uint j=0;

	if(i>0) 
	{
		t=(oa_ht_table_ptr)(calloc(i, sizeof(oa_ht_item_t)));
		if(t) {	for(j=0;j<i;j++) t[j]=oa_ht_item_alloc(); }
	}

	return t;
}

oa_ht_ptr oa_ht_alloc(uint i)
{
	oa_ht_ptr ht=(oa_ht_ptr)(calloc(1, sizeof(oa_ht)));

	if(ht)
	{
		ht->items=i;
		ht->table=oa_ht_table_alloc(ht->items);
		if(!ht->table) oa_ht_free(ht);
	}

	return ht;
}

void oa_ht_free(oa_ht_ptr ht)
{
	if(ht)
	{
		oa_ht_table_free(ht->table, ht->items);
		ht->items=0;
		free(ht);
	}
}

int hash(void_ptr k, uint i, uint m, type_id t)
{
/* La funzione di hashing adottata è molto semplice (e primitiva): [chiave] modulo M. M è prefissato
 * con una direttiva di preprocessore e deve essere abbastanza lontano da una potenza di 2
 *
 * Quello di cui si occupa questa funzione è essenzialmente di effettuare correttamente il casting
 * della chiave, che è un puntatore a void, rendendo possibile la dereferenziazione e quindi l'operazione
 * di modulo.
*/
	if(k && (i>=0))
	{
		switch(t)
		{
			case INT_PTR: return *(((int*)k)+i)%m; break;
			case UINT_PTR: return *(((uint*)k)+i)%m; break;
			case LONG_PTR: return *(((long*)k)+i)%m;  break;
			case ULONG_PTR: return *(((unsigned long*)k)+i)%m; break;
			case CHAR_PTR: return (int)((*(char*)k)+i)%m; break;
			default: break;
		}
	}
	return -1; /* Hash non valido: le posizioni di un array cominciano da 0, per cui si saprà che c'è stato un errore. */
}

boolean oa_ht_is_cell_free(oa_ht_item_ptr i)
{
	if(i && !i->value) return true;
	
	return false;
}

boolean oa_ht_was_cell_emptied(oa_ht_item_ptr i)
{
	if (i && (memcmp(i, CANC, CANC_SIZE)==0)) return true;

	return false;
}

int _oa_ht_insert(oa_ht_ptr ht, void_ptr k, size_t ks, void_ptr e, size_t es, type_id t)
{
	int h_k, i;

	h_k=i=0;

	if(ht && k && (ks>0) && e && (es>0))
	{
		for(i=0;i<ht->items;i++)
		{
			h_k=hash(k, i, ht->items, t);
			if((h_k>=0) && (oa_ht_is_cell_free(ht->table[h_k])==true || oa_ht_was_cell_emptied(ht->table[h_k])==true) )
			{
				ht->table[h_k]->key=calloc(1, ks);		
				ht->table[h_k]->value=calloc(1, es);
					
				if(ht->table[h_k]->key && ht->table[h_k]->value)
				{
					ht->table[h_k]->key_size=ks;
					ht->table[h_k]->value_size=es;
					memcpy(ht->table[h_k]->key, k, ks);
					memcpy(ht->table[h_k]->value, e, es);
					ht->items++;
					return 0;
				}				
			}
		}
	} 
	return -1;
}

void_ptr _oa_ht_search(oa_ht_ptr ht, void_ptr k, type_id t)
{
	int h_k, i;

	h_k=i=0;

	if(ht)
	{
		for(i=0;i<ht->items;i++)
		{
			h_k=hash(k, i, ht->items, t);
			if(h_k>=0)
			{
				if(ht->table[h_k] && !ht->table[h_k]->value) return NULL;
				if(ht->table[h_k] && ht->table[h_k]->key && ht->table[h_k]->value && (memcmp(ht->table[h_k]->key, k, ht->table[h_k]->key_size)==0) && (memcmp(ht->table[h_k]->value, CANC, CANC_SIZE)!=0))	return ht->table[h_k]->value;
			}
		}
	}
	return NULL;
}

int _oa_ht_delete(oa_ht_ptr ht, void_ptr k, type_id t)
{
	int h_k, i;

	h_k=i=0;

	if(ht && k)
	{
		for(i=0;i<ht->items;i++)
		{
			h_k=hash(k, i, ht->items, t);
			if((h_k>=0) && (memcmp(ht->table[h_k]->key, k, ht->table[h_k]->key_size)==0))
			{
				free(ht->table[h_k]->value);
				ht->table[h_k]->value_size=0;
				ht->table[h_k]->value=calloc(1, CANC_SIZE);
				if(ht->table[h_k]->value)
				{
 				        memcpy(ht->table[h_k]->value, CANC, CANC_SIZE);
					ht->table[h_k]->value_size=CANC_SIZE;
					return 0;
				}
			}
		}
	}
	return -1;
}

void oa_ht_print(oa_ht_ptr ht, type_id t)
{
	uint i=0;

	if(ht)
	{
		
		printf("\n");
		for(i=0;i<ht->items;i++)
		{
			if(ht->table[i] && ht->table[i]->key) 
			{
				printf("[%d] ", i);			
				switch(t)
				{
					case CHAR_PTR: printf("%s=%s", (char*)(ht->table[i]->key), (char*)(ht->table[i]->value)); break;
					case INT_PTR: printf("%d=%d", *(int*)(ht->table[i]->key), *(int*)(ht->table[i]->value)); break;
					case UINT_PTR: printf("%u=%u", *(uint*)(ht->table[i]->key), *(uint*)(ht->table[i]->value)); break;
	    /* Nota: richiedono compatibilità C99.
	     *			case LONG_PTR: printf("%l=%l", *(long*)(ht->table[i]->key), *(long*)(ht->table[i]->value)); break;
	     *	case ULONG_PTR: printf("%ul=%ul", *(unsigned long*)(ht->table[i]->key), *(unsigned long*)(ht->table[i]->value)); break;				 
	    */
					default: break;
				} 
				printf("\n");
			}
		}
	}
}

main.c

#include <stdio.h>
#include "oa_ht.h"

int main()
{
	oa_ht_ptr ht=NULL;
	printf("Alloco memoria per la tabella:\n");
	ht=oa_ht_alloc(256);
	int retval=0;
	printf("Inserimento nella tabella:\n\nchiave: ABCDEFGHIJKLMNOPQRSTUVWXYZ\nvalore: PRECIPITEVOLISSIMEVOLMENTE\n");
	if(ht)
	{
		oa_ht_insert_c_string(ht, "A", "P");
		oa_ht_insert_c_string(ht, "B", "R");
		oa_ht_insert_c_string(ht, "C", "E");
		oa_ht_insert_c_string(ht, "D", "C");
		oa_ht_insert_c_string(ht, "E", "I");
		oa_ht_insert_c_string(ht, "F", "P");
		oa_ht_insert_c_string(ht, "G", "I");
		oa_ht_insert_c_string(ht, "H", "T");
		oa_ht_insert_c_string(ht, "I", "E");
		oa_ht_insert_c_string(ht, "J", "V");
		oa_ht_insert_c_string(ht, "K", "O");
		oa_ht_insert_c_string(ht, "L", "L");
		oa_ht_insert_c_string(ht, "M", "I");
		oa_ht_insert_c_string(ht, "N", "S");
		oa_ht_insert_c_string(ht, "O", "S");
		oa_ht_insert_c_string(ht, "P", "I");
		oa_ht_insert_c_string(ht, "Q", "M");
		oa_ht_insert_c_string(ht, "R", "E");
		oa_ht_insert_c_string(ht, "S", "V");
		oa_ht_insert_c_string(ht, "T", "O");
		oa_ht_insert_c_string(ht, "U", "L");
		oa_ht_insert_c_string(ht, "V", "M");
		oa_ht_insert_c_string(ht, "W", "E");
		oa_ht_insert_c_string(ht, "X", "N");
		oa_ht_insert_c_string(ht, "Y", "T");
		oa_ht_insert_c_string(ht, "Z", "E");
		printf("\nStampa della struttura della tabella\n");
		oa_ht_print(ht, CHAR_PTR);
		printf("\nRicerca del valore corrispondente alla chiave O: ");
		printf("%s\n", oa_ht_search_c_string(ht, "O"));
		printf("\nRimozione del valore corrispondente alla chiave E.\n");
		retval=oa_ht_delete_c_string(ht, "E");
		if(oa_ht_search_c_string(ht, "E"))
			printf("%s\n", oa_ht_search_c_string(ht, "E"));
		else if(retval==0)
			printf("VALORE RIMOSSO CON SUCCESSO\n");
		printf("\nRicerca del valore corrispondente alla chiave Z: ");
		if(oa_ht_search_c_string(ht, "Z"))
			printf("%s\n", oa_ht_search_c_string(ht, "Z"));
		else
			printf("NON TROVATO\n");
		printf("Libero la memoria allocata per la tabella\n");
		oa_ht_free(ht);
	}
	return 0;
}

programmazione_2:modelli_di_calcolo_e_analisi_degli_algoritmi:teorema_fondamentale_delle_ricorrenze

ordeal — Thu, 16 Jul 2009 23:40:10 +0200

TEOREMA FONDAMENTALE DELLE RICORRENZE

Supponiamo che un problema di dimensione n venga diviso in a sottoproblemi di dimensione \frac{n}{b} ciascuno, e che ad ogni suddivisione sia necessario un tempo f(n) per poter rielaborare i dati parziali.

La relazione di ricorrenza corrispondente a tale algoritmo ricorsivo è: T(n) = aT(\frac{n}{b}) + f(n)

Il teorema master, supposto che n sia una potenza esatta di b, e che la ricorsione si fermi per n=1, risolve la precedente relazione di ricorrenza con una formula aperta.

Rappresentiamo l'algoritmo ricorsivo che risolve il precedente problema, su un albero di ricorsione, ove ogni nodo rappresenta una generica chiamata ricorsiva, operante su una certa porzione del problema iniziale.

Proprietà 1 Il contributo di ogni nodo a livello i al tempo di esecuzione è f(\frac{n}{b^i})

Proprietà 2 All' i-esimo livello sono presenti a^i nodi

Proprietà 3 Poichè la massima profondità si ha quando la dimensione dei dati su cui operare è 1, le foglie contribuiscono con f(1), il livello delle foglie si ha per 1 = \frac{n}{b^i} \Rightarrow i=log_b{n}

Il costo d'esecuzione, visto come somma dei contributi di ogni nodo, vale pertanto

(R) T(n) = \sum_{i=0}^{log_b{n}}{a^i f(\frac{n}{b^i})}

Articoliamo lo sviluppo di tale somma in 3 casi:

Ip. f(n)= O(n^{log_{b}{a} - \epsilon}) per \epsilon costante e >0

Th. T(n) = \Theta(n^{log_{b}{a}})

Ip. f(n) = \Theta(n^{log_{b}{a}})

Th. T(n) = \Theta(n^{log_{b}{a}} log_{b}{n})

Ip. cf(n) \geq af(\frac{n}{b}) per 0 < c < 1

( e quindi f(n) = \Omega(n^{log_{b}{a} + \epsilon})

Th. T(n)=\Omega(f(n))

Dimostrazione

Dalla (R) abbiamo:

T(n) = \sum_{i=0}^{log_b{n}}{a^i O( (\frac{n}{b^i})^{log_{b}{a} -\epsilon} )} =

O(\sum_{i=0}^{log_b{n}}{n^{log_b{a - \epsilon}}b^{i\epsilon} }) =

O(n^{log_b{a} - \epsilon}\sum_{i=0}^{log_b{n}}{(b^{\epsilon})^{i} }) =

O(n^{log_b{a} -\epsilon} (1+b^{\epsilon} + \ldots n^{\epsilon})) =

O(n^{log_b{a}-\epsilon}(n^{\epsilon} +O(n^{\epsilon}))) =

O(n^{log_b{a}-\epsilon}n^{\epsilon}) =

O(n^{log_b{a}})

Inoltre per le proprietà 2 e 3, il contributo delle sole foglie al costo totale è a^{log_b{n}}=n^{log_b{a}}, quindi T(n)=\Omega(n^{log_b{a}}), pertanto

T(n)=\Theta(n^{log_b{a}}) C.V.D.

Dalla (R) abbiamo:

T(n)=\sum_{i=0}^{log_b{n}}{a^i \Theta( (\frac{n}{b^i})^{log_b{a}} )} = \Theta(\sum_{i=0}^{log_b{n}}{n^{log_b{a}}}) = \Theta(n^{log_b{a}}\sum_{i=0}^{log_b{n}}{1}) = \Theta(n^{log_b{a}}log_b{n}) C.V.D.

Notiamo che l'equazione f(n)=\Omega(n^{log_b{a} + \epsilon}) NON è l'ipotesi, bensì è una condizione NECESSARIA all'ipotesi cf(n) \geq af(\frac{n}{b}) per 0 < c < 1

Da quest'ultima ricaviamo iterativamente :

af(\frac{n}{b}) \leq cf(n) \Rightarrow f(\frac{n}{b}) \leq \frac{c}{a} f(n) \Rightarrow f(\frac{n}{b^2}) \leq (\frac{c}{a})^{2}f(n) \Rightarrow \ldots f(\frac{n}{b^i}) \leq (\frac{c}{a})^i f(n) \Rightarrow a^i f(\frac{n}{b^i}) \leq c^if(n)

Da quest'ultima e dalla R abbiamo:

T(n) \leq \sum_{i=0}^{log_b{n}}{c^i f(n)} \leq f(n)\sum_{i=0}^{\infty}{c^i} = f(n) \frac{1}{1-c} = \Theta(f(n))

\Rightarrow T(n)=O(f(n))

ma f(n) è il contributo del solo nodo radice, quindi T(n) = \Omega(f(n)) e quindi T(n) = \Theta(f(n)) C.V.D.

Dimostriamo infine che af(\frac{n}{b}) \leq cf(n) \Rightarrow f(n)=\Omega(n^{log_b{a}+\epsilon}) con c<1

se \frac{a}{c}f(\frac{n}{b}) \leq f(n) abbiamo iterativamente che:

\frac{n^{log_b{a}}}{n^{log_b{c}}} \ldots \frac{a^i}{c^i}f(\frac{n}{b^i}) \leq \ldots \frac{a^2}{c^2}f(\frac{n}{b^2}) \leq \frac{a}{c}f(\frac{n}{b}) \leq f(n)

\Rightarrow n^{log_b{a}}n^{log_b{\frac{1}{c}}} \leq f(n)

\Rightarrow f(n) = \Omega(n^{log_b{a}}n^{\epsilon}) con \epsilon = log_b{\frac{1}{c}} C.V.D.

programmazione_2:selezione_e_statistiche_di_ordine:calcolo_deterministico_del_mediano - creata

gsdefender — Thu, 12 Mar 2009 20:57:53 +0200