GEMP Quixadá

O grupo de estudos da Maratona de Quixadá (GEMP-UFC Quixadá)  que foi criado em 2009 pelo professor Wladimir Araújo Tavares.

Atualmente, o grupo conta com uma página:
http://lia.ufc.br/~wladimir/gemp/index.html

Além dessa página, o grupo mantém um site com um boa quantidade de material de apoio:
https://sites.google.com/site/quixadamaratona/

O grupo também desenvolve uma ferramenta para classificar os problemas do spoj:
http://classificadorspoj.appspot.com/

Acesse também o wiki do GEMP - UFC Fortaleza
http://lia.ufc.br/~gemp/Main/HomePage

Na seção Problemas do wiki do GEMP - UFC Fortaleza, você poderá encontrar dicas de como resolver alguns problemas resolvidos pelos membros do GEMP-UFC Fortaleza.
http://lia.ufc.br/~gemp/Problemas/Problemas

Usando a Busca Binária - Ensinando a pescar

Considere o seguinte problema retirado sessão de prática da Internacional Olympiad in Informatics 2007 em Zagreb na  Croácia.

O problema a seguir é um ótimo exemplo da aplicação da busca binária.

PEIXES

Em um pequeno país costeiro, todas as cidades estão situadas em uma longa faixa costeira (que vai ser modelada como uma linha reta). Uma estrada longa corre ao longo da costa, que liga as cidades. A posição de cada cidade pode ser descrita por um número inteiro não negativo único representando a distância (em km) a partir do início da estrada. A maioria dos cidadãos são pescadores, e eles pegam grandes quantidades de peixe. Após a temporada de pesca terminar e antes da alta temporada começar, os peixes podem ser transportados entre diferentes cidades. Uma cidade pode acomodar X turistas se tem toneladas de peixes X disponíveis. O objetivo é para acomodar o maior número possível de turistas igualmente em cada cidade. Em outras palavras, queremos encontrar o maior número inteiro Y para o qual é possível distribuir os peixes de modo a que cada cidade pode acomodar, pelo menos, Y turistas. Em uma transferência, um número inteiro de toneladas de peixes é enviado de uma cidade para outra. Durante o transporte, uma tonelada de peixe por quilômetro percorrido é perdido para saqueadores famintos que descem das montanhas. Mais formalmente, se a navios cidade F toneladas de peixe para outra cidade que é D quilômetros de distância, em seguida, toneladas FD vai chegar o destino, se F é inferior a D, então, toda a carga é perdida. É possível arbitrariamente reembalar e combinar envios em cidades intermediárias. Por exemplo, podemos enviar embarques de cidades A e B para a cidade C, combinar a metade do peixe restante de ambos os embarques com os peixes originários em C e enviá-lo em uma única remessa grande de cidade C para a cidade D.

TAREFA

Escreva um programa que, dadas as posições de todas as cidades e da quantidade de peixe de cada cidade produz, determina o maior número de turistas que podem ser acomodados em cada cidade depois que o peixe foi distribuído.

A primeira linha da entrada contém um inteiro N, 1 ≤ N ≤ 100 000, o número de cidades.

ENTRADA

Cada uma das N linhas seguintes contém dois inteiros P e F, 0 ≤ P, F ≤ 1012, a posição de uma cidade (em km) e da quantidade de peixe que produz (em toneladas). As cidades serão classificadas em ordem crescente de posição.

As posições de todas as cidades sejam distintas.

SAÍDA

A primeira linha de saída e apenas deve conter a maior quantidade de turistas Y a partir da descrição de tarefas.

Entrada 3 1 0 2 21 4 0 Saída 6

input 3 5 70 15 100 1200 20 output 20

input 4 20 300 40 400 340 700 360 600 output 415

Primeiramente, precisamos fazer algumas observações

• Um algoritmo guloso pode ser usado para descobrir se é possível acomodar X turistas em cada cidade. Podemos considerar as cidades da esquerda para a direita. Se uma cidade tem mais X unidades de peixes, então ela pode enviar o excedente para a cidade da direita. Se a cidade tem menos que X unidades, ela deve receber o que falta da cidade da esquerda.

