No contexto da análise de algoritmos, as notações assintóticas são utilizadas para descrever o comportamento do tempo de execução em função do tamanho da entrada. Com base nas definições de Big O, little o e Ω, informe se é verdadeiro (V) ou falso (F) o que se afirma a seguir e assinale a alternativa com a sequência correta.
( ) A notação Big O (O(g(n))) define um limite superior assintótico, indicando que o algoritmo cresce no máximo como g(n). ( ) A notação little o (o(g(n))) define um limite superior estrito, indicando que a taxa de crescimento é estritamente menor que g(n). ( ) A notação Ω(g(n)) define um limite intermediário assintótico, sendo comumente empregada para expressar o pior caso de execução de um algoritmo. ( ) A notação Θ(g(n)) define um limite inferior assintótico, garantindo que o algoritmo cresce pelo menos como g(n).

Um professor do IFCE solicitou que os alunos projetassem a rede interna de um novo laboratório de informática, conectando todos os computadores de forma a minimizar o custo total e sem gerar ciclos. O professor explicou que a estratégia consiste em iniciar a árvore a partir de um computador específico e, iterativamente, adicionar a conexão de menor custo que ligue a árvore a um computador ainda não conectado, até integrar todos os computadores. Com base nesse cenário, qual é o algoritmo utilizado para construir a árvore geradora de custo mínimo?

Na Teoria da Computação, a Tese de Church-Turing estabelece uma relação entre o conceito intuitivo de algoritmo e modelos formais de computação, como a Máquina de Turing. Embora não seja um teorema formalmente demonstrado, é amplamente aceita como uma hipótese sobre os limites do que pode ser computado. Com base nessa concepção, assinale a alternativa que expressa corretamente o conteúdo da Tese de Church-Turing.

Em um sistema de mapeamento urbano, os cruzamentos são vértices e as ruas são arestas de um grafo. Para analisar a conectividade e verificar quais regiões podem ser alcançadas a partir de um ponto inicial, a equipe utiliza Busca em Largura (BFS) e Busca em Profundidade (DFS). Considerando que o grafo é representado por lista de adjacência e que ambos os algoritmos percorrem todos os vértices e arestas alcançáveis, assinale a alternativa que apresenta corretamente a complexidade de tempo no pior caso para BFS e DFS.

Um professor do IFCE desafia seus alunos a refletirem sobre os limites da formalização matemática. Ele propõe a seguinte situação: Um matemático desenvolve um sistema formal consistente e suficientemente poderoso para expressar toda a aritmética básica. Apesar de definir axiomas claros e as regras de inferência rigorosas, ele percebe que existem proposições dentro desse sistema que, embora sejam verdadeiras, não podem ser demonstradas apenas com os axiomas e regras definidas. Além disso, o matemático tenta provar que o próprio sistema não contém contradições, mas descobre que isso não é possível apenas com os recursos internos do sistema. Com base nessa situação, assinale a alternativa que indica corretamente o teorema que formaliza essas limitações de sistemas matemáticos.

A respeito das plataformas de multimídia e dos tipos de mídia suportados, analise as assertivas e assinale a alternativa que aponta as corretas.
I. Plataformas de áudio permitem captura, edição, mixagem e reprodução de sons, sendo compatíveis com formatos como MP3 (MPEG Audio Layer III), WAV (Waveform Audio File Format) e AAC (Advanced Audio Coding). II. Plataformas de imagens oferecem recursos de edição, compressão e transformação de fotos e ilustrações, utilizando softwares como Photoshop, GIMP (GNU Image Manipulation Program) e CorelDRAW. III. Plataformas de vídeo suportam captura, reprodução, edição de clipes e transmissões ao vivo, aceitando formatos como MP4 (MPEG-4 Part 14), AVI (Audio Video Interleave) e MOV (QuickTime Movie). IV. Plataformas de áudio e vídeo podem ser manipuladas com as mesmas ferramentas, como Audacity, Adobe Premiere e Final Cut, sem que seja necessário utilizar softwares específicos para cada tipo de mídia.

Um pesquisador do IFCE está utilizando Algoritmos Genéticos para otimizar a distribuição de horários das turmas em um campus. Cada solução candidata é representada por uma sequência de valores, onde cada posição da sequência corresponde a uma variável, como horário atribuído a uma disciplina, sala utilizada ou professor responsável. Dentro desse modelo, cada uma dessas variáveis pode ser vista como a 'menor unidade' de uma solução. Considerando o contexto descrito, assinale a alternativa que denomina corretamente essa ‘menor unidade de informação’ em uma solução candidata

Em algoritmos de otimização local, existe uma técnica que inicia com uma solução candidata e, a cada iteração, avalia modificações possíveis, sempre escolhendo aquela que proporciona o maior aumento imediato na função objetivo. O algoritmo não aceita soluções que reduzam o valor da função, o que pode levar a ficar preso em máximos locais, sem garantir o valor global ótimo. Com base nessas características, é correto afirmar que o algoritmo descrito é

Nos compiladores, a tabela de símbolos é uma estrutura utilizada para organizar informações relacionadas aos identificadores de um programa. Assinale a alternativa que descreve corretamente o funcionamento dos identificadores.