O algoritmo de Floyd-Warshall resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo orientado (com direção) e valorado (com peso).
Sobre o algoritmo e dado que V é o número de vértices e E o número de arestas do grafo, podemos afirmar que:
Analise as afirmativas referentes ao algoritmo de Dijkstra, e assinale V para as alternativas verdadeiras e F para as falsas.
( ) O algoritmo de Dijkstra é ótimo para a situação do problema do caminho mínimo.
( ) O algoritmo de Dijkstra consegue encontrar o menor caminho em um grafo com pesos negativos.
A partir dessa análise, assinale a sequência CORRETA.
Analise as afirmativas referentes à classe de problemas computacionais e assinale V para as alternativas verdadeiras e F para as falsas.
( ) Sejam A, B dois problemas tais que A ϵ NP - Completo e B ϵ P. Então, B é polinomialmente transformável em A, somente se P = NP.
( ) Todo problema P não pertence à classe de problemas NP.
A partir dessa análise, assinale a sequência CORRETA.
Numere as estruturas de dados da COLUNA II com os algoritmos apresentados na COLUNA I.
Assinale a alternativa que apresenta a sequência CORRETA.
O formato de uma moldura de página da arquitetura (fictícia) k86 reserva os bits 0 a 23 para o endereço da moldura de página na memória física, usados para indexar a tabela de páginas.
Admitindo um sistema de memória virtual paginada com tamanho de página de 2K bytes, assinale a alternativa que apresenta qual a quantidade máxima CORRETA de memória que um processo pode usar.
Analise as afirmativas que tratam dos algoritmos de processamento de caracteres, assinalando V para as afirmativas verdadeiras e F para as falsas.
( ) O algoritmo Knuth–Morris–Pratt (KMP) é mais eficiente quando maior for o tamanho do padrão de busca.
( ) O algoritmo de busca em autômatos não tem necessidade de retroceder para reler a entrada do texto.
A partir dessa análise, assinale a sequência CORRETA.
Analise as afirmativas concernentes aos algoritmos de processamento de caracteres, assinalando V para as afirmativas verdadeiras e F para as falsas.
( ) O algoritmo Boyer-Moore é mais eficiente quanto maior for o tamanho do padrão de busca.
( ) Os algoritmos Shift-And e Knuth–Morris–Pratt (KMP) não tem necessidade de retroceder para reler a entrada do texto.
A partir dessa análise, assinale a sequência CORRETA.
Resolva a relação de recorrência a seguir:
T(n) = 2T(n/2) + n2
O resultado será:
