(define +
(lambda (a b)
(if (zero? b)
a
(succ (+ a (pred b))))))
(+ zero x) = x?
(succ (+ a b)) = (+ (succ a) b)
(succ (+ a b)) = (+ a (succ b))
(define f
(lambda (x n)
(if (zero? n)
1
(if (even? n)
(f (* x x) (quotient n 2))
(* x (f (* x x) (quotient n 2)))))))
(f x n),
quantas vezes a função f é chamada?
x
e uma lista de números l,
e retorne uma lista com os elementos de l que são
menores que x.
x.
(define lim 8)
(define (ataca l1 c1 l2 c2)
(or (= c1 c2)
(= (- l1 c1) (- l2 c2))
(= (+ l1 c1) (+ l2 c2))))
(define (livre l c p)
(if (null? p)
#t
(and (not (ataca l c (length p) (car p)))
(livre l c (cdr p)))))
(define (q p i)
(if (= (length p) lim)
(begin (display p) (newline) #t)
(if (> i lim)
#f
(or (and (livre (+ (length p) 1) i p)
(q (cons i p) 1))
(q p (+ i 1))))))
l com seus elementos):
(define subs
(lambda (l a)
(if (null? l)
(begin (display a) (newline))
(begin (subs (cdr l) a)
(subs (cdr l) (cons (car l) a))))))
a é um
acumulador de resultados parciais...)
subs
escreva a função subs#,
que retorna o número de elementos impressos em uma
chamada (subs l '()).
Simplifique ao máximo sua função (retire argumentos não utilizados, etc).
subs# calcula?
Prove sua resposta.
subs de modo que ela receba um parâmetro
adicional n, e imprima somente os subconjuntos
de l com no máximo n elementos.
(define subsn
(lambda (l n a)
(if (or (null? l) (zero? n))
(begin (display a) (newline))
(begin (subsn (cdr l) n a)
(subsn (cdr l) (- n 1) (cons (car l) a))))))
subs# para essa nova função.
(define (comb l n a)
(cond ((zero? n) (display a) (newline))
((null? l) '())
(else (comb (cdr l) n a)
(comb (cdr l) (- n 1) (cons (car l) a)))))
(define (comb# l n)
(cond ((zero? n) 1)
((zero? l) 0)
(else (+ (comb# (- l 1) n)
(comb# (- l 1) (- n 1))))))
comb (ver acima) para que ele
enumere todas as combinações com repetições de n elementos de uma lista l.
(Chame a nova função de comb*.)
(define (f l)
(if (null? l)
l
(cons (+ (car l) (length l) -1) (f (cdr l)))))
comb* para que ela
aplique f sobre os resultados antes de mostrá-los.
(O que a função faz agora?)
l uma lista não crescente de m números entre 1 e n,
e l1 = (f l).
l1?
l1?
l1 é uma lista decrescente
(e portanto não possui valores repetidos).
g que seja a inversa de f.
Prove que (f (g l)) = l e (g (f l)) = l.
l uma combinação de m números entre 1 e n,
listados em ordem decrescente, e l1 = (g l).
l1?
l1?
b bolas distintas em u urnas distintas:
ub
b bolas indistintas em u urnas distintas:
C*(u,b)
b bolas distintas em u urnas indistintas:
ver lista de exercícios passada.
b bolas indistintas em u urnas indistintas:
ver próxima aula.
b bolas indistintas
em u urnas indistintas.
Podemos repartir as soluções em dois grupos: as soluções que deixam ao
menos uma urna vazia e as que não deixam nenhuma urna vazia.
No primeiro caso, o problema se resume a distribuir as b
bolas nas u-1 urnas ainda disponíveis.
No segundo caso, para garantir que nenhuma urna está vazia,
precisamos colocar pelo menos uma bola em cada urna,
utilizando portanto u bolas;
em seguida, podemos distribuir livremente as b-u bolas
restantes por todas as u urnas.
Como as bolas são indistintas, podemos representar cada solução por uma
lista de inteiros de comprimento u, que indica quantas bolas
cada urna contém.
A ação de colocarmos uma bola em cada urna, então, se traduz em
incrementarmos os elementos da lista.
Para implementar essa ação, escreva uma função auxiliar que receba uma
lista l e um número u,
e retorne l com os u primeiros
números incrementados de 1.
Agora, escreva a função dist que gera as distribuições.
Siga a estrutura geral usada nas outras funções de enumeração que já
escrevemos (em especial, use um acumulador para os resultados).
Procure identificar cuidadosamente os casos base.
O caso geral pode ser resolvido seguindo-se a estratégia recursiva
delineada acima.
Finalmente, modifique sua função dist para escrever
dist#, que retorna o número de distribuições.
04/05 - Problemas combinatórios (exercícios)
n-1,
onde n é o tamanho do array.
(make-vector x y) retorna um novo
array com x posições,
inicializadas com o valor y.
(vector-ref a i) acessa o i-ésimo elemento
do array a (leia como a[i]).
(vector-set! a i v) modifica o i-ésimo elemento
do array a (leia como a[i] = v).
#(...),
com os elementos do array entre os parênteses.
Agora, o exercício é construir um conversor de grafos.
Sua função deve receber uma lista com dois elementos:
um número n e uma lista de pares de
números entre 0 e n-1;
por exemplo, (5 ((2 3) (3 4) (2 4) (0 1) (0 2))).
A função então deve retornar um array com n elementos,
cada um deles contendo uma lista de números,
com a seguinte característica:
um número y deve constar da lista de números na posição
x do array se e somente se o par (x y)
estiver na lista de pares do argumento.
Por exemplo, se a função for chamada com a lista mostrada acima,
retornaria algo como #((2 1) () (4 3) (4) ())
(a ordem dos números dentro de cada lista não é relevante).
Por exemplo, por causa da presença do par (2 4) na entrada,
a lista na posição 2 do array, (4 3), contém o número 4.
Dica: faça uma função auxiliar, recursiva, que receba a lista de pares e o array, e insira os números nas listas adequadas. Faça outra função, principal, que crie o array e use essa função auxiliar para preenchê-lo.
(define (fill g l)
(if (not (null? l))
(let ((x (caar l)) (y (cadar l)))
(vector-set! g x (cons y (vector-ref g x)))
(fill g (cdr l)))))
(define (converte g1)
(let ((g (make-vector (car g1) '())))
(fill g (cadr g1))
g))
Modifique agora sua função para um par (x y) na lista de
entrada gerar um y na lista da posição x do array
*e* um x na lista da posição y.
Por exemplo, a lista de exemplo geraria como saída o array
#((2 1) (0) (0 4 3) (4 2) (2 3)).
F: aresta -> vértice (From - origem da aresta)
T: aresta -> vértice (To - destino da aresta)
A implementação (recursiva) desse algoritmo é bastante simples:
temos uma função básica, visita, que recebe um
grafo G (representado por um vetor de listas de adjacências)
e um nó N,
e então chama visita recursivamente para todos os nós
vizinhos de N
(isto é, aqueles nós para os quais exista um arco
saindo diretamente de N).
visita;
por enquanto, faça ela apenas imprimir cada nó visitado.
(Dica: você pode usar a função pré-definida (for-each f l),
que aplica a função f sobre cada elemento da lista
l.)
(cola)
A implementação "ingênua" feita acima tem um grave problema: se o grafo contiver ciclos, sua função poderá entrar em loop (por que?). Além disso, ela pode visitar várias vezes um mesmo nó. Uma maneira de solucionarmos isso é adicionarmos mais um parâmetro à nossa função: um array que indica, para cada nó, se ele já foi visitado. Assim, quando chegamos em um nó pela segunda vez (posição no array já "marcada"), não precisamos visitar seus vizinhos novamente.
visita,
para representar o pai.)
Com isso, ao final do nosso algoritmo, esse array irá representar
listas encadeadas com o inverso do caminho da origem do nosso
percorrimento para cada nó visitado.
Por exemplo, se depois de percorrermos todo um grafo com 10 nós,
partindo do nó 0, o array de marcas for
#(0 0 #f 0 5 3 5 3 6 #f), isso indica que existe
um caminho (0 3 5 4) de 0 para 4 no grafo:
na posição 4 do array temos 5, na posição 5 temos 3,
e na posição 3 temos 0, nossa origem.
(Nesse exemplo, existe um caminho de 0 para 8? Qual?)
Dica: ao invés de marcar o array a quando tiramos um nó
da fila, como o algoritmo atual faz,
marque o nó quando for colocá-lo na fila
(pois nessa hora sabemos quem é seu antecessor);
em particular, se o nó já estiver marcado,
ele nem precisa ser colocado na fila.
Para isso, defina uma função auxiliar.
Ela pode receber a lista de vizinhos,
o nó "pai", e o array de marcas;
cada nó ainda não marcado recebe o pai como marca,
e a função retorna a lista dos nós que ela marcou
(isso é, que não estavam marcados).
#(( 1 3 ) () ( 0 1 ) ()) ; grafo sem custos
#(((1 0.5) (3 1.2)) () ((0 5.0) (1 0)) ()) ; com custos
O grafo com custos representado acima tem, saindo do nó 0,
um arco para o nó 1 com custo 0.5,
e outro arco para o nó 3 com custo 1.2.
Seguindo a representação acima, defina o grafo abaixo:
Lemas, teoremas e corolários: árvores são grafos conexos e acíclicos. A raiz tem sempre grau de entrada 0, e os outros nós grau de entrada 1. Uma árvore com n vértices tem exatamente n-1 arestas.
Uma árvore não dirigida é um grafo não dirigido conexo e acíclico.
Lemas, teoremas e corolários: um grafo não dirigido é uma árvore se e somente se existe alguma maneira de atribuir direções aos arcos que o transforme em uma árvore dirigida. Dada uma árvore não dirigida com n nós, existem exatamente n maneiras diferentes de atribuirmos direções aos arcos para transformá-la em uma árvore dirigida, correspondendo a escolhermos cada um dos nós como raiz.
Uma árvore geradora de um grafo não dirigido G é um sub-grafo de G que (1) seja uma árvore e que (2) contenha todos os nós de G.
Algoritmo para achar uma árvore geradora de custo mínimo para um dado grafo (não dirigido com custos).
Nosso trabalho é construirmos um algoritmo para colorir um grafo (não necessariamente com a coloração mínima). O algoritmo é uma modificação do algoritmo básico de busca em profundidade (cola): quando visitamos um nó ainda não marcado, marcamos o nó com uma cor (isto é, colocamos o número representando a cor no array de marcas...). A cor escolhida para o nó será sempre a menor cor livre, isso é, ainda não ocupada por algum vizinho.
Observe que o problema da coloração se refere a grafos
não dirigidos (só estamos interessados se nós são ou não são vizinhos).
Por isso, a lista de adjacências de cada nó
deve incluir todos os vizinhos desse nó.
Um grafo como (4 ((0 1) (3 2) (0 3) (2 1))) é representado
como #((1 3) (0 2) (1 3) (2 0)).
As duas funções abaixo podem facilitar bastante o trabalho:
#f para nós ainda não
coloridos), retorne a lista de cores usadas por esses nós.
Para terminar: você é capaz de construir um grafo para o qual esse algoritmo não constrói a coloração mínima?
Arcos serão representados por listas com três elementos:
(origem destino custo).
Para simplificar a manipulação de arcos,
definimos as funções auxiliares abaixo:
(define origem car) (define destino cadr) (define custo caddr)
Para representarmos o conjunto de nós "dentro",
vamos usar um array de booleanos indexado pelos nós:
um valor #t indica que o nó pertence ao conjunto.
(define (pertence? no conjunto) (vector-ref conjunto no)) (define (insere no conjunto) (vector-set! conjunto no #t))
destino
não pertence ao conjunto dado.
Grafos serão representados por um array que, para cada nó,
contém a lista de todos os arcos incidentes no nó.
Isso implica uma certa redundância no grafo
(pois cada arco já contém o seu nó origem),
mas simplifica o programa.
Como exemplo, o grafo
(4 ((0 1 10) (3 1 1) (2 0 5)))será representado como
#(((0 1 10) (0 2 5)) ((1 0 10) (1 3 1)) ((2 0 5)) ((3 1 1))).
Lembre-se do passo do algoritmo: selecionar o arco de menor custo que cruza de "dentro" para "fora" (função já feita), incluir o nó destino desse arco no conjunto de nós "dentro" (função já feita), e atualizar a lista de arcos que cruzam a fronteira. Uma maneira fácil de executar esse último passo é juntar a lista antiga com todos os arcos incidentes ao novo nó "dentro", e retirar da lista os arcos cujo destino esteja "dentro" (função já feita).