• 1.  Se um valor de turista X é possível então X-1 também é um valor possível. Por outro lado, se X não é possível então X+1 também não é possível. Logo, podemos usar uma busca binária para encontrar o maior valor X possível. A complexidade do algoritmo será O(N LG MAX), onde MAX é um limite superior para a solução do problema. Um bom limite superior seria a soma de toda produção de peixes divididos pelo número de cidades.

Escalonamento de intervalos com pesos

• Cada tarefa j tem um início $s_j$ e um fim $f_j$ e tem um peso ou valor $v_j$.
• Duas tarefas são compatíveis se elas não se sobrepõem 
• Meta: encontrar o subconjunto de tarefas mutuamente compatíveis com maior peso.

Figura retirada dos slides  http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf

O algoritmo guloso funciona para esse problema quando todas as tarefas tem o mesmo peso.

1. Ordene as tarefas em ordem crescente de tempo final.

2. Adicione um tarefa no subconjunto construído se ela é compatível quando as tarefas previamente escolhidas. Note que para executar este passo basta comparar o início da tarefa com o final da última tarefa escolhida.

Note que esta estratégia não funciona quando os pesos não são iguais.

O algoritmo guloso falha quando ordenamos por tempo final ou ordenamos por peso.

Contra-exemplo 1: ordenando por tempo final

Contra-exemplo 2: ordenando por peso

Programação Dinâmica

Ordene as tarefas pode ordem de tempo final: $f_1$,$f_2$,$f_3$,....

Defina p(j) = maior indíce i < j tal que a tarefa i é compatível com a tarefa j.

typedef struct{
  int s,f,w;
} tarefa;

tarefa t[MAXN];
int p[MAXN];

int order_by_finish(const void *a, const void *b){
  tarefa pa,pb;

  pa = *(tarefa *)a;
  pb = *(tarefa *)b;

  return pa.f - pb.f;
}

Agora, vamos decompor o problema definindo uma estrutura recursiva. A forma de decompor será chamada de escolha binária. A escolha binária também é utilizada no problema da mochila.

OPT(j) = valor da solução ótima do problema consistindo das tarefas 1,2,..,j.

Note que temos que avaliar dois casos:

• Se a tarefa j é escolhida então não podemos usar nenhuma tarefa que  incompatível com j. Logo, p(j) entra em acão. As tarefas {p(j)+1,...,j-1} serão descartadas, o problema fica:

OPT(j) = OPT(p(j)) + v(j)

• Se a tarefa j não é escolhida então o problema é reduzido para 

OPT(j) = OPT(j-1).

Logo, a solução é dada por 

OPT(j) = max(OPT(p(j)) + v(j), OPT(j-1)).

Main

t[0].s = 0;
t[0].f = 0;
t[0].w = 0;

for(i=1;i<=n;i++)
   scanf("%d %d %d",&t[i].s,&t[i].f,&t[i].w);

qsort(t,n+1,sizeof(tarefa), order_by_finish);

for(i=1;i<=n;i++){
   p[i] = 0;
   for(j=i-1;j>=1;j--){
      if(t[j].f <= t[i].s){
          p[i] = j;
          break;
      }
   }
}

opt[0] = 0;
for(j=1;j<=n;j++){
  opt[j] = max(opt[j-1], opt[ p[j]] + t[j].w);     
}
printf("%d\n",opt[n]);

SPOJ:

http://www.spoj.com/problems/RENT/

Referência:

http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf

Problema da Maioria

Como determinar se algum candidato recebeu mais de 50% dos votos em tempo linear. Esse problema é conhecido como problema da maioria. Formalmente,

Dada uma sequência de n elementos onde cada elemento é um inteiro x $\in$ [1..k] devolva o elemento majoritário, ou seja, o elemento que aparece mais do que $\frac{n}{2}$ ou zero se nenhum elemento é encontrado.

Algoritmo baseado em contagem

int MajorityCount(int v[], int n, int k){
  int c[k];
  int i;
  for(i=0;i<k;i++) c[i] = 0;
  for(i=0;i<n;i++) c[v[i]]++;
  for(i=0;i<k;i++)
    if(c[i] > n/2 ) return i;
  return 0;
}

