domingo, 26 de setembro de 2010

Os apertos de mão

Numa festa foram dados 28 apertos de mão. Cada pessoa apertou a mão a cada uma das outras, exactamente uma vez.
Quantas pessoas estavam na festa?

E se estivessem na festa 20 pessoas  quantos apertos de mão se dariam, sabendo que cada uma apertaria a mão a cada uma das outras apenas uma única vez?

R:  8; 190

sexta-feira, 10 de setembro de 2010

Sistema de escrutínio maioritário de duas voltas


 (Eleição do Presidente da República Portuguesa)

Algoritmo:


1 – Será eleito o candidato que obtiver mais de metade dos votos validamente expressos, não se considerando como tal os votos brancos e nulos.

2 – Se nenhum dos candidatos obtiver esse nº de votos, procede-se a 2ª votação
(sufrágio).

3 – Ao 2º sufrágio concorrerão apenas os dois candidatos mais votados (que não tenham retirado a sua candidatura).

quinta-feira, 9 de setembro de 2010

Método de Saint-Laguë

Este método difere do de Hondt apenas na série de divisores que é utilizada. Neste caso,o número de votos apurados por cada lista é dividido sucessivamente por 1, 3, 5, 7, etc...

Este método encontra-se em vigor nos países escandinavos.

Método de Hondt

Este método foi aplicado pela primeira vez nas eleições parlamentares de 1900, na Bélgica.

Em Portugal, as eleições da Assembleia da República, Autarquias Locais e Parlamento Europeu seguem o Método de Hondt (jurista Belga e professor de Direito Civil na Universidade de Gand).

Algoritmo:

1 - Apura-se em separado o número de votos recebidos por cada lista no respectivo círculo eleitoral.

2 - O número de votos apurados por cada lista é dividido sucessivamente por 1, 2, 3, 4, 5,... até ao número de mandatos a atribuir (se necessário) sendo os quocientes ordenados por ordem decrescente da sua grandeza, numa sequência de tantos termos quantos os mandatos atribuídos ao respectivo círculo eleitoral.

3 - Os mandatos pertencem às listas a que correspondem os termos da sequência estabelecida no passo anterior recebendo cada uma das listas tantos mandatos quantos os seus termos na sequência.

4 - No caso de restar um só mandato para atribuir e de os termos seguintes da sequência serem iguais e pertencerem a listas diferentes, o mandato cabe à lista que tiver obtido o menor número de votos.

Sistemas Maioritários. Conceitos

Sistema maioritário de uma volta – Ganha o candidato mais votado, independentemente de ter maioria absoluta ou relativa.


Sistema maioritário de duas voltas – Ganha o candidato que obtiver maioria absoluta na 1ª volta, caso contrário serão admitidos à 2ª volta os dois candidatos mais votados e ganhará o que obtiver mais votos.

Sistema maioritário de duas ou mais voltas – Ganha o candidato que obtiver maioria absoluta na 1ª volta, caso contrário serão admitidos à 2ª volta todos os candidatos que atinjam uma determinada percentagem de votos, repetindo-se o processo até se obter o vencedor com maioria absoluta.

Sistemas Maioritários e Sistemas de Representação Proporcional

1. SISTEMAS MAIORITÁRIOS


1.1. CIRCUNSCRIÇÕES UNINOMINAIS

1.1.1. Maioria simples

1.1.2. Maioria absoluta

1.1.3. Votação alternativa ou preferencial

1.2. CIRCUNSCRIÇÕES PLURINOMINAIS

1.2.1. Votação por listas de partidos

1.2.2. Votação maioritária

2. SISTEMAS PROPORCIONAIS

2.1. Proporcionais puros

2.2. Proporcionais limitados

2.2.1. Quociente eleitoral (com o sistema de repartição de restos dos "restos maiores" ou da "média maior")

2.2.1.1. simples ou hare

2.2.1.2. hagenbach-bischoff

2.2.1.3. imperiali

2.2.1.4. droop

2.2.1.5. duplo

2.2.1.6. número uniforme

2.2.2. Hondt

2.2.3. Saint-Laguë

2.2.4. Saint-Laguë modificado

Sistemas Eleitorais

Métodos Eleitorais - Parlamento Europeu:




• Alemanha – Método Hare/Niemeyer

• Áustria – Método de Hondt

• Bélgica – Voto preferencial

• Dinamarca – Método de Hondt

• Eslovénia – Voto preferencial

• Espanha – Método de Hondt

• Estónia – Método de Hondt

• Finlândia – Método de Hondt

• Holanda – Método de Hondt e voto preferencial

• Hungria – Método de Hondt

• Letónia – Método de Saint-Lague

• Lituânia – Voto Preferencial

• Luxemburgo – Método de Hondt

• Polónia – Método de Hondt e Método Hare/Niemeyer

