Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Notas de rodapé: ciência da computação

Instância de um problema

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 ax² + 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 1x² + 1x − 2 = 0.  Outra instância consiste em encontrar x tal que 1x² − 2x + 1 = 0.  Ainda outra instância pede x tal que 123x² − 456x + 789 = 0.

Solução de uma instância de um problema

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

• o número 1 é uma solução da instância (a = 1, b = 1, c = −2) do problema; outra solução da mesma instância é o número −2;
• o número 1 é a única solução da instância (a = 1, b = −2, c = 1) do problema;
• a instância (a = 1, b = 0, c = 1) do problema não tem solução alguma (supondo que o problema exige que x seja real).

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 ± √b² − 4ac) / 2a.

Algoritmo correto

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.

Algoritmo elegante

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.

Algoritmo eficiente

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:

1. A expressão mais rápido que outros deveria incluir não só os algoritmos já conhecidos para o problema, como também os que ainda não foram descobertos.
2. Dados dois algoritmos para um mesmo problema, um pode ser mais rápido que o outro para algumas instâncias do problema e mais lento para outras. Para caracterizar a eficiência, as instâncias maiores são as mais relevantes.
3. Outros recursos computacionais além do tempo (como o espaço de memória, por exemplo) poderiam ser levados em conta para definir eficiência.

Para fazer um resumo grosseiro do conceito, poderíamos dizer que eficiência é fazer mais com menos.

Linear, linearítmico, quadrático

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 é

1. constante se seu consumo tempo não depende de n,
2. logarítmico se consome tempo proporcional a  log n,
3. linear se consome tempo proporcional a  n,
4. linearítmico (ou ene-log-ene) se consome tempo proporcional a  n log n,
5. quadrático se consome tempo proporcional a  n²,
6. cúbico se consome tempo proporcional a  n³,
7. exponencial se consome tempo proporcional a  cⁿ, sendo c uma constante (como 2, por exemplo).

Esses termos referem-se, em geral, ao consumo de tempo no pior caso.

Tipos-de-dados

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:

• O conjunto de valores do tipo  int  (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.

• O conjunto de valores do tipo  char  é  −128, −127, . . . , +126, +127.

  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
  

• O conjunto de valores do tipo  unsigned char  é  0, 1, . . . , 254, 255.
• O conjunto de valores do tipo  double  (que corresponde aos 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.

Números reais e números 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 × 10¹, por exemplo) representados em notação ponto flutuante. Todos esses números são racionais.

Fila de prioridades

Uma fila de prioridades (= priority queue) é qualquer tipo-de-dados dotado de duas operações:

• retirar um elemento de valor máximo;
• acrescentar um novo elemento.

É 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.

Heap

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.

Notação binária, octal e hexadecimal

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×2⁶ + 1×2³ + 1×2² + 1×2¹ + 1×2⁰.  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:

• na notação decimal, o primeiro dígito é diferente de 0,
• na notação octal, o primeiro dígito é 0,
• na notação binária, os dois primeiros caracteres são 0b,
• na notação hexadecimal, os dois primeiros caracteres são 0x.

Por exemplo,  0117  é a representação octal e  0x4F  é a representação hexadecimal de setenta e nove.

Letras com diacríticos

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.)

Tabela ISO-LATIN-1

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.

Estrutura do código UTF-8

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

Expressão bem-formada de parênteses e colchetes

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 devolva sim
          senão devolva nã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 devolva não
          senão se c ≡ ']' então 
               se pilha não vazia e topo da pilha é '[' então
                    desempilhe
               senão devolva não
          senão empilhe c
     }
     se pilha vazia 
          então devolva sim
          senão devolva não
}  

Transformação de expressão infixa em posfixa

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
}  

Distâncias entre cidades

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
}

Peneira do Heapsort

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
}

Heapsort

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])
}

Dicas sobre resolução de problemas

O que você deve fazer ao ser desafiado a encontrar um algoritmo para um novo problema computacional?

1. Antes de tentar resolver o problema, entenda muito bem a natureza dos dados do problema.  Os dados consistem em uma lista de números? um único número? uma sequência de caracteres? um grafo? uma matriz?  Os números são inteiros ou fracionários? são todos positivos ou podem também ser negativos? são todos diferentes entre si ou podemos ter repetições?
2. Entenda muito bem a natureza das soluções das instâncias do problema.  Uma solução é um único número? uma lista de números? uma matriz? uma lista de caracteres? um grafo?  É verdade que toda instância do problema tem solução?
3. Gaste o tempo que for preciso para entender a relação que deve existir entre os dados e uma solução.  Você deve ser capaz de descrever um algoritmo que receba os dados juntamente com um candidato a solução e diga se o candidato é de fato uma solução.

   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.

4. Resista à tentação de começar a escrever código imediatamente. Faça um pouco de planejamento antes de começar a programar.  Se começar a programar cedo demais você corre o risco de ver as árvores e não enxergar a floresta.

(Esta nota foi inspirada no artigo How to think like a programmer — lessons in problem solving de Richard Reis.)

Humor

• Quora: When does programming stop being fun?
• If programming languages were vehicles.
• Sistemas operacionais: MAC, Windows e Linux.
• Engenharia de software.
• Diferença entre do...while e while...do [dica de Arnaldo Mandel].