Complexidade de tempo O(n+k)
Complexidade de espaço extra O(k)

Algoritmo baseado em comparações

Força Bruta

int MajorityBrute(int v[], int n)
{
  int i;
  for(i=0; i< n; i++)
  {
    int count = 1;
    int item = v[i];
    int j;
    for(j=i+1; j <= n; j++)
    {
      if (v[j] == item) count++; }
      if (count > n/2) return item;
    }
    return 0;
}

Complexidade de tempo O($n^2$)
Complexidade de espaço extra O(1)

Divisão e Conquista

int Count(int v[], int lo, int hi, int x){
  int k;
  int cont = 0;
  for(k=lo;k<=hi;k++)
    if(v[k]==x) cont++;
  return cont;
}

int MajorityDivideConquer(int v[], int lo, int hi)
{
  if (lo > hi) return 0; // empty sequence case
  else if (lo == hi) return v[lo]; // one-element sequence case
  else // general case
  {
    int mid = lo + (hi-lo)/2; // integer division
    int x = MajorityDivideConquer(v,lo,mid);
    int y = MajorityDivideConquer(v,mid+1,hi);
    if (x==y) return x; // x and y are both zero or both majority
    if (x > 0) // x is a majority in 1st half
    if ( Count(v,lo, hi,x) > (hi-lo+1)/2 ) return x;
    if (y > 0) // y is a majority in 2nd half
    if ( Count(v,lo, hi,y) > (hi-lo+1)/2 ) return y;
    return 0;
  }
}

Complexidade de tempo


C(n) = C(n/2) + C(n−n/2) + 2n
C(0) = C(1) = 0

Simplificando para C(n)=2C(n/2)+2n


Complexidade de tempo O(n lg n)

Moore’s Voting Algorithm

int MajorityLinearMoore(int v[], int n){
     int maj_index = 0;
     int count = 1;
     int i;
     for (i = 1; i < n; i++ ){
      if (v[maj_index] == v[i]) count++;
      else count--;
      if (count == 0){
        maj_index = i;
        count = 1;
      }
     }
    if( Count(v, 0, n-1, v[maj_index]) > n/2 )
      return v[maj_index];
    else
      return 0;
}

A corretude deste algoritmo é baseado nas seguintes observações:

1. se v[1..n] tem um valor majoritário e se A[n-1] $\neq$ A[n] então A[1..n-2] também tem um valor majoritário. A mesma observação vale para quaisquer dois elementos do vetor: se A[i] $\neq$ A[j] e A tem um valor majoritário então o vetor que se obtém pela eliminação das posições i e j também tem um valor majoritário. Observe que quando o valor count == 0, o algoritmo recomeça. Isso quer dizer que todos os valores anteriores podem ser eliminados.
2. Para qualquer k $\in$ [1..n], se x é majoritário de A[1..n] se somente se x é majoritário em A[1..k-1] ou A[k..n] ou em ambos. 

Complexidade de tempo O(n)

Problema SPOJ
http://www.spoj.com/problems/MAJORITY/
http://www.spoj.com/problems/MAJOR/


Referências:
Majority Element : http://www.geeksforgeeks.org/majority-element/
Minicurso de Análise de Algoritmos http://www.ime.usp.br/~pf/livrinho-AA/

Identidades combinatórias

A análise combinatória pode ser uma bastante divertida quando tentamos entender as identidades combinatórias através de situações problemas. A análise combinatória deixa de ser um jogo complicado de fórmulas complexas e passa ser um jogo de contagem interessante. Logo, a frase de Tales de Mileto passa a fazer todo o sentido:

“A questão primordial, não é o que sabemos, mas como sabemos”

Frase retirada do trabalho Demonstração de Identidades Combinatórias com Teoria de Contagem

Identidade 1

$\binom{n}{k}$ = $\binom{n}{n-k}$

Problema:

De quantas maneiras podemos formar uma comissão com k alunos para representar a turma com n alunos?