terça-feira, 7 de setembro de 2010

Introdução à Teoria dos Grafos

Grafo - estrutura matemática usada para representar as relações entre as coisas ou objectos.

Os grafos possuem nós ou vértices (coisas/objectos) e arestas (relações entre as coisas). Se designarmos por V ( conjunto não-vazio de vértices) e A (conjunto das arestas, constituído por pares não ordenados de vértices) então o grafo G é o par (V, A).

 Exemplos:
1. Mapa rodoviário -> nele as cidades (vértices) relacionam-se entre si através das várias estradas (arestas).
2. Sistema de distribuição de água /electricidade/gás -> nele as casas (vértices) relacionam-se entre si (e entre as centrais de distribuição) através dos canos de água/postes de electricidade/canos de gás (arestas).
3. Rede do Metropolitano -> nela as estações (vértices) estão ligadas entre si através de vias onde circulam os comboios (arestas)



Um grafo G=(V, A) consiste, pois, em:


- um conjunto finito de pontos V. Os elementos de V dizem-se os vértices de G.

- um conjunto finito A de pares não ordenados de V, que se dizem as arestas de G.

Uma aresta a em A é um par não ordenado {v, w} de vértices v, w em V, que se dizem as extremidades   de a.

Duas arestas distintas podem ter as mesmas extremidades (mesmos vértices) dizendo-se nesse caso arestas paralelas.

Uma aresta com as duas extremidades iguais diz-se um lacete.

Um vértice que não tem ligação com nenhum outro vértice é um vértice isolado.

Um grafo  sem arestas é um grafo nulo.

Grafo simples é todo aquele que não possui arestas paralelas nem lacetes.

ADJACÊNCIA,ORDEM, DIMENSÃO E GRAU

Num grafo, dois vértices dizem-se adjacentes se tiverem uma aresta que os una.

Num grafo, duas arestas dizem-se adjacentes se tiverem um vértice em comum.

A ordem de um grafo representa o número de vértices desse grafo.

A dimensão de um grafo representa o número de arestas desse grafo.

O grau ou valência de um vértice é igual ao número de arestas que começam (ou terminam) nesse vértice.

Grafo regular é um grafo cujos  vértices têm o mesmo grau.

MULTIGRAFO

Multigrafo é um grafo em que entre dois dos seus vértices existem duas ou mais arestas ou em que existem lacetes.


Em qualquer grafo:

soma de todos os graus dos vértices = 2 x número de arestas

A figura   traz a representação gráfica do grafo G acima, onde
 G = (V, A) = ({v0, v1, v2, v3, v4, v5}, {(v0, v3), (v0, v2), (v1, v2), (v2, v3), (v3, v4)}) =
     = ({v0, v1, v2, v3, v4, v5}, {e0, e1,e2, e3, e4})


Os seus vértices correspondem a pontos distintos do plano em posição aleatória e  as suas arestas correspondem a rectas ou curvas que unem estes pontos.

Um grafo completo com n vértices, designado Kn, é um grafo simples onde todo par de vértices é ligado por uma aresta. Por outras palavras, um grafo completo é um grafo simples que contém o número máximo de arestas.

Eis alguns exemplos de grafos completos:
O grafo K1 chama-se grafo trivial.


Assim, o número de arestas de um grafo completo é
sendo n o número de vértices do grafo.

segunda-feira, 6 de setembro de 2010

Grafos.Redes.

Os grafos são a forma elegante de codificar aquilo que na linguagem corrente chamamos redes.
Um grafo é um conjunto de pontos, que representam objectos reais, ligados por arestas, que representam relações entre os objectos reais.

Na figura seguinte podemos ver alguns exemplos adicionais do que os nodos (vértices) e arestas podem representar.

Alguns exemplos de grafos:
Os grafos foram inventados por Euler em 1736 para resolver o famoso problema das pontes de Königsberg (a). A questão era saber se era possível atravessar as sete pontes do rio Pregel (b), passando sobre cada uma delas uma só vez, e regressar ao ponto de partida. A ideia de Euler consistiu em representar as quatro zonas da cidade, delimitadas pelo rio, por nodos e as pontes por arestas entre esses nodos (c). O objecto assim construído é um exemplo de um grafo. Pensando neste modelo, é evidente que um tal caminho só é possível se cada nodo estiver ligado a um número par de arestas, pois se se chega a uma zona por uma ponte, a condição de que cada ponte é percorrida uma só vez implica que se possa sair por uma outra. Dado que todos os nodos do grafo têm grau (número de arestas que saem de um nodo) ímpar, um caminho com aquelas propriedades é impossível.


(in Escola de Redes)

AS CLASSES DE GINÁSTICA - o método de Hamilton

Três classes de ginástica de um clube decidem constituir uma associação que defenda os seus interesses. A assembleia será constituída por 2...