Linux® vs Windows®: um benchmark com
algoritmos de ordenação
Negreiros, J1, Painho, M2, Lopes, I3, Malta, P4
[email protected], [email protected], ilí[email protected], [email protected]
1
Instituto Superior de Línguas e Administração, Quinta do Bom Nome, Lisboa, Portugal
Instituto Sup. Estatística Gestão Informação-UNL, Campus de Campolide, Lisboa, Portugal
3
Instituto Superior de Gestão de Santarém, Complexo Andaluz, 2001-904, Santarém, Portugal
4
Universidade Lusófona, Campo Grande 376, Lisboa, Portugal
2
Resumo: Normalmente, os algoritmos apresentam como função resolver um
problema específico a partir de um conjunto predefinido de passos singulares.
Neste artigo, pretende-se utilizar cinco algoritmos de ordenação (Heap,
Inserção, Selecção, Quick e Shell) como ferramenta de comparação de
performance entre o sistema operativo SuSe Linux® e o Windows® XP
Professional e, implicitamente, os respectivos compiladores (gcc e cl).
Paralelamente, é apresentado o estado da arte relativo à complexidade
logarítmica, tipos de algoritmos e outros estudos de benchmark envolvendo
outros factores como o TCO (Total Cost of Ownership).
Linux®; Windows®; Benchmark; Algoritmos de ordenação;
Compiladores C/C++.
Palavras-chave:
1. Complexidade Algorítmica: Introdução
Os algoritmos são uma parte diária na nossa vida reflectindo-se, por exemplo,
em pesquisas operacionais, acessos na Web ou problemas de optimização.
Genericamente, um algoritmo pode ser visto como uma sequência de acções
executáveis para a obtenção de uma solução relativo a um determinado problema.
Na medição da execução de um algoritmo, é comum definir uma função de custo
ou função de complexidade f(t,s,n) em que t e s representam o tempo e o espaço de
memória necessários para executar uma sequência de passos para a resolução de um
problema de dimensão n (quantidade de input). Assim, é necessário distinguir três
cenários: A) Melhor caso – Corresponde ao menor tempo de execução sobre todas as
possibilidades de input de tamanho n; B) Pior caso – Corresponde ao maior tempo de
execução; C) Caso médio – Corresponde à média dos tempos de todas as entradas de
tamanho n. Logicamente, o tempo de resposta de um algoritmo pode ser bastante
diverso e por isso, a análise do comportamento da distribuição de probabilidades
sobre o conjunto do input é de difícil estimação.
Se para valores suficientemente pequenos de n qualquer algoritmo apresenta um
pequeno custo para ser executado, mesmo para algoritmos ineficientes, a escolha do
algoritmo é fundamental para grandes valores de input de modo a obter-se uma
análise assintótica O(n) ou função de complexidade do algoritmo em tempos
razoáveis. Em termos de literatura clássica [Preiss, 2001, Loudon, 1999],
independentemente do tipo de paradigma associado aos algoritmos (indução,
recursividade, tentativa e erro, divisão e conquista, balanceamento, programação
dinâmica, algoritmos gulosos e aproximados), tem-se a seguinte classificação de
classes de função de complexidade:
Constante f(n)=O(1): O tempo de resolução do algoritmo é independente da
quantidade de input.
Logarítmica f(n)=O(log n): O tempo de execução varia relativamente pouco
aquando um aumento significativo da quantidade de registos à entrada.
Linear f(n)=O(n): O tempo de resposta depende directamente da quantidade de
dados.
Linear logarítmica f(n)=O(n log n): A solução do problema é linearmente
complexa mas acentuando-se à medida que o n cresce.
Quadrática f(n)=O(n2): Sempre que os dados de input duplicam, o tempo da
solução quadruplica.
Cúbica f(n)=O(n3): Sempre que a quantidade de input duplica, o tempo de
execução é multiplicada por 8.
Exponencial f(n)=O(2n): Quando o n dobra, o tempo de execução fica elevado
ao quadrado.
Factorial f(n)=O(n!): O pior dos problemas para solucionar pois o conceito da
força bruta pode requerer um tempo virtualmente infinito para a obtenção da
solução óptima. Imagine uma problema deste tipo com n=50. O tempo de
resposta seria 3.0414E64 unidades de tempo.
Por curiosidade, Garey e Johnson [1979] apresentam o seguinte quadro na qual
mostra a razão de crescimento de várias funções de complexidade para tamanhos
diferentes de n.
Quadro 1 – O tempo de execução varia entre milésimos de segundo e biliões de séculos.
Função
de
custo
n
n2
n3
n5
2n
3n
10
20
0.00001s
0.0001s
0.001s
0.1s
0.001s
0.059s
0.00002s
0.0004s
0.008s
3.2s
1s
58min
Tamanho n
30
40
0.00003s
0.0009s
0.027s
24.3s
17.9min
6.5anos
0.00004s
0.0016s
0.64s
1.7min
12.7dias
3855séc
50
60
0.00005s
0.035s
0.125s
5.2min
35.7anos
108séc
0.00006s
0.0036s
0.316s
13min
366séc
1013séc
Uma outra visão interessante e apresentado por Ziviani [2004] é o efeito causado
pelo aumento da velocidade dos computadores sobre os algoritmos. Repare-se que
para um aumento de 1000 vezes na velocidade de computação este apenas resolve 10
vezes mais rápido, se na presença de um algoritmo de complexidade O(2 n).
Quadro 2 – Influência do aumento de velocidade de computação no tempo de resolução de
problemas pertencentes a várias classes.
Função de custo
de tempo
N
n2
n3
Computador
actual
t1
t2
t3
Computador 100
vezes + rápido
100 t1
10 t2
4.6 t3
Computador 1000
vezes + rápido
1000 t1
31.6 t2
10 t3
Infelizmente, não existe um conjunto completo de regras para analisar programas
[Aho, Hopcroft, Ullman, 1983]. Por exemplo, o tempo de escrita num disco ou de
leitura de uma banda magnética não pode ser considerado como O(1). Se o programa
possui funções não recursivas associado a condições de execução, o cálculo torna-se
mais complicado pois não se sabe, à partida, o número total de vezes que esse
procedimento vai ser executado. Só o próprio tempo de execução da condição de teste
é constante. Se a função é recursiva então é fundamental o recurso a equações de
recorrência para se calcular o tipo de complexidade associado. Baseado no trabalho de
Ziviani [2004], imagine o seguinte procedimento recursivo de pesquisa de um
determinado número inteiro numa possível tabela unidimensional com z elementos:
Naturalmente, a complexidade desta função de pesquisa depende de cada uma
das instruções em causa. Assim, a primeira e a segunda instrução tem uma
complexidade O(1) enquanto a terceira é de ordem O(n). Contudo, o principal
problema de calculo é a instrução recursiva Pesquisa(n/3). Considere a equação de
recorrência para o bloco else begin...end: T(n)=n+T(n/3). Se n=1 então a
complexidade T(1)=1. Globalmente, tem-se T(n)=n+T(n/3) com T(n/3)=n/3+T(n/3/3).
Consequentemente, T(n/3/3)=n/3/3+T(n/3/3/3) e assim sucessivamente. Adicionando
todos estes termos, a complexidade do problema inicial significa uma complexidade
O(n) dado que
T ( n)
(1/ 3)i
n
i 0
1
n
1
1
3
3n
2
.
Embora a complexidade de um algoritmo seja um factor importante para
determinar o quão eficiente este pode ser, o facto é que o tempo de resposta de um
algoritmo é um parâmetro extremamente importante a ter em consideração em
qualquer análise de benchmark. Preiss [2001] confirma esta afirmação usando código
Java no problema do somatório da série geométrica
n
xi (ver figura 1). Note que
i 0
diferentes estratégias podem implicar diferentes performances. Como alternativa, este
artigo apresenta como objectivo primário uma comparação de performance de dois
sistemas operativos de 32 bits, SuSe Linux® e Windows XP® Professional, e
respectivos compiladores (gcc 4.0.2 e C/C++ 14.00.5) baseado no tempo de resposta
na resolução de cinco algoritmos de ordenação.
Figura 1 – Tempo de processamento versus quantidade de input relativo ao algoritmo somatório
da série geométrica perante três estratégias diferentes.
2. Linux® VS Windows®: Estado da Arte
Seguindo a luta actualmente existente entre estes dois sistemas operativos (SO)
na conquista e reconversão de clientes, a realidade é que existem testes de
comparação de performance para todos os gostos. Contudo, é de evitar análises
independentes com a marca “conducted at the request of Microsoft ®” [Trezentos,
2005].
Mindcraft® é uma empresa independente que se dedica a realizar testes de
comparação entre diversos softwares e hardware. Num desses estudos, utilizou-se as
ferramentas de benchmark Netbench® 5.01 para analisar a performance de gestão de
acesso a ficheiros em termos de servidor para n clientes (usou-se a plataforma
Samba® 2.03 em termos de Linux®) e o Webbench® 2.0 para testar o servidor Web
(Apache® 1.3.6 para Linux®). Em termos de hardware, o servidor usado foi o Dell ®
PowerEdge 6300 com 4 processadores. Baseado nos seus testes de Junho de 1999
entre o Windows® NT Server 4.0 e o Red Hat® Linux 5.2, esta fonte claramente
mostrou uma performance de superioridade em termos de servidor de ficheiros do
Windows®: 2.43 mais rápido. A mesma análise se verifica quando testados os
respectivos servidores Web: 2.58.
A empresa VeriTest® confirma esta superioridade em termos de servidor de
ficheiros quando em Junho de 2004 comparou o Windows 2003 Server ® com o
Samba® 3.0 num servidor HP® DL 380. O teste indicou uma melhor performance de
requests de ficheiros na ordem dos 46%.
Contudo, o Linux® é reconhecido pela sua fiabilidade. Um servidor pode estar
em funcionamento durante vários anos sem qualquer problema. Ao invés, todos os
utilizadores de Windows® estão familiarizados com o ecrã “blue screen of death”.
Além disso, é muito difícil manter o sistema sem fragmentação por um período longo
dado ser um excelente devorador de recursos físicos do sistema [Bruce, Stokely,
2001]. Em termos de segurança, pouco se sabe da construção interna da plataforma
Windows® pois é código fechado. No entanto, existem empresas que sofrem
diariamente danos por motivos de buracos de segurança [Bruce, Stokely, 2001].
O facto do Linux® ser código aberto também constitui um problema por si só.
Analise-se a falta de device drivers para alguns dispositivos físicos. Esta situação
deve-se à não intenção dos fornecedores de devices em fornecer o código original
provocando assim um problema ainda maior para os clientes. A mesma situação se
passa com a criação de aplicações pessoais que podem compilar no Red Hat® e não no
Slackware®. Claramente, a falta de aplicações comerciais (ferramentas Macromedia®,
por exemplo) é muito mais grave para o Linux® do que para a plataforma Windows®.
Factualmente, o famoso TCO (Total Cost of Ownership) inicial é mais baixo
para o Linux® embora, no longo prazo, é uma situação que ainda requer mais estudos
detalhados a nível financeiro. É importante não esquecer que a manutenção de um
serviço informático é um pesadelo ainda maior que a compra deste. Actualmente, é
mais dispendioso manter um administrador de Linux® do que Windows®. Por outro
lado, é mais trabalhoso manter um servidor Windows ® do que Linux® [Trezentos,
2005].
Quadro 3 – Solução Linux® standard versus Microsoft® em termos de TCO. Os custos
assinalados representam dólares australianos e incluem diversos serviços como antivírus, base
de dados, mail server, firewall e custos de pessoal de administração [Cybersource, 2004].
Utilizando a actual infraestrutura
Comprando uma nova
estrutura de hardware
Microsoft®
$1,066,712
Linux®
$682,090
%
36%
$1,366,833
$1,012,260
26%
É também possível encontrar benchmarks de TCO que contraria as conclusões
anteriores. Por exemplo, a Bearing Point [2004] apresenta um estudo equiparado ao
anterior entre o Windows® 2003 Server e o Red Hat® Enterprise Linux 3. De acordo
com esta análise, os custos totais são relativamente iguais ao longo de um período de
5 anos.
Utilizando um CPU AMD Athlon 64 3800+ e o famoso jogo Doom 3,
testaram-se quatro placas de vídeo (ABIT GeForce 3 Vio com 64MB, ABIT GeForce
4 Ti 4600 com 128MB, NVIDIA GeForce FX 5900 Ultra com 256MB e GeForce
6800GT AGP com 256 MB) em função de dois sistemas operativos: Gentoo Linux ® e
o Windows® XP SP2. De acordo com www.linuxhardware.org [2005], o Windows®
consegue uma performance mais rápida que o Linux®. Usando a placa de vídeo mais
sofisticada, por exemplo, a diferença do número de frames por segundo varia entre
20-36% mais rápido (naturalmente, maior definição no ecrã) e com placas de vídeo
mais lentas, esta margem pode atingir 50%.
Um outro facto sociológico interessante é o reaparecimento do Unix ®, um
sistema operativo criado em C na AT&T ® em 1969, na forma de Linux® devido a um
jovem Finlandês que se entreteu a realizar um sistema alternativo ao actual vigente
Windows® e que está a tornar-se num caso muito interessante, nomeadamente em
termos de servidores de base de dados, E-mail, FTP, Newsgroups e WWW. Casos
como a cidade de Munique, a administração Chinesa ou a região administrativa
espanhola da Extremadura, que estão a viver tempos de reconversão, poderão ser
casos de alguma preocupação para o Golias Microsoft®.
3. Algoritmos de Ordenação
Ordenação significa arrumar um conjunto de elementos numa determinada
ordem (ascendente ou descendente). Teoricamente, os métodos de ordenação são
classificados em dois grupos: A) Interna (caso o ficheiro ou estrutura a ser ordenado
resida em RAM); B) Externa (caso o arquivo esteja armazenado em disco, DVD ou
fita magnética, por exemplo).
Os algoritmos aqui considerados apenas focam o primeiro grupo e funcionam
sobre uma parte do registo designada chave (este é por sua vez um campo de uma
estrutura específica). O princípio da distribuição (como a ordem de um baralho de
cartas com joker, reis, damas, valetes e ases) não foi considerado. Assim, apresentamse nas seguintes subsecções os cinco métodos de ordenação que servirão de
ferramenta de teste.
3.1. Heap
O algoritmo Heap consiste numa árvore binária completa (cada nó tem dois e
apenas dois filhos) com as seguintes propriedades específicas de ordenação: A) Todos
os nós descendentes de um determinado nó N são menores ou iguais ao conteúdo de
N; B) Todos os nós ascendentes de N são maiores ou iguais ao conteúdo de N; C)
Consequentemente, todos os nós são menores que a raiz.
Uma característica curiosa desta metodologia consiste na sua representação em
vectores. Os filhos de um nó i estão nas posições 2i e 2i+1 (caso existam) e o pai de
um nó i está na posição (int)i/2. Assim, por exemplo, a raiz está no índice zero do
vector (o maior valor de todos os elementos) e os seus descendentes directos estão no
índice 1 e 2.
3.2. Inserção
Esta metodologia consiste em percorrer sequencialmente o vector a ordenar
elemento por elemento, deslocando-o e inserindo-o na posição correcta. Inicialmente,
são formados dois blocos: Um de valores ordenados e outro de não ordenados. Este
algoritmo consiste em passar sucessivamente os valores de um bloco para o outro.
Assim e caso os registos sejam inseridos sequencialmente por uma determinada
aplicação, este procedimento torna-se muito útil.
3.3. Selecção
Apesar de ser um algoritmo muito ineficiente para listas de valores muito
extensas, este método simples de ordenação poderia ser apresentado do seguinte
modo: A) Seleccionar o menor dos valores e trocá-lo por v[0]; B) Seleccionar o
menor entre os restantes e trocá-lo por v[1]; C) Realizar sucessivamente os passos
anteriores até todos os elementos estarem ordenados.
3.4. Quick
Este algoritmo funciona do seguinte modo: Dado um vector de elementos, T[n],
escolhe-se arbitrariamente um pivot x tal que todos os elementos menores que x ficam
do lado esquerdo do vector enquanto os elementos maiores fiquem do lado direito.
Normalmente, esse pivot costuma ser a mediana ou a média do conjunto de elementos
de modo a obter uma performance equilibrada. Ao realizar-se este procedimento, a
lista não fica necessariamente ordenada na primeira iteração. Em termos
computacionais, portanto, o algoritmo passa pelas seguintes operações: A) Percorrer o
vector T a partir da esquerda até que T[i]>=x; B) Percorrer o vector a partir da direita
até que T[j]<=x; C) Trocar T[i] com T[j]; D) Continuar este processo até que os
índices i e j se cruzem.
Realizado estes quatro passos, o vector T[Esq...Dir] está dividido de tal forma
que: A) Os valores T[Esq], T[Esq + 1],..., T[j] são menores ou iguais a x; B) Os
valores T[i], T[i + 1],..., T[Dir] são maiores ou iguais a x (com i=j+1).
Utilizando a estratégia da divisão e conquista, basta agora dividir a tabela dada,
T[n]=T[Esq...Dir], em duas tabelas tal que T[n]=T[Esq...Dir]=T[Esq...j]+T[i...Dir].
Quando o cardinal do domínio [Esq...j] for zero ou um, então tem-se a primeira
condição de paragem activa. Analogamente, quando o cardinal do domínio [i...Dir]
for zero ou um, tem-se a segunda condição de paragem activa o que significa que este
ramo do vector já foi ordenado.
3.5. Shell
Metodologia proposta em 1959, este é uma extensão do algoritmo da ordenação
de Inserção e que se resume a dar um valor de salto para o teste de inserção. Como já
foi referido anteriormente, no método de Inserção existe uma troca de itens adjacentes
quando se está à procura do ponto de inserção na sequência destino. No caso do Shell,
a troca dos registos estão separados h posições de tal forma que o vector está
reorganizado ao nível h.
4. Análise Comparativa
Na escolha de um algoritmo de ordenação interna, este procedimento deve
considerar o tempo de resposta da metodologia em causa como factor crítico. Sendo n
o número de registos do arquivo a ordenar, as medidas de complexidade relevantes
nos diversos métodos são o número de comparações entre chaves, C(n), e o número
de movimentações de itens dentro do arquivo, M(n). Claramente, o uso económico da
memória disponível é também um requisito primordial na ordenação interna.
Esta secção pretende relacionar e comparar os métodos de ordenação
anteriormente referidos em vectores de diferentes dimensões e em função de dois
sistemas operativos: Windows® XP Professional SP2 e Linux® SuSex 10. Considerase que ambos os sistemas operativos têm apenas os serviços mínimos para estes
estarem operacionais. Mais, o computador (Pentium III a 1GHz com 1GB de RAM)
deste benchmark é o rigorosamente o mesmo (a memória livre rondava 630MB em
ambos os SO). A mesma situação acontece com o código C dos cincos algoritmos.
Para facilitar a análise, todos os vectores considerados estavam ordenados
descendentemente (o que significa que foi apenas simulado uma só vez para cada
dimensão do vector a ordenar). Pretende-se uma ordenação ascendente. A compilação
dos mesmos programas foi realizada pelo Microsoft® Visual Studio .Net 2.0 e pelo
GNU C/C++ 4.0.2, no caso do SuSe® 10. É ainda de referir que no código usado, não
foram usadas nenhumas threads como não foi usado qualquer outro software de
medida de performance. Finalmente, o tempo de resposta de cada um dos algoritmos
foi calculado pela diferença do tempo de resolução através da chamada da seguinte
função C:
Com base na figura 4, apresentam-se os seguintes comentários:
Para todas as formas de algoritmos de ordenação considerados, o seu tempo
de resolução é geralmente menor para o ambiente Linux®. Contudo, esta
regra é fatalmente quebrada quando o número de registos a ordenar atinge a
ordem dos 300 milhões (Shellsort e Heapsort), 400 milhões (Quicksort) e 1
milhão (Seleção).
No método de Shellsort, Heapsort, Quicksort e Seleção, a diferença do
tempo de resposta entre o Linux® e o Windows® aumenta directamente com
a quantidade de input considerada. Inexplicavelmente, este padrão não se
verifica quando o vector a ordenar atinge as maiores dimensões consideradas
neste estudo.
Considerando o método de Inserção, a plataforma Windows® consegue
superar a performance do SuSe Linux® numa proporcionalidade que atinge
4.5 vezes. Esta proporcionalidade desce para 2 (Quicksort), 1.97 (Heapsort)
e 1.8 (Shellsort).
Contrariando a conclusão anterior, o SuSe Linux® apresenta um tempo de
resposta inferior com a ordenação de Seleção, independentemente da
dimensão do vector a ordenar. De facto, a proporcionalidade referida no
ponto anterior inverte para 3.86 vezes mais lento (Windows®).
Analisando a imagem seguinte, verifica-se uma tendência de um
comportamento linear positivo no tempo de resposta dos algoritmos, em
geral.
Performance (métodos de ordenação)
300
ShellWindow s
200
150
100
Segundos
250
50
ShellLinux
QuickWindow s
QuickLinux
HeapWindow s
HeapLinux
0
10
30
50
60
100
200
Dim ensão do vector a ordenar
(m ilhões)
Figura 2 – Análise de comparação de resultados dos cinco algoritmos de ordenação para
dimensões inferiores a 200 milhões de registos.
É ainda de notar diferenças substanciais entre os diversos métodos para um
vector de 300 milhões de valores inteiros.
Performance (métodos de ordenação)
20000
ShellWindow s
Segundos
15000
ShellLinux
QuickWindow s
10000
QuickLinux
HeapWindow s
5000
HeapLinux
0
300 Milhões
Dim ensão do vector a ordenar
Figura 3 – Análise de comparação de resultados dos cinco algoritmos de ordenação
para uma dimensão de 300 milhões de registos.
Retirando a análise de todos os algoritmos para a respectiva maior dimensão
do vector a ordenar, verificou-se um outlier no comportamento destes
algoritmos. No algoritmo de Inserção, quando a dimensão do vector é de 100
mil registos, o tempo de resposta em Windows® é menor que em Linux®.
Quer em Windows® XP quer em SuSe Linux®, as metodologias Quicksort e
Heapsort são os algoritmos mais rápidos de ordenação, confirmando as
afirmações comuns da literatura especializada. Esta diferença de
performance com os restantes métodos verifica-se, nomeadamente, para
vectores com médias e grandes dimensões.
Os métodos com pior performance, independentemente do SO, são os
métodos de Inserção e Seleção.
Figura 4 – Comparação de tempos de resposta das cinco metodologias de ordenação.
5. Conclusão
Nesta análise prática sobre a performance de algoritmos de ordenação em função
do sistema operativo e dos respectivos compiladores, este artigo não pretende indicar
qual o melhor sistema operativo na sua globalidade. Como já foi referido
anteriormente e embora estes sejam concorrentes directos, ambos os SO tem um
historial e uma realidade bastante diferente. Mais, esta análise aqui descrita é apenas e
simplesmente mais uma outra análise de bechmark a juntar a tantos outros testes já
realizados por outras empresas e particulares. De qualquer modo, os autores garantem
o factor de imparcialidade e honestidade nos resultados finais apresentados.
Contudo e fundamentalmente, estes testes indicam claramente que considerando
o tempo de resolução de uma ordenação de um vector, o mesmo código C torna-se
mais rápido quando em plataforma Linux® do que em Windows® para vectores com
dimensão inferior a 200 milhões (Shell, Quick e Heap). Contrariamente, a situação
inverte-se completamente quando a dimensão cresce para 300 milhões. Em relação ao
porquê deste comportamento, é uma questão que fica em aberto para especialistas de
compiladores e sistemas operativos.
Colateralmente, as metodologias de pior performance, Inserção e Seleção,
apresentam piores resultados em ambiente Windows ® do que em Linux®,
independentemente da dimensão considerada. Será que existe alguma dimensão
superior ainda não testada que inverta este padrão? É ainda de referir a falta da
medição da performance recorrendo ao uso de threads na codificação dos algoritmos
em causa, um outro factor importante a considerar numa próxima análise de
benchmark.
Agradecimentos
Pelo apoio prestado neste artigo, os presentes autores gostariam de agradecer aos
alunos António Vargas, Telma Filipa e Jefra Araújo do actual 2º ano de Engenharia
Informática da Universidade Lusófona.
Referências
Aho, A., Hopcroft, J., Ullman, J. (1983). Data Structures and Algorithms. AddisonWesley.
Bearing Point. (2004). http://www.bearingpoint.com.
Cybersource. (2004). http://www.cybersource.com.au/about/linux_vs_windows_tco_
comparison.pdf
Garey, M., Johnson, D. (1979). Computers and Intractability A Guide to the Theory
of NP-Completeness. Freeman Press.
Loudon, K. (1999). Mastering Algorithms with C. O’Reilly Media, Inc.
Mindcraft, 1999. www.mindcraft.com/whitepapers.
Preiss, B. (2001). Estruturas de Dados e Algoritmos. Editora Campus.
Trezentos, P. (2005). Linux para PCs - Caixa Mágica. FCA-Lidel.
Veritest. (2004). www.veritest.com.
Ziviani, N. (2004). Projecto de Algoritmos (2ª edição). Pioneira Thomson Learning.