The Birth of Computer Science

La nascita dell’informatica.
Il primo kernel Linux è stato pubblicato nel 1991, l’annuncio del primo sistema operativo della famiglia Windows risale al 1983, la nascita dell’informatica come disciplina scientifica risale al 1953, il primo calcolatore programmabile digitale al 1941 (Z3 di Zuse); in realtà tutto scaturisce da una storia molto più lunga che parte dagli studi di Leibniz quando non esistevano i calcolatori digitali, e coinvolge grandi studiosi come Frege, Gödel, e Turing.

Continue reading “The Birth of Computer Science”

Recursive implementation of Heap sort algorithm

L’ heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L’ heapsort per eseguire l’ordinamento, utilizza una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell’albero e ad ogni nodo corrisponde uno ed un solo elemento.

In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.

Quindi in ogni istante, in un heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l’ordinamento di array.

In questo caso si considera come radice l’elemento iniziale di indice 1; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.

Continue reading “Recursive implementation of Heap sort algorithm”

C implementation of Heap sort algorithm

L’ heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L’ heapsort per eseguire l’ordinamento, utilizza una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell’albero e ad ogni nodo corrisponde uno ed un solo elemento.

In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.

Quindi in ogni istante, in un heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l’ordinamento di array.

In questo caso si considera come radice l’elemento iniziale di indice 1; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.

Continue reading “C implementation of Heap sort algorithm”

ISDN Technology

Integrated Services Digital Network, o ISDN, è una rete digitale che dà supporto a molti servizi di voce e dati. La definizione tecnica dell’ISDN, che investe diverse componenti delle reti, risale alle raccomandazioni ITU-T della serie I del 1984 e comprende numerose altre pubblicazioni dello stesso ITU-T e dell’ETSI (European Telecommunications Standard Institute) fatte negli anni successivi.
Continue reading “ISDN Technology”

Java implementation of the Ackermann function

Wilhelm Friedrich Ackermann (29/3/1896 – 24/12/1962) was a German mathematician best known for the Ackermann function, an important example in the theory of computation.
La funzione di Ackermann è una funzione f(x,y,z) che ha come dominio l’insieme delle terne di numeri naturali e come codominio i numeri naturali.
Essa è un esempio di funzione ricorsiva che non è primitiva ricorsiva poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva.

Continue reading “Java implementation of the Ackermann function”

XQuery queries in Java

XQuery, una abbrevazione per XML Query Language, è un linguaggio di programmazione specificato dal W3C e destinato ad interrogare documenti e basi di dati XML. Questo perché XML si sta proponendo come la tecnologia per rimpiazzare i vecchi DBMS relazionali :-)

Il w3c ha definito il linguaggio XQuery 1.0; usa la sintassi delle espressioni di XPath  2.0, con l’aggiunta delle cosiddette espressioni FLWOR per la formulazione di query complesse. Il risultato è un linguaggio di programmazione funzionale, dichiarativo, con somiglianze con il vecchio SQL.

Per effettuare delle query xquery su un file XML possiamo usare delle librerie come BaseX e Saxon. Purtroppo attualmente Saxon non è un prodotto del tutto gratuito, quindi scegliamo di usare BaseX, un processore Xquery-XPath open source.

Continue reading “XQuery queries in Java”

Describing media with XML and MPEG-7

La diffusione delle connessioni a banda larga ha agevolato la diffusione di audio e video via web: un esempio eclatante è YouTube! Ma riuscire a trovare un video particolare tra la grossa quantità di dati multimediali sul web è un compito arduo: il valore del dato multimediale dipende da quanto è agevole trovarlo, gestirlo, ed accedere.

Per gestire questa grossa quantità di dati multimediali, sia da parte degli utenti, sia da parte dei sistemi automatici, ci aiuta Mpeg-7: uno standard nato per codificare i contenuti multimediali attraverso la definizione di metadati sui dati multimediali.

I precedenti standard Mpeg-1 (1992), Mpeg-2 (1994), e Mpeg-4 (1999) riguardano la codifica del video. Nel 2001 è stato definito Mpeg-7 che non definisce il modo di codificare un video, ma riguarda la sua metataggatura attraverso un linguaggio XML.
Perché 7? Mpeg-7 permette di definire metadati sui video codificati con Mpeg 1, 2, e 4. Siccome 4+2+1=7, nasce il nome Mpeg-7.

Continue reading “Describing media with XML and MPEG-7”

Very brief introduction to XML

Il linguaggio XML è diventato uno degli elementi fondamentali per la realizzazione di sistemi informativi, indipendentemente dalla tecnologia usata.

Storia

Il World Wide Web Consortium (W3C), in seguito alla guerra dei browser fu costretto a seguire le individuali estensioni al linguaggio HTML. Dovette scegliere quali caratteristiche standardizzare e quali lasciare fuori dalle specifiche ufficiali dell’HTML. Fu in questo contesto che iniziò a delinearsi la necessità di un linguaggio di markup che desse maggiore libertà nella definizione dei tag, pur rimanendo in uno standard.

Il “progetto XML”, che ebbe inizio alla fine degli anni ’80 nell’ambito della SGML Activity del W3C, suscitò un così forte interesse a tal punto che la W3C creò un gruppo di lavoro, chiamato XML Working Group, composto da esperti mondiali delle tecnologie SGML, ed una commissione, XML Editorial Review Board, deputata alla redazione delle specifiche del progetto.

Nel febbraio del 1998 le specifiche divennero una raccomandazione ufficiale con il nome di Extensible Mark-up Language, versione 1.0. Ben presto ci si accorse che XML non era solo limitato al contesto web, ma era qualcosa di più: uno strumento che permetteva di essere utilizzato nei più diversi contesti, dalla definizione della struttura di documenti, allo scambio delle informazioni tra sistemi diversi, dalla rappresentazione di immagini alla definizione di formati di dati.

Continue reading “Very brief introduction to XML”

Very brief introduction to Regular Expressions

Le espressioni regolari sono utili per descrivere la validità di valori, come ad esempio valori di attributi, dati caratteri, e qualsiasi tipo di valore esprimibile con un certo alfabeto.

Il concetto di espressione regolare è un formalismo importante utilizzato, in varie forme, in svariate applicazioni… ad esempio nei linguaggi di schema (come DTD di XML) per descrivere sequenze di elementi o caratteri. I linguaggi regolari sono utilizzati in molte altre aree dell’informatica oltre a XML, dall’elaborazione del testo e del linguaggio naturale alla verifica formale dei componenti hardware.

Potrebbe essere necessario, ad esempio, vincolare un valore ‘data’ in modo tale da rispettare il formato dd-mm-yyyy, ovvero sia composto da due cifre per il giorno, seguite da due per il mese e quattro per l’anno, tutto separato da un segno meno “-”. Alternativamente possiamo specificare che un certo valore deve essere un numero intero.

Chiamiamo Σ un alfabeto consistente in un insieme di atomi, che tipicamente sono caratteri Unicode o nomi di elementi. Un’espressione regolare su Σ è costruita in base alle seguenti regole:

Continue reading “Very brief introduction to Regular Expressions”

Matrix types and Storage methods

In mathematics, a matrix (plural matrices) is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. The individual items in a matrix are called its elements or entries.
In computer science the term “matrix” refers to a multidimensional array, that is a systematic arrangement of objects, usually in rows and columns.

In questo articolo si illustra i vari tidi di matrice, e i vari tipi di memorizzazione di matrice. Dal modo in cui sono collocati gli elementi all’interno di una matrice, possiamo distinguere vari tipi

Continue reading “Matrix types and Storage methods”