O lado esquerdo conta de quantas maneiras podemos formar uma comissão com k alunos em uma turma com n alunos.  Cada comissão com k alunos exclui n-k alunos. O lado direito conta de quantas maneiras diferentes podemos exclui n-k alunos para formar uma comissão com k alunos.

Identidade 2

$\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$

Problema: 

Novamente, o lado esquerdo representa o número de comissões com k alunos em uma turma com n alunos. Escolha um aluno qualquer da turma, este aluno pode pertencer ou não a comissão.
Caso 1: Se o aluno escolhido pertence a comissão então precisamos escolher k-1 alunos entre n-1 alunos restantes.
Caso 2: Se o aluno escolhido não pertence a comissão então precisamos escolher k alunos entre n-1 alunos restantes.

Identidade 3

$\sum_{i=0}^{n} \binom{n}{i}$ = $2^{n}$

Problema:

Precisamos formar uma comissão de alunos de qualquer tamanho em uma turma com n alunos?

O lado direito conta o número de subconjuntos possíveis em uma turma com n alunos. Cada subconjunto representa uma possível comissão formada. O lado esquerdo conta a mesma quantidade mas de uma maneira mais difícil. O lado esquerdo soma a quantidade de maneiras de formar uma comissão considerando todos os tamanhos possíveis.


Identidade 4

$k\binom{n}{k}$ = $n\binom{n-1}{k-1}$

Problema:

Queremos formar uma comissão com k alunos em uma turma com n alunos sendo que um deles é o presidente.

No lado direito, temos o seguinte raciocínio: temos n possibilidade para a escolha do presidente multiplicada pela quantidade de maneiras de escolher k-1 alunos entre n-1 alunos restantes. No lado esquerdo, contamos de quantas maneiras podemos formar uma comissão de k alunos entre n alunos multiplicada pela quantidade de maneiras que podemos escolher o presidente na comissão com k alunos.

Identidade 5

$\sum_{i=0}^{n} i\binom{n}{i}$ = $n2^{n-1}$

Problema:

Precisamos formar um time de futebol de qualquer tamanho com n jogadores sendo que um deles é o capitão.

Solução:

No lado direito, n representa de quantas maneiras podemos escolher o capitão entre n jogadores multiplicado pela quantidade de maneiras que podemos formar um time (subconjunto) entre n-1 jogadores (elementos). No lado esquerdo, realizamos o mesmo cálculo. Primeiramente, formamos um time com i jogadores multiplicamos pela quantidade maneiras que podemos escolher o capitão no time formado.


Exercício

Prove as seguintes identidades:

Identidade

$k(k-1)\binom{n}{k}$ = $n(n-1)\binom{n-2}{k-2}$

Pense em uma comissão com k membros de n possíveis sendo que cada comissão tem um presidente e um vice-presidente.

Identidade

$2\binom{2n-1}{n}$ = $\binom{2n}{n}$


Identidade

$\sum_{i=0}^{n} \binom{x}{i} \binom{y}{n-i}$ = $\binom{x+y}{n}$

Considere uma turma com x homens e y mulheres, precisamos formar uma comissão com n alunos.


Referências

Monografia Demonstração de Identidades Combinatórias com Teoria de Contagem

Bijections

More bijections

Análise Léxica

Análise Léxica 

Funções

·         Encontrar Lexemas

·         Guarda a numeração das linhas

·         Inserir ids na tabela de símbolos

·         Identificar tokens

·         Identificar constantes

·         Identificar Erros Léxicos

index = 2*cont + 17LL + 0.2 + 0x12;

Lexema	Token
index	identificador
=	sinal_igual
2	constante inteiro
*	Asterisco
cont	identificador
+	sinal_mais
17LL	constante long long
0.2	Constante float
0x12	Constante hexadecimal

Observe que o seguinte código não contém nenhum erro léxico:

if ( a > ) {

 a = 2;

}

Por outro lado, o seguinte trecho de código terá um erro léxico, lexema não identificado.

a = 2b;

Considerando que nenhum identificador pode começar com um dígito então 2b não é identificador válido.

Descrevendo Formal Tokens

Podemos descrever um identificador da seguinte maneira:

