Uma instância de um problema computational é um caso particular do problema, com valores específicos dos parâmetros (isto é, dos dados de entrada) do problema. Cada conjunto de dados do um problema define uma instância.
[A palavra instância é um neologismo importado do inglês. Ela está sendo empregada aqui no sentido de exemplo, espécime, amostra, ilustração.)
Considere, por exemplo, o seguinte problema: dados números a, b, e c, encontrar um número x tal que ax2 + bx + c = 0. (Os números a, b, e c são os parâmetros do problema.) Uma instância desse problema consiste em encontrar x tal que 1x2 + 1x − 2 = 0. Outra instância consiste em encontrar x tal que 1x2 − 2x + 1 = 0. Ainda outra instância pede x tal que 123x2 − 456x + 789 = 0.
Uma solução de uma instância de um problema computational é qualquer objeto que satisfaz o enunciado da instância. Tome, por exemplo, o problema da nota acima; então
Uma solução de um problema é um algoritmo que resolve o problem. Em outras palavras, para quaisquer valores dos parâmetros, o algoritmo produz uma solução da correspondente instância (ou avisa que a instância não tem solução). Para o problema enunciado acima, um algoritmo pode ser resumido pela fórmula (−b ± √. ) / 2a
Um algoritmo é correto se cumpre suas promessas, ou seja, se faz o que promete fazer. Em outras palavras, um algoritmo é correto se resolve o problema que promete resolver.
Elegante é mais ou menos o mesmo que simples, limpo, bonito, econômico. Um algoritmo (ou programa) elegante não tem código supérfluo nem variáveis desnecessárias. Um algoritmo elegante não trata os casos especiais do problema em separado.
Um algoritmo muito esperto, intricado, emaranhado, feio, confuso, é deselegante.
A experiência mostra que algoritmos elegantes tendem a ser eficientes, e algoritmos eficientes são em geral elegantes. Além disso, processos iterativos elegantes têm invariantes mais simples.
Um algoritmo é eficiente se não perde tempo à toa. Em outras palavras, um algoritmo é eficiente se for mais rápido que outros algoritmos para o mesmo problema.
Embora essa definição
seja adequada para uso informal,
ela esconde sérias dificuldades:
mais rápido que outrosdeveria incluir não só os algoritmos já conhecidos para o problema, como também os que ainda não foram descobertos.
As definições a seguir referem-se ao consumo de tempo
(ou seja, ao tempo de resposta
)
de algoritmos.
Em todas as definições,
n é o tamanho de uma instância do problema que o algoritmo resolve,
ou seja,
o parâmetro que mede o tamanho da entrada
do algoritmo.
(Se a entrada for um grafo, por exemplo,
então n é o
tamanho do grafo.)
Um algoritmo é
Esses termos referem-se, em geral, ao consumo de tempo no pior caso.
Um tipo-de-dados (= data type) é um conjunto de valores munido de um conjunto de operações. Algumas operações transformam valores em outros valores. Outras, associam números a valores ou conjuntos de valores. Eis alguns tipos-de-dados básicos da linguagem C:
inteiro) é INT_MIN, . . . , −2, −1, 0, 1, 2, . . . , INT_MAX. Os valores das constantes INT_MIN e INT_MAX estão definidos na interface da biblioteca limits.h.
Entre as operações sobre esses valores destacam-se as de comparação ( <, <=, ==, >, >= ) e as aritméticas ( +, -, *, / ). Cada operação aritmética recebe dois ints e devolve um int como resultado. O efeito de uma operação aritmética é às vezes diferente do pregado pela matemática pois pode ocorrer overflow em alguns casos e truncamento em outros. Por exemplo, 9 / 2 vale 4 (e não 4.5). Outro exemplo: se o conjunto de valores é o intervalo [−32768,+32767] então 32767 + 1 vale −32768 e não 32768.
As operações usuais sobre esses valores são indicadas por <, <=, ==, >, >=, + e -. Em uma implementação ideal do tipo-de-dados, o valor da expressão 127 + 2 seria −127 e não 129. Na linguagem C, entretanto, o valor da expressão x + y abaixo é 129, pois a expressão é calculada em aritmética int.
char x, y, z; x = 127; y = 2; z = x + y; // o valor de z é -127
números reais) é mais difícil de descrever.
Você pode definir os seus próprios tipos-de-dados recorrendo ao typedef. O seguinte tipo-de-dados, por exemplo, é muito útil para representar valores booleanos:
typedef enum {FALSE, TRUE} boolean;
(Se bem que esse tipo-de-dados já está definido na interface stdbool.h.) Outro tipo-de-dados muito usado é string (ou cadeia de bytes):
typedef char *string;
Um exemplo mais especializado: o tipo-de-dados ponto representa as coordenadas de pontos no plano:
typedef struct { double x; double y; } ponto;
As operações sobre valores desse tipo são derivadas das operações sobre doubles. Você também pode acrescentar suas próprias operações, como por exemplo a operação que produz a distância euclideana entre dois pontos.
reais
Computadores não sabem o que são números reais no sentido matemático do termo. Computadores conhecem apenas um pequeno conjunto de números racionais.
O mundo da computação
chama de reais
os número do tipo
float e
double
(como 0.31415926 × 101,
por exemplo)
representados em notação
ponto flutuante
.
Todos esses números são racionais.
Uma fila de prioridades (= priority queue) é qualquer tipo-de-dados dotado de duas operações:
É fácil implementar a fila de prioridades de modo que uma dessas operações seja rápida. É mais difícil inventar uma implementação em que ambas as operações são rápidas.
A definição acima é a de uma fila de prioridades de máximo
.
Não é difícil adaptar essa definição
para filas de prioridades de mínimo
.
Não confunda a estrutura de dados heap com a área da memória do computador usada para alocação dinâmica. (Veja o artigo Heap overflow and Stack overflow no GeeksforGeeks.) Os dois conceitos são independentes.
Números naturais podem ser escritos em notação binária (base 2), octal (base 8), decimal (base 10), e hexadecimal (base 16).
Na notação binária, os dígitos são 0 e 1. Na notação octal, os dígitos são 0 1 .. 7. Na notação decimal, os dígitos são 0 1 .. 9. Na hexadecimal, os dígitos são 0 1 .. 9 A B .. F.
Por exemplo, o número setenta e nove
é representado por
79
em notação decimal,
pois setenta e nove é
7×10 + 9.
O mesmo número é representado por
1001111
em notação binária,
pois setenta e nove é 1×26 + 1×23 + 1×22 + 1×21 + 1×20.
O mesmo número é representado por
117
em notação octal
(pois setenta e nove é 1×8² + 1×8¹ + 7),
e por 4F
em notação hexadecimal
(pois setenta e nove é
4×16¹ + F).
A linguagem C adota a seguinte convenção:
Por exemplo, 0117 é a representação octal e 0x4F é a representação hexadecimal de setenta e nove.
Sinais diacríticos são os acentos e o til que são colocados sobre vogais (produzindo á, ã, é, etc.) e a cedilha que é colocada sob a letra c (produzindo ç).
O padrão C99 da linguagem C (e os padrões posteriores) permite letras com diacríticos em nomes de variáveis e funções. Mas as letras com diacríticos precisam ser representados (no arquivo-fonte do seu programa) por meio de seus números Unicode. Por exemplo, se quiser que o nome de uma variável seja preço, você precisa digitar pre\u00E7o. Essa complicação torna o recurso inútil na prática…
No caso de constantes-caracteres, entretanto, as coisas são mais simpáticas: letras com diacríticos podem ser digitadas diretamente, desde que a variável de ambiente LC_CTYPE do seu sistema tenha valor pt_BR.UTF-8 ou en_US.UTF-8. (Digite locale no terminal para saber o valor dessa variável no seu sistema Linux.) Por exemplo,
char mensagem[11] = "Atenção!"; printf( "%s\n", mensagem);
produz
Atenção!
(Note que a string "Atenção!" ocupa 11 bytes pois ç e ã ocupam 2 bytes cada na codificação UTF-8.)
Até recentemente, os bytes 10000000 a 11111111 eram usados para representar letras com sinais diacríticos e alguns outros caracteres. Essa correspondência é definida pela tabela ISO-LATIN-1, também conhecida como ISO-8859-1.
Com a popularização do código UTF-8, a tabela ISO-LATIN-1 caiu em desuso. Assim, os bytes cujo primeiro bit é 1 (unsigned chars 128 a 255) deixaram de representar caracteres.
O código UTF-8 representa cada caractere por uma sequência de 1 a 4 bytes. O esquema de codificação foi cuidadosamente projetado para permitir a decodificação de uma sequência de bytes e ser compatível com o código ASCII.
Os primeiros 128 caracteres da lista Unicode (números U+0000 a U+007F) são representados por 1 byte cada. Os 1920 caracteres seguintes (números U+0080 a U+07FF) são codificados em 2 bytes. E assim por diante.
A tabela abaixo mostra a estrutura do código UTF-8. Na coluna esquerda, temos os intervalos de números Unicode, em notação hexadecimal. Na coluna direita, em notação binária, os intervalos dos correspondentes bytes do código:
números Unicode byte 1 byte 2 byte 3 byte 4 00000000 .. 0000007F 0xxxxxxx 00000080 .. 000007FF 110xxxxx 10xxxxxx 00000800 .. 0000FFFF 1110xxxx 10xxxxxx 10xxxxxx 00010000 .. 0010FFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Agora, a mesma tabela escrita em notação decimal:
0 .. 127 000..127 128 .. 2047 192..223 128..191 2048 .. 65535 224..239 128..191 128..191 65536 .. 1114111 240..247 128..191 128..191 128..191
Finalmente, a mesma tabela escrita em notação hexadecimal:
0 .. 7F 00..7F 80 .. 7FF C0..DF 80..BF 800 .. FFFF E0..EF 80..BF 80..BF 10000 .. 10FFFF F0..F7 80..BF 80..BF 80..BF
Primeiro, um rascunho muito grosseiro:
// Esta função decide se a string s contém uma // sequência bem-formada de parênteses e colchetes. bemFormada (string s) { para cada elemento c de s faça { se c ≡ ')' então se topo da pilha tem '(' então desempilhe senão se c ≡ ']' então se topo da pilha tem '[' então desempilhe senão empilhe c } se pilha vazia então devolvasimsenão devolvanão}
Agora um rascunho melhor, que já poderia ser traduzido em código:
bemFormada (string s) { aloque espaço para uma pilha de bytes para cada byte c de s faça { se c ≡ ')' então se pilha não vazia e topo da pilha é '(' então desempilhe senão devolvanãosenão se c ≡ ']' então se pilha não vazia e topo da pilha é '[' então desempilhe senão devolvanãosenão empilhe c } se pilha vazia então devolvasimsenão devolvanão}
Eis um rascunho em pseudocódigo da função infixaParaPosfixa. Primeiro um rascunho grosseiro:
// Esta função recebe uma expressão infixa inf // e devolve a correspondente expressão posfixa. infixaParaPosfixa (string inf) { para cada caractere c de inf faça { dependendo do valor de c coloque c na pilha ou coloque c na expressão posfixa ou transfira caracteres da pilha para a posfixa } coloque '\0' na expressão posfixa devolva posfixa }
Agora um rascunho bem mais exato e completo:
infixaParaPosfixa (string inf) { aloque espaço para string posf aloque espaço para uma pilha de bytes // primeiro byte de inf é um '(' empilhe o primeiro byte de inf para cada byte c de inf faça { se c ≡ '(' então empilhe c senão se c ≡ ')' então enquanto o topo da pilha for diferente de '(' desempilhe x coloque x em posf desempilhe x senão se c é '+' ou '-' então enquanto o topo da pilha for diferente de '(' desempilhe x coloque x em posf empilhe c senão se c é '*' ou '/' então enquanto topo da pilha diferente de '(' de '+' e de '-' desempilhe x coloque x em posf empilhe c senão coloque c em posf } coloque '\0' em posf devolva posf }
Eis um rascunho do algoritmo das distâncias:
// Recebe matriz A das interligações // entre 6 cidades. Devolve vetor d tal que // d[i] é a distância da cidade c à cidade i. distancias (matriz A[0..5][0..5], int c) { d[c] = 0 coloque c na fila enquanto a fila não estiver vazia { seja i a primeira cidade da fila para cada cidade j vizinha de i faça se d[j] ainda não foi definida então d[j] = d[i] + 1 coloque j na fila tire i da fila } devolva d }
Eis um rascunho, em pseudocódigo, da função peneira:
peneira (vetor v[1..m]) {
p = 1
enquando 2p ≤ m faça
seja f o filho mais valioso de p
se v[p] ≥ v[f] então pare
senão troque v[p] com v[f]
senão p = f // p desce no heap
}
Eis um rascunho, em pseudocódigo, da função heapsort
// Rearranja v[1..n] em ordem crescente. heapsort (v[1..n]) { transforme v[1..n] em heap para m = n, n−1, ... , 2 faça troque v[1] com v[m] peneira (v[1..m-1]) }
Problem-solving skills are almost unanimously
the most important qualification
that employers look for […]
more than programming languages proficiency,
debugging, and system design.
O que você deve fazer ao ser desafiado a encontrar um algoritmo para um novo problema computacional?
Para entender bem o problema, escreva seu enunciado num pedaço de papel, faça um diagrama, explique o problema a um colega exigente. Tente resolver algumas instâncias simples do problema. Tente resolver instâncias extremas, como as muito pequenas e as que não têm solução.
(Esta nota foi inspirada no artigo How to think like a programmer — lessons in problem solving de Richard Reis.)