Algoritmos Flashcards
Quais são os tipos de dados primitivos utilizados em algoritmos?
- Inteiros: Representam números inteiros, positivos ou negativos, sem casas decimais (ex: -5, 0, 10).
- Reais: Representam números reais, com ou sem casas decimais (ex: 3.14, -2.5).
- Caracteres: Representam um único caractere, como uma letra, um número ou um símbolo (ex: ‘a’, ‘5’, ‘*’).
- Strings: Representam sequências de caracteres, ou seja, textos (ex: “Olá, mundo!”, “123”).
- Booleanos: Representam valores lógicos, verdadeiro ou falso (ex: True, False).
_NÃO EXISTE DADO CONSTANTE_
Em Portugol, o que são vetores bidimensionais ou matrizes?
Definição
É uma estrutura de dados que organiza informações em linhas e colunas, similar a uma tabela. Cada elemento da matriz é identificado por um par de índices: um para a linha e outro para a coluna.
Snippet de código
tipo_de_dado nome_da_matriz[numero_de_linhas, numero_de_colunas]
Exemplo
inteiro notas[3, 4] // Matriz para armazenar as notas de 3 alunos em 4 provas
Para a FUNDATEC também é possível escrever:
Vetor [1..10,1..3]
Criando assim, um vetor onde se tem 10 linhas e 3 colunas._
Sintase:
- Utilize a palavra vetor para declarações de matrizes (só vetor);
- Especifique os índices entre colchetes [ ];
- Defina o tipo de dados após a palavra de.
- Não se pode utilizar atribuição (<-). Apenas m: vetor [1…10,1..3] de inteiro
Como se inicializa uma matriz em Portugol?
Elemento por elemento
notas[1, 1] <- 8
notas[1, 2] <- 7
// …
Na declaração
inteiro notas[3, 4] = {{8, 7, 9, 10}, {6, 5, 8, 7}, {9, 8, 9, 10}}
Utilizando um laço
para linha de 1 ate 3 faca
para coluna de 1 ate 4 faca
leia(notas[linha, coluna])
fimpara
fimpara
Como se percorre uma matriz em Portugol?
para linha de 1 ate 3 faca
para coluna de 1 ate 4 faca
escreva(notas[linha, coluna], “ “)
fimpara
escreva(“\n”)
fimpara
Como se declara uma variável em Portugol?
Existem duas formas:
- Iniciar com “var” e, posteriormente, declarar o nome da variável e o tipo de dado que estará nela:
var
nome_da_variável: tipo_de_dado
- Ou, declarar a variável diretamente:
tipo_de_dado nome_da_variavel
Como se utiliza o Loop ‘Para’ em Portugol?
Definição
Permite repetir um bloco de código um determinado número de vezes. Ele é especialmente útil quando você precisa realizar uma mesma operação várias vezes ou percorrer todos os elementos de um vetor.
Sintaxe
para variavel_controle de valor_inicial ate valor_final faca
// Bloco de código a ser repetido
fimpara
variavel_controle: Uma variável que controla o número de repetições. Seu valor é incrementado a cada iteração do loop.
valor_inicial: O valor inicial da variável de controle.
valor_final: O valor final da variável de controle. O loop continua enquanto a variável de controle for menor ou igual a este valor.
Bloco de código: As instruções que serão executadas a cada repetição do loop.
Exemplo
para i de 1 ate 5 faca
escreva(i, “ “)
fimpara
Qual é a finalidade principal da análise de algoritmos?
Determinar os recursos necessários para executar um dado algoritmo.
A análise de algoritmos tem como principal objetivo avaliar o desempenho de um algoritmo em termos de recursos computacionais que ele consome. Esses recursos podem incluir o tempo de execução (complexidade temporal) e a quantidade de memória utilizada (complexidade espacial). Ao fazer essa análise, podemos determinar qual algoritmo é mais eficiente para resolver um problema específico, levando em conta os recursos que ele consome.
Como se dá a ordenação por inserção?
*Como funciona:
1.Lista Original: No início, você tem uma lista desordenada que contém todos os elementos.
2.Sublista Ordenada: O algoritmo começa considerando que o primeiro elemento da lista forma uma sublista ordenada (com apenas um elemento). À medida que avança, ele “expande” essa sublista ordenada.
3.Inserção de Elementos: Para cada novo elemento que o algoritmo processa (começando do segundo elemento), ele o insere na posição correta da sublista ordenada. O algoritmo move os elementos da sublista que são maiores do que o novo elemento, criando espaço para a inserção.
4.Repetição: Esse processo se repete até que todos os elementos da lista original tenham sido processados e a sublista ordenada contenha todos os elementos da lista.
*Código
//
~~~
for i in ragne(1,len(arr)):
chave = arr[i] #Aqui colocamos o elemento posterior
j = i -1 #Aqui utilizaremos j para marcar o elemento anterior a chave
while j >=0 and arr[j] > chave:
arr[j+1] = arr[j]
j = j - 1
#Cada vez que o arr[j] for maior que a chave, significa que o vetor ainda está fora de ordem. Com isso, há a troca ‘arr[j+1] = arr[j]’. Após, diminuímos mais um número em j para continuar a comparação.
#Como a chave é o elemento ‘inserido’, ela não muda até arr[j] ser menor que ela.
#O ‘j>=0’ serve para mostrar que o vetor chegou ao início e que a chave é o menor elemento do vetor.
arr[j+1] = chave
#Quando arr[j] for menor que a chave, significa que encontramos a posição. Com isso, a chave deve ficar após o arr[j]
~~~
//
Complexidade
- Melhor caso: Ocorre quando o vetor já está ordenado. Nesse cenário, o algoritmo realiza apenas uma comparação por elemento, resultando em uma complexidade linear de O(n).
- Pior caso: Ocorre quando o vetor está ordenado de forma inversa. Nesse caso, o algoritmo precisa realizar o maior número possível de comparações e movimentações, resultando em uma complexidade quadrática de O(n²).
- Caso médio: A complexidade do caso médio também é O(n²).
Comentário:
É estável já que ele não altera a ordem relativa dos elementos com valores iguais.
Como funciona o método de ordenação por bolha?
Como funciona:
1.Comparação de pares: O algoritmo percorre a lista, comparando pares de elementos adjacentes.
2.Troca: Se os elementos estiverem na ordem incorreta (por exemplo, se o elemento anterior for maior que o posterior), eles são trocados de posição.
3.Repetição: Esse processo de comparação e troca é repetido várias vezes até que a lista esteja completamente ordenada. A cada iteração, o maior elemento “flutua” para o final da lista, como uma bolha em um líquido, daí o nome do algoritmo.
Código
// algoritmo bolha
var
vetor: vetor[1..10] de inteiro // Adapte o tamanho do vetor
i, j, aux: inteiro
// Leitura dos dados do vetor (não mostrado aqui)
para i de 1 ate tamanho(vetor) - 1 faca
para j de 1 ate tamanho(vetor) - i faca
se vetor[j] > vetor[j + 1] entao
// Trocar os elementos
aux <- vetor[j]
vetor[j] <- vetor[j + 1]
vetor[j + 1] <- aux
fimse
fimpara
fimpara
// Impressão do vetor ordenado (não mostrado aqui) fim_algoritmo
Complexidade
-Pior caso e caso médio: O(n²), onde n é o número de elementos. Isso ocorre porque o algoritmo precisa percorrer a lista inteira em cada iteração, e o número de iterações pode ser igual ao número de elementos.
-Melhor caso: O(n), se a lista já estiver ordenada, mas isso raramente acontece na prática.
Comentário:
É estável já que ele não altera a ordem relativa dos elementos com valores iguais.
Como se dá a ordenação por seleção?
Definição:
A ordenação por seleção (ou Selection Sort) é um algoritmo simples que ordena uma lista repetidamente encontrando o menor (ou maior, dependendo da ordem) elemento da lista e trocando-o com o primeiro elemento da parte não ordenada. Esse processo é repetido até que toda a lista esteja ordenada.
Como funciona:
Encontre o menor elemento: O algoritmo percorre a lista e encontra o menor elemento.
Troque de posição: Troca esse menor elemento com o primeiro elemento da lista não ordenada.
Repita o processo: Agora, considere o próximo elemento como o início da lista não ordenada e repita o processo até que todos os elementos estejam ordenados.
Código:
//algoritmo selecao
var
vetor: vetor[1..10] de inteiro // Adapte o tamanho do vetor
i, j, min_idx, aux: inteiro
// Leitura dos dados do vetor (não mostrado aqui)
para i de 0 ate tamanho(vetor) - 2 faca
min_idx <- i
para j de i + 1 ate tamanho(vetor) - 1 faca
se vetor[j] < vetor[min_idx] entao
min_idx <- j
fimse
fimpara
// Trocar os elementos
aux <- vetor[min_idx]
vetor[min_idx] <- vetor[i]
vetor[i] <- aux
fimpara
// Impressão do vetor ordenado (não mostrado aqui) fim_algoritmo
Complexidade:
-Pior caso e caso médio: O(n²), onde n é o número de elementos. Isso ocorre porque o algoritmo precisa percorrer a lista inteira em cada iteração para encontrar o menor elemento.
Qual a diferença entre procedimento e função?
Procedimento
- Definição: Um procedimento é um bloco de código que executa uma sequência de instruções, mas não retorna um valor. Ele é usado principalmente para realizar ações, como manipular dados ou executar tarefas.
- Uso: Geralmente é chamado quando se deseja realizar uma operação específica, sem a necessidade de um retorno.
- Exemplo: Um procedimento pode ser responsável por imprimir uma mensagem na tela ou atualizar o estado de uma variável.
Função
- Definição: Uma função é um bloco de código que também executa instruções, mas, diferentemente do procedimento, ela retorna um valor ao seu chamador. Esse valor pode ser de diferentes tipos, como inteiro, string, etc.
- Uso: Funções são usadas quando é necessário obter um resultado a partir de um conjunto de dados ou realizar cálculos.
- Exemplo: Uma função pode calcular a soma de dois números e retornar esse valor.
O que é modularização?
Definição
É um princípio de design em programação que consiste em dividir um programa em módulos ou componentes menores e independentes. Cada módulo encapsula uma parte específica da funcionalidade do software, facilitando a compreensão, o desenvolvimento e a manutenção do código.
Vantagens
- A independência do módulo permite uma manutenção mais simples e evita efeitos colaterais em outros pontos do algoritmo.
- O módulo pode ser feito independentemente do restante do algoritmo e pode usar objetos globais.
- Um módulo independente pode ser utilizado em outros algoritmos que requeiram o mesmo processamento por ele executado.
- Testes e correções dos módulos podem ser feitos em separado.
- elaboração do módulo pode ser feita independentemente e em época diferente do restante do algoritmo.
O que seria o aprendizado supervisionado?
Aprendizado supervisionado é uma técnica de aprendizado de máquina em que um modelo é treinado usando um conjunto de dados rotulado. Isso significa que cada exemplo no conjunto de dados é composto por entradas (ou características) e saídas conhecidas (ou rótulos).
Como Funciona:
1.Conjunto de Dados: O modelo é alimentado com um conjunto de dados que contém pares de entrada e saída. Por exemplo, em um modelo que prevê preços de casas, as entradas podem incluir características como tamanho, localização e número de quartos, enquanto as saídas seriam os preços reais das casas.
2.Treinamento: O modelo aprende a relação entre as entradas e as saídas. Durante o treinamento, ele ajusta seus parâmetros internos para minimizar a diferença entre suas previsões e os valores reais.
3.Avaliação: Após o treinamento, o modelo é avaliado em um conjunto de dados separado (conjunto de teste) para verificar sua capacidade de generalização — ou seja, como ele se comporta com dados que não viu durante o treinamento.
4.Previsão: Uma vez treinado, o modelo pode ser usado para fazer previsões sobre novos dados, onde as saídas são desconhecidas.
Vantagens:
- Precisão: Modelos supervisionados podem alcançar alta precisão quando há dados rotulados suficientes.
Interpretação: Os resultados podem ser mais facilmente interpretáveis, uma vez que se sabe qual saída corresponde a cada entrada.
Desafios:
- Necessidade de Dados Rotulados: O aprendizado supervisionado requer um grande conjunto de dados rotulados, o que pode ser caro e demorado para obter.
- Overfitting: O modelo pode se tornar excessivamente complexo e se ajustar muito aos dados de treinamento, perdendo a capacidade de generalização.
Esses elementos fazem do aprendizado supervisionado uma abordagem fundamental em várias áreas, como reconhecimento de padrões, diagnóstico médico e previsão de vendas.
O que é aprendizado não supervisionado?
Aprendizado não supervisionado é uma técnica de aprendizado de máquina em que um modelo é treinado usando um conjunto de dados sem rótulos. Isso significa que as entradas são apresentadas ao modelo sem informações sobre as saídas ou categorias associadas.
Como Funciona:
1.Conjunto de Dados: O modelo recebe um conjunto de dados que contém apenas as entradas, sem qualquer anotação ou rótulo.
2.Treinamento: O modelo tenta identificar padrões ou estruturas subjacentes nos dados. Ele pode agrupar dados semelhantes ou reduzir a dimensionalidade para facilitar a visualização.
3.Análise: O modelo fornece insights sobre a estrutura dos dados, como agrupamentos ou associações.
Aplicações:
- Agrupamento (Clustering): Agrupar dados em clusters com base em características similares (ex: segmentação de clientes).
- Redução de Dimensionalidade: Reduzir o número de variáveis em um conjunto de dados, preservando as características mais importantes (ex: PCA - Análise de Componentes Principais).
- Detecção de Anomalias: Identificar padrões incomuns ou anômalos nos dados (ex: fraudes).
Vantagens:
- Sem Necessidade de Dados Rotulados: Pode ser utilizado em situações onde rotular dados é difícil ou caro.
- Exploração de Dados: Permite explorar e descobrir padrões ocultos nos dados que podem não ser evidentes.
Desafios:
- Interpretação dos Resultados: Os resultados podem ser mais difíceis de interpretar, já que não há rótulos conhecidos para validar os agrupamentos.
- Escolha de Parâmetros: A eficácia de alguns algoritmos depende da escolha de parâmetros, como o número de clusters, que pode ser subjetivo.
Esses aspectos tornam o aprendizado não supervisionado uma abordagem valiosa em diversas áreas, como análise de mercado, biologia, e análise de dados em geral.
O que seria aprendizado por esforço?
Aprendizado por esforço (ou apprentissage par renforcement) é uma técnica de aprendizado de máquina em que um agente aprende a tomar decisões através da interação com um ambiente. O agente realiza ações e recebe feedback na forma de recompensas ou penalidades, que o ajudam a entender quais ações são mais benéficas para alcançar um objetivo.
Como Funciona:
1.Agente e Ambiente: O agente é o aprendiz que interage com o ambiente, que pode ser qualquer sistema ou situação em que as ações do agente têm consequências.
2.Ações e Estados: O agente executa ações que podem mudar o estado do ambiente. Cada ação pode levar a diferentes estados, dependendo das condições.
3.Recompensas e Penalidades: Após realizar uma ação, o agente recebe uma recompensa (ou penalidade) com base na qualidade da ação em relação ao objetivo que deseja alcançar. O objetivo é maximizar as recompensas ao longo do tempo.
4.Aprendizado: O agente usa algoritmos de aprendizado para ajustar suas estratégias, aprendendo quais ações levarão a melhores recompensas em diferentes estados.
Aplicações:
-Jogos: Treinamento de agentes para jogar jogos complexos (ex: xadrez, Go).
-Robótica: Desenvolvimento de robôs que aprendem a realizar tarefas em ambientes dinâmicos.
-Sistemas de Recomendação: Otimização de sugestões para usuários com base em suas interações.
Vantagens:
-Adaptação Dinâmica: O agente pode aprender e se adaptar a ambientes em constante mudança.
-Exploração e Exploração: O aprendizado por esforço equilibra a exploração de novas ações e a exploração de ações conhecidas que trazem recompensas.
Desafios:
-Tempo de Treinamento: O processo pode ser demorado, pois o agente precisa de muitas interações para aprender efetivamente.
-Recompensas Espalhadas: Em alguns casos, as recompensas podem ser raras ou difíceis de obter, tornando o aprendizado mais complexo.
O aprendizado por esforço é uma abordagem poderosa que tem sido utilizada com sucesso em diversos campos, incluindo jogos, robótica, e otimização de processos.