Uma letra minúscula ou maiúsculas ou underline seguida um ou mais letras minúsculas ou maiúsculas   ou um dígito ou um underline.

Podemos descrever formalmente utilizando o seguinte dispositivo formal:

Essa figura representa um autômato que pode ser descrito da seguinte maneira:

DFA = S,d,Q₀,F>

Q = conjunto de estados

S = Alfabeto

d Função de transição TOTAL

d : Q x S ® Q

A função recebe um estado e um símbolo do alfabeto e devolve um novo estado.

Q₀ Estado Inicial Q₀ Î Q

F    Estados Finais F Í Q

Exemplo:

Q = {q0,q1,q2,q3}

S = {a,b}

Q₀=q0

F = {q3}

d	a	b
q0	q1	q2
q1	q0	q3
q2	q3	q0
q3	q2	q1

Algumas strings que pertencem a essa linguagem do autômato L_A:

ab Î L_A

ba  Î L_A

bbab Î L_A

aaba Î L_A

Que linguagem está sendo descrita por esse autômato?

Observe que nesse autômato, todas as strings tem uma quantidade ímpar de a’s e b’s com tamanho maior que 1. Com um modelo simples descrevemos formalmente um dispositivo capaz de reconhecer qualquer string dessa linguagem.

Expressão Regular

É outra forma concisa e flexível de descrever unidades léxicas.

e é uma expressão regular.  (caractere vazio é uma expressão regular).

a Î S^* então a e (a) são expressões regulares. (qualquer string formada pelo nosso alfabeto é uma expressão regular).

 a e b são expressões regulares então

ab é uma expressão regular (concatenação)

a|b é uma expressão regular (união)

a⁺ é uma expressão regular (1 ou +)

a^* é uma expressão regular (0 ou +)

a? é uma expressão regular (0 ou 1)

Exemplos:

‘0’’1’ = {‘01’}

‘0’|’1’ = {‘0’,’1’}

‘0’⁺ = {‘0’,’00’,’000’,’0000’,...}

‘0’^* = {e,‘0’,’00’,’000’,’0000’,...}

‘0’? = {e,‘0’}

‘0’^*’1’⁺={‘1’,’’}

Identificador usando expressão regular

(‘a’...’z’|’A’...’Z’|’_’) (‘a’...’z’|’A’...’Z’|’_’|’0’...’9’)^*

ANTLR

Expressão regular

ID  :     ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*

    ;

Diagrama de Sintaxe

Introdução à Programação Dinâmica

Programação dinâmica é uma técnica de resolução de problemas que aparece de muitas formas em várias situações. A programação dinâmica é baseada na aplicação da técnica de divisão e conquista nos problemas nos quais os subproblemas gerados se repetem.  Esta propriedade chamamos de sobreposição de subproblemas. 

Nem sempre é fácil dividir o problema e encontrar os problemas sobrepostos.

Problema do Tijolo

Nós queremos construir uma parede de tijolos com tijolos do tipo 2 x 1, e se o nosso muro deve ter de duas unidades de altura, podemos fazer o nosso muro de várias maneiras, dependendo do comprimento do muro.

De quantas maneiras podemos construir um muro com comprimento 4? E comprimento 5?  Precisamos aplicar a técnica de divisão e conquista para resolver este problema. Primeiramente, podemos observar que o tijolo pode ficar em pé ou dois deitados.

Considerando uma parede inicial com comprimento n, no primeiro caso, temos que cobrir uma parede com comprimento n-1 e no segundo caso uma parede com comprimento n-2.

Se observamos a maneira que uma parede com comprimento 3 é coberta, podemos notar que as duas primeiras maneiras começam com um tijolo em pé depois segue o padrão do comprimento 2 e a última maneira começa com dois tijolos deitados.

Algoritmo

int f(int n){ 
 cont++;
 if(n<=2) return n;
 else return f(n-1)+f(n-2);
}
int main(){
 cont = 0;
 clock_t begin = clock();  
 printf("%d\n",f(40));
 printf("chamadas %d\n",cont);
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
}

165580141
chamadas 204668309
EXECUTION TIME(seconds):    1.367 second(s).

