Acesso mais rápido do que o navegador!
59 relações: Algoritmo de aproximação, Algoritmo de Dijkstra, Algoritmo de Kruskal, APX-completude, Árvore (grafo), Árvore de extensão mínima, Bioinformática, Carl Friedrich Gauss, Circuito elétrico, Combinatória, Complexidade de pior caso, Complexidade temporal, Computers and Intractability, Conjectura, CRC Press, Desigualdade triangular, Distância euclidiana, Elsevier, Espaço métrico, Esquema de aproximação de tempo polinomial, Estrela (teoria dos grafos), Geometria do táxi, Grafo completo, Grafo k-aresta-conexo, Grafo k-vértice-conexo, Grafo simples, Grafo valorado, Heap, Hiperônimo e hipônimo, Jakob Steiner, Miloš Kössler, NP-completo, NP-difícil, Otimização combinatória, P versus NP, Planejamento e design de rede, Plano (geometria), Plano projectivo, Ponto (matemática), Ponto de Fermat, Problema de cobertura de conjuntos, Problema de decisão, Problema de otimização, Problema do caixeiro-viajante, Problema do caminho mínimo, Programação linear, Reta, Ronald Graham, Simpósio da Teoria da Computação, Software de projeto de circuitos integrados, ..., Springer Science+Business Media, Subconjunto, Supremo e ínfimo, Toro (topologia), União-busca, Vojtěch Jarník, W. H. Freeman and Company, World Scientific, 21 problemas NP-completos de Karp. Expandir índice (9 mais) »
Algoritmo de aproximação
Em ciência da computação e pesquisa operacional (PO), algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização.
Novo!!: Problema da árvore de Steiner e Algoritmo de aproximação · Veja mais »
Algoritmo de Dijkstra
O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O(E + V \log(V)) onde V é o número de vértices e E é o número de arestas.
Novo!!: Problema da árvore de Steiner e Algoritmo de Dijkstra · Veja mais »
Algoritmo de Kruskal
O algoritmo de Kruskal é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo conexo com pesos.
Novo!!: Problema da árvore de Steiner e Algoritmo de Kruskal · Veja mais »
APX-completude
Em teoria da complexidade a classe 'APX' (uma abreviação de "aproximável" em inglês) é o conjunto de Problemas de otimização NP que permitem algoritmos de aproximação em tempo polinomial com relação de aproximação delimitadas por uma constante (ou algoritmos de aproximação de fator constante por simplicidade).
Novo!!: Problema da árvore de Steiner e APX-completude · Veja mais »
Árvore (grafo)
Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos).
Novo!!: Problema da árvore de Steiner e Árvore (grafo) · Veja mais »
Árvore de extensão mínima
Dado um grafo não orientado conectado, uma árvore de extensão deste grafo é um subgrafo o qual é uma árvore que conecta todos os vértices.
Novo!!: Problema da árvore de Steiner e Árvore de extensão mínima · Veja mais »
Bioinformática
Mapa do cromossomo X humano (a partir do site NCBI). O mapeamento do genoma humano é uma das maiores conquistas da bioinformática Bioinformática é um campo interdisciplinar que corresponde à aplicação das técnicas da informática, no sentido de análise da informação, nas áreas de estudo da biologia.
Novo!!: Problema da árvore de Steiner e Bioinformática · Veja mais »
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (ou Gauß) (Braunschweig, — Göttingen) foi um matemático, astrônomo e físico alemão que contribuiu muito em diversas áreas da ciência, dentre elas a teoria dos números, estatística, análise matemática, geometria diferencial, geodésia, geofísica, eletroestática, astronomia e óptica.
Novo!!: Problema da árvore de Steiner e Carl Friedrich Gauss · Veja mais »
Circuito elétrico
Um circuito elétrico simples, constituído de uma fonte de tensão e de um resistor. Um circuito elétrico é a ligação de elementos elétricos, tais como resistores, indutores, capacitores, diodos, linhas de transmissão, fontes de tensão, fontes de corrente e interruptores, de modo que formem pelo menos um caminho fechado para a corrente elétrica.
Novo!!: Problema da árvore de Steiner e Circuito elétrico · Veja mais »
Combinatória
A combinatória é um ramo da matemática que estuda coleções finitas de elementos que satisfazem critérios específicos determinados e se preocupa, em particular, com a "contagem" de elementos nessas coleções (combinatória enumerativa), com decidir se certo objeto "ótimo" existe (combinatória extremal) e com estruturas "algébricas" que esses objetos possam ter (combinatória algébrica).
Novo!!: Problema da árvore de Steiner e Combinatória · Veja mais »
Complexidade de pior caso
Na Ciência da computação a “Complexidade de pior caso” (usualmente denotada em notação assintótica) mede os recursos (ex. tempo de execução, memória) que um algoritmo precisa no pior caso.
Novo!!: Problema da árvore de Steiner e Complexidade de pior caso · Veja mais »
Complexidade temporal
Em ciência da computação, a complexidade temporal de um algoritmo quantifica o montante de tempo tomado por este dado algoritmo rodar como uma função do comprimento de uma cadeia representando os dados de entradaSipser, Michael (2006).
Novo!!: Problema da árvore de Steiner e Complexidade temporal · Veja mais »
Computers and Intractability
Computers and Intractability: A Guide to the Theory of NP-Completeness (Computadores e Intratabilidade: Um guia para a Teoria da NP-completude, tradução livre, não há edição em português) é um livro de Michael Garey e David S. Johnson de grande influência em ciência da computação, mais especificamente em teoria da complexidade computacional.
Novo!!: Problema da árvore de Steiner e Computers and Intractability · Veja mais »
Conjectura
Uma conjectura é uma ideia, fórmula ou frase, a qual não foi provada ser verdadeira, baseada em suposições ou ideias com fundamento não verificado.
Novo!!: Problema da árvore de Steiner e Conjectura · Veja mais »
CRC Press
CRC Press é uma empresa de publicação de livros dos Estados Unidos, dedicada a distribuição de obras relacionadas à engenharia, ciência e matemática.
Novo!!: Problema da árvore de Steiner e CRC Press · Veja mais »
Desigualdade triangular
A desigualdade triangular tem origem na geometria euclidiana e refere-se ao teorema que afirma que, num triângulo, o comprimento de um dos lados é sempre inferior à soma dos comprimentos dos outros dois lados.
Novo!!: Problema da árvore de Steiner e Desigualdade triangular · Veja mais »
Distância euclidiana
A distância euclidiana em duas dimensões. Em matemática, distância euclidiana é a distância entre dois pontos, que pode ser provada pela aplicação repetida do teorema de Pitágoras.
Novo!!: Problema da árvore de Steiner e Distância euclidiana · Veja mais »
Elsevier
Logotipo da Elsevier Elsevier é uma empresa editorial holandesa especializada em conteúdo científico, técnico e médico.
Novo!!: Problema da árvore de Steiner e Elsevier · Veja mais »
Espaço métrico
métrica de Manhattan. Em matemática, um espaço métrico é um conjunto não-vazio onde as distâncias entre quaisquer de seus elementos é definida.
Novo!!: Problema da árvore de Steiner e Espaço métrico · Veja mais »
Esquema de aproximação de tempo polinomial
Em ciência da computação, um esquema de aproximação de tempo polinomial (PTAS) é um tipo de algoritmo de aproximação para problemas de otimização (na maioria das vezes, problemas de otimização NP-difíceis).
Novo!!: Problema da árvore de Steiner e Esquema de aproximação de tempo polinomial · Veja mais »
Estrela (teoria dos grafos)
Em teoria dos grafos, uma estrela Sk é o grafo bipartido completo K1,k, uma árvore com um nó interno e k folhas.
Novo!!: Problema da árvore de Steiner e Estrela (teoria dos grafos) · Veja mais »
Geometria do táxi
A Geometria do táxi, considerada por Hermann Minkowski no século XIX, é uma forma de geometria em que a usual métrica da geometria euclidiana é substituída por uma nova métrica em que a distância entre dois pontos é a soma das diferenças absolutas de suas coordenadas.
Novo!!: Problema da árvore de Steiner e Geometria do táxi · Veja mais »
Grafo completo
Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices.
Novo!!: Problema da árvore de Steiner e Grafo completo · Veja mais »
Grafo k-aresta-conexo
Na teoria dos grafos, um grafo é k-aresta-conexo se ele permanece conexo mesmo que (menos que) k arestas sejam retiradas.
Novo!!: Problema da árvore de Steiner e Grafo k-aresta-conexo · Veja mais »
Grafo k-vértice-conexo
Na teoria dos grafos, um grafo G é dito k-vértice-conexo (ou k-conexo) se tem mais de k vértices e permanece conexo sempre que são removidos k-1 vértices.
Novo!!: Problema da árvore de Steiner e Grafo k-vértice-conexo · Veja mais »
Grafo simples
Em teoria dos grafos, um grafo é simples se ele não tem laços nem mais de uma aresta ligando dois vértices.
Novo!!: Problema da árvore de Steiner e Grafo simples · Veja mais »
Grafo valorado
Um grafo valorado ou grafo ponderado é um grafo que possui funções relacionando o conjunto de vértices ou o conjunto de arestas a conjunto de números.
Novo!!: Problema da árvore de Steiner e Grafo valorado · Veja mais »
Heap
Em ciência da computação, um heap (monte) (pronuncia-se riːp) é uma estrutura de dados especializada, baseada em árvore, que é essencialmente uma árvore quase completa que satisfaz a propriedade heap: se P é um nó pai de C, então a chave (o valor) de P é maior que ou igual a (em uma heap máxima) ou menor que ou igual a (em uma heap mínima) chave de C. O nó no "topo" da heap (sem pais) é chamado de nó raiz.
Novo!!: Problema da árvore de Steiner e Heap · Veja mais »
Hiperônimo e hipônimo
é uma palavra que pertence ao mesmo campo semântico de outra mas com o sentido mais abrangente, podendo ter várias possibilidades para um único hipônimo.
Novo!!: Problema da árvore de Steiner e Hiperônimo e hipônimo · Veja mais »
Jakob Steiner
Jakob Steiner (Utzenstorf, 18 de março de 1796 — Berna, 1 de abril de 1863) foi um matemático suíço que trabalhou principalmente na área de geometria.
Novo!!: Problema da árvore de Steiner e Jakob Steiner · Veja mais »
Miloš Kössler
Miloš Kössler (Praga, – Praga) foi um matemático tcheco.
Novo!!: Problema da árvore de Steiner e Miloš Kössler · Veja mais »
NP-completo
Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.
Novo!!: Problema da árvore de Steiner e NP-completo · Veja mais »
NP-difícil
NP-difícil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP".
Novo!!: Problema da árvore de Steiner e NP-difícil · Veja mais »
Otimização combinatória
A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos.
Novo!!: Problema da árvore de Steiner e Otimização combinatória · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: Problema da árvore de Steiner e P versus NP · Veja mais »
Planejamento e design de rede
Planejamento e design de rede é um processo iterativo, abrangendo o projeto topológico, a síntese e a realização de(a) rede e visa garantir que uma nova rede de telecomunicações ou serviço atende às necessidades do assinante e da operadora.
Novo!!: Problema da árvore de Steiner e Planejamento e design de rede · Veja mais »
Plano (geometria)
paralelos no espaço Na matemática, um plano é um ente primitivo geométrico infinito a duas dimensões.
Novo!!: Problema da árvore de Steiner e Plano (geometria) · Veja mais »
Plano projectivo
Em geometria projetiva, o plano projectivo é obtido a partir do plano euclidiano acrescentando-se, para cada direção, um ponto impróprio, e uma reta imprópria que contém todos os pontos impróprios.
Novo!!: Problema da árvore de Steiner e Plano projectivo · Veja mais »
Ponto (matemática)
Em Matemática, particularmente na Geometria e na Topologia, um ponto é uma noção primitiva pela qual outros conceitos são definidos.
Novo!!: Problema da árvore de Steiner e Ponto (matemática) · Veja mais »
Ponto de Fermat
Construção do primeiro centro isogônico. Em geometria o ponto de Fermat de um triângulo, também chamado de ponto de Torricelli, é o ponto tal que a distância total dos três vértices do triângulo até esse ponto é a menor possível (i.e. a soma das distâncias deste ponto aos vértices é mínima).
Novo!!: Problema da árvore de Steiner e Ponto de Fermat · Veja mais »
Problema de cobertura de conjuntos
O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional.
Novo!!: Problema da árvore de Steiner e Problema de cobertura de conjuntos · Veja mais »
Problema de decisão
Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.
Novo!!: Problema da árvore de Steiner e Problema de decisão · Veja mais »
Problema de otimização
Problema de otimização, em matemática ou ciência da computação, é um problema de encontrar a melhor solução de todas as soluções viáveis.
Novo!!: Problema da árvore de Steiner e Problema de otimização · Veja mais »
Problema do caixeiro-viajante
O problema do caixeiro-viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem.
Novo!!: Problema da árvore de Steiner e Problema do caixeiro-viajante · Veja mais »
Problema do caminho mínimo
O caminho mínimo entre ''D'' e ''E'' não é D-E, mas sim D-F-E, com uma distância de 14. Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.
Novo!!: Problema da árvore de Steiner e Problema do caminho mínimo · Veja mais »
Programação linear
Exemplo de poliedro (bidimensional) resultante das condições de um problema de programação linear. Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.
Novo!!: Problema da árvore de Steiner e Programação linear · Veja mais »
Reta
eixo y no mesmo local). Uma representação de um segmento de reta. A noção de ou linha reta foi introduzida por matemáticos antigos para representar objetos retos (isto é, sem curvatura) com largura e profundidade desprezíveis.
Novo!!: Problema da árvore de Steiner e Reta · Veja mais »
Ronald Graham
Ronald Lewis Graham (Taft, — San Diego, 6 de julho de 2020) foi um matemático estadunidense.
Novo!!: Problema da árvore de Steiner e Ronald Graham · Veja mais »
Simpósio da Teoria da Computação
STOC, o Simpósio Anual da ACM de Teoria da Computação é uma conferência acadêmica no campo da teoria da ciência da computação.
Novo!!: Problema da árvore de Steiner e Simpósio da Teoria da Computação · Veja mais »
Software de projeto de circuitos integrados
Um software de projeto de circuitos integrados (do inglês Electronic design automation, ou simplesmente EDA) refere-se a uma categoria de ferramentas focadas no projeto, concepção e produção de sistemas eletrônicos, abrangendo desde o projeto de circuitos integrados até o desenho de placas de circuito impresso.
Novo!!: Problema da árvore de Steiner e Software de projeto de circuitos integrados · Veja mais »
Springer Science+Business Media
Springer Science+Business Media ou Springer-Verlag, ou ainda, simplesmente Springer é uma editora mundial baseada na Alemanha, a qual publica livros-texto, livros de referência acadêmica, e periódicos de artigos com revisão por pares (peer-review), com foco em ciência, tecnologia, matemática, e medicina.
Novo!!: Problema da árvore de Steiner e Springer Science+Business Media · Veja mais »
Subconjunto
Diagrama de Euler ilustrando o fato de que A é subconjunto de B ou, equivalentemente, que B é superconjunto de A Em teoria dos conjuntos, quando todo elemento de um conjunto A é também elemento de um conjunto B, dizemos que A é um subconjunto de B, denotado A \subseteq B (também dito "A é uma parte de B" ou "A está contido em B").
Novo!!: Problema da árvore de Steiner e Subconjunto · Veja mais »
Supremo e ínfimo
Em matemática, definem-se os conceitos de majorante/cota superior, minorante/cota inferior, máximo, mínimo, supremo e ínfimo.
Novo!!: Problema da árvore de Steiner e Supremo e ínfimo · Veja mais »
Toro (topologia)
Animação Toróide Toro ou toróide é um espaço topológico homeomorfo ao produto de dois círculos.
Novo!!: Problema da árvore de Steiner e Toro (topologia) · Veja mais »
União-busca
Em ciência da computação, uma estrutura de dados união-busca também chamado de estrutura de dados disjoint-set é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos (não sobreposicionados).
Novo!!: Problema da árvore de Steiner e União-busca · Veja mais »
Vojtěch Jarník
Vojtěch Jarník (Praga, — Praga) foi um matemático tcheco Sua principal área de trabalho foi a teoria dos números e análise matemática.
Novo!!: Problema da árvore de Steiner e Vojtěch Jarník · Veja mais »
W. H. Freeman and Company
W.
Novo!!: Problema da árvore de Steiner e W. H. Freeman and Company · Veja mais »
World Scientific
World Scientific é uma empresa de publicação acadêmica de Singapura fundada em 1981 e creditada pela distribuição de mais de 500 obras científicas, técnicas e medicinais.
Novo!!: Problema da árvore de Steiner e World Scientific · Veja mais »
21 problemas NP-completos de Karp
Na teoria da complexidade computacional, os 21 problemas NP-completos de Karp é um conjunto de problemas computacionais que são NP-completos.
Novo!!: Problema da árvore de Steiner e 21 problemas NP-completos de Karp · Veja mais »
