Maquina de Turing

Complexidade Computacional

A classe P

Podemos classificar todos os problemas computacionais em nos que podem ser resolvidos através de algoritmos e os que não podem.

Uma Máquina de Turing é dita polinomialmente limitada se há polinômio p(n), tal que, para qualquer entrada x, tal que esta máquina sempre pára após, no máximo, p(n) passos, onde n é o comprimento da cadeia de entrada.

Grafo eurelianos e hamiltonianos

Um Grafo G é Eureliano se e somente se apresentar as duas propriedades:

1 Para qualquer par u, v ϵ V, nenhum dos quais isolados, existe algum caminho de u a v; e

2 Todos os vértices apresentam o mesmo número de arestas que entram e saem.

Grafo A é Eureliano, B não é.

Circuito de Hamilton: Dado um grafo G, existe algum circuito que passa por cada um dos vértices de G exatamente uma vez?
Se isso acontecer, é denominado grafo Hamiltoniano.

O grafo A é tanto Eureliano como Hamiltoniano e o grafo B, apenas Hamiltoniano.

Problema do Caixeiro Viajante

Dado um conjunto de cidades e uma matriz n x n de inteiro não-negativos d, onde d denota a distância entre a cidade ci e a cidade cj, admitindo que dii= 0 e dij=dji para todos os i,j, pede-se encontrar a trajetória mais curta pelas cidades, isto é, uma bijeção π do conjunto { 1,2, ..., n} para ele próprio (onde π é a i-ésima cidade visitada nessa trajetória), tal que a quantidade seja a menor possível.

Problema da cobertura de vértices

Um conjunto de vértices cobre uma aresta se ele contiver, no mínimo, uma das extremidades dessa aresta. Podemos considerar os vértices de um grafo não-orientado como sendo as salas de um museu, e cada aresta, como um corredor reto que une duas salas. Então, o Problema da Cobertura de Vértices pode ser útil para destacar o número mínimo possível de guardas para as salas, de modo que todos os corredores possam ser vigiados por um guarda.

Problema do Particionamento

Suponha que sejam fornecidos