Observe que existe muita intersecção entre os subproblemas gerados.
f(5)
f(4) + f(3)
f(3)+f(2) + f(2) + f(1)
f(2)+f(1)+ f(2) + f(2) + f(1)

Por exemplo, para resolver f(5) será resolvido uma vez f(4), duas vezes f(3), três vezes f(2) e duas vezes f(1).

Podemos reduzir o número de chamadas aproveitando a própria estrutura recursiva e construindo uma solução bottom-up (de baixo para cima).

int f2(int n){ 
 int f[n+1];
 int i;
 if(n<=2) return n;
 else{
  f[1]  = 1;
  f[2]  = 2;
  for(i=3;i<=n;i++){
   f[i] = f[i-1]+f[i-2];
  }
  return f[n];
 }
}

165580141
EXECUTION TIME(seconds):    0.001 second(s).

Uma técnica que pode ser utilizada para reduzir o número de chamadas desnecessárias é a memorização. A memorização consiste em guardar os valores computados para que eles não precisem ser computados novamente.

int memo[MAXN];
void init(){
 int i;
 for(i=0;i<MAXN;i++) memo[i] = -1;
 memo[1] = 1;
 memo[2] = 2;
}

int f3(int n){
 cont++;
 if( n <= MAXN ){
  if(memo[n]!=-1) return memo[n];
  else{
   memo[n] = f3(n-1) + f3(n-2);
   return memo[n];
  }
 }else{
  return f3(n-1) + f3(n-2);
 }
}

int main(){
 cont = 0;
 clock_t begin = clock();  
 init();
 printf("%d\n",f3(40));
 printf("chamadas %d\n",cont);
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
 
}

165580141
chamadas 77
EXECUTION TIME(seconds):        0 second(s).

Número de combinações

O número de combinações pode ser obtido pela seguinte fórmula:

C(n,k) = $\frac{n!}{k!(n-k)!}$

C(n,k) representa o número de subconjuntos de tamanho k que podem ser formados a partir de um conjunto com n elementos. Observe que podemos dividir em subproblemas fazendo uma simples observação.

Escolha um elemento x qualquer do conjunto com n elementos. O elemento x pode está ou não no subconjunto com k elementos formados.

Caso 1: x está no subconjunto que está sendo formado. Precisamos escolher k-1 elementos de conjunto com n-1 elementos.
Caso 2: x não está no subconjunto que está sendo formado. Precisamos escolher k elementos de conjunto com n-1 elementos.

C(n,k) = C(n-1,k-1) + C(n-1,k)

int C(int n, int k){
 cont ++;
 if(k==0 || n==k ) return 1;
 else return C(n-1,k-1) + C(n-1,k);
}

int main(){
 cont = 0;
 clock_t begin = clock();  
 printf("%d\n",C(30,10) );
 printf("chamadas %d\n",cont);
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
}

30045015
chamadas 60090029
EXECUTION TIME(seconds):     0.48 second(s).
Pressione qualquer tecla para continuar. . .

Memorizando

int memo[MAXN][MAXN];
void init(){
 int i,j;
 for(i=0;i<MAXN;i++) 
  for(j=0;j<=i;j++)
    memo[i][j] = -1;
 for(i=0;i<MAXN;i++)
  memo[i][0] = memo[i][i] = 1;  
}

int C(int n, int k){
 cont ++;
 printf("%d %d\n",n,k);
 if(memo[n][k]!=-1) return memo[n][k];
 else {
  memo[n][k] = C(n-1,k-1) + C(n-1,k);
  return memo[n][k];
 }
}

int main(){
 cont = 0;
 clock_t begin = clock();  
 init();
 printf("%d\n",C(30,10) );
 printf("chamadas %d\n",cont);
 double elapsed = ((double) (clock() - begin)) / CLOCKS_PER_SEC;
 printf("EXECUTION TIME(seconds): %8.5g second(s). \n", elapsed);
 system("PAUSE");
}

30045015
chamadas 401
EXECUTION TIME(seconds):    0.001 second(s).
Pressione qualquer tecla para continuar. . .