Algoritmos e Programação II (SENAC) - 2023

Prévia do material em texto

Aula 01
Representação de uma Variável
tipo de dado + nome da variável = valor da variável
Exemplos:
double altura = 1.80;
int peso = 75;
bool quitação_eleitoral = true;
Estrutura de Dados Linear (Vetor ou Array Unidimensional)
Variáveis que possuem uma relação entre si;
Possuem o mesmo tipo de dado;
Possuí índice e posição (índice = posição – 1);
Possuem apenas linhas.
Declaração e Atribuição dos Valores em uma única Instrução:
tipo_de_dado[ ] nome_do_vetor = {valor_pos_0, valor_pos_1, ..., valor_ultima_pos};
Exemplos:
int[ ] anos = { 9, 11, 14, 17 };
double[ ] pesos = { 67.5, 72.5, 89.4, 92.7 }
Declaração do Vetor com o tamanho definido para posteriormente receber Valores:
tipo_de_dado[ ] nome_do_vetor = new tipo_de_dado[tamanho_do_vetor];
Exemplos:
int[ ] idades = new int[10];
double[ ] pesos = new double[10];
O número 10 representa o tamanho do vetor, nesse caso terá 10 posições, começando no índice 0 e terminando no índice 9.
Declaração do vetor sem predefinição do tamanho:
Dessa forma, primeiramente declara-se o vetor, depois define-se o tamanho do vetor e, por fim, o valor de cada posição.
tipo_de_dado[ ] nome_do_vetor;
nome_do_vetor = new tipo_de_dado[tamanho_do_vetor];
Exemplo:
double[ ] notas;
notas = new double[3];
3 formas de representar um vetor:
Sabemos o tamanho do vetor e seus valores:
int[ ] idades = { 10, 12, 14 };
Sabemos apenas o tamanho do vetor, não sabemos seus valores:
int[ ] idades = new int[10];
Não sabemos o tamanho do vetor, nem seus valores:
int[ ] idades;
Aula 02
Estrutura de Dados (Matriz ou Array Bidimensional)
Variáveis que possuem uma relação entre si;
Possuem o mesmo tipo de dado;
Possuí índice e posição (índice = posição – 1);
Possuem linhas e colunas.
Representação:
float[ , ] pesos = { { 17.8, 22.8, 34.8 }, { 23.9, 44.7, 89.7 } };
3 formas de representar uma matriz:
Sabemos o tamanho da matriz e seus valores:
int[ , ] idades = {{ 10, 12, 14 }, { 13, 23, 78 }};
Sabemos apenas o tamanho da matriz, não sabemos seus valores:
int[ , ] idades = new int[10, 5];
Não sabemos o tamanho da matriz, nem seus valores:
int[ , ] idades;
Aula 03 e Aula 04
Algoritmos de Busca em Vetores:
Busca Linear ou Sequencial
Busca Binária (menos iterações que a busca linear para encontrar o valor)
Busca Linear:
. Os valores não precisam estar ordenados no vetor.
Busca Binária:
. Todos os valores precisam estar ordenados no vetor em ordem crescente;
. Segue o método de divisão e conquista;
. Caso haja um valor par de índices, o índice central é arredondado para o menor valor.
	
EFICIÊNCIA de Algoritmos
	
Busca Linear
	Função Linear
	O(n)
	
Busca Binária
	Função Logarítmica
	O(log2n)
Aula 05
Ordenação pelo Método Bolha (Bubble Sort)
. A ordenação pelo método bolha procura posicionar os maiores elementos ao final do vetor;
. Em uma passada pelo vetor (n operações), o maior elemento será alocado na última posição;
. Uma passada pelo vetor sem nenhuma ocorrência de alteração de posição dos elementos indica que ele já está ordenado e, portanto, não é mais necessário repetir essas passadas até um total de n, podendo-se encerrar o algoritmo;
. Cada passada não precisa percorrer todo o vetor, pois, garantidamente, os últimos elementos estão ordenados; assim, a cada passada, é necessário ir até o elemento anterior ao último ordenado na passada anterior.
Exemplo: https://shre.ink/QEsP
Ordenação por Seleção (Selection Sort)
. A ordenação por seleção troca um elemento na parte inicial pelo menor elemento que há no restante do vetor a cada iteração;
. O algoritmo procurará o menor elemento a partir da posição inicial (0) e o trocará com o da posição 0. Em seguida, buscará o menor elemento a partir da posição 1 e o trocará com o da posição 1 – repetindo o processo até ordenar todo o vetor.
Exemplo: https://shre.ink/QEhO
Ordenação por Inserção (Insertion Sort)
. Busca os menores elementos no restante do vetor para posicioná-los ordenadamente no início.
Exemplo: https://shre.ink/QEHr
Resumo Geral: https://shre.ink/QEKR
	
EFICIÊNCIA de Algoritmos
	
Bubble Sort
	Função Quadrática
	O(n²)
	
Selection Sort
	Função Quadrática
	O(n²)
	
Insertion Sort
	Função Quadrática
	O(n²)
Aula 06
Função Recursiva
. É uma função que chama a si mesma;
. Uma chamada recursiva a si mesma com parâmetros sempre diferentes;
. Um critério de parada para evitar o loop infinito.
Um problema recursivo é representado pelo princípio matemático da indução, por meio do qual partimos da observação de diversos casos particulares para estabelecer uma conclusão. A demonstração da solução pelo método da indução contém duas partes:
1. Passo base: solução para o caso mais básico.
2. Passo indutivo: solução para os demais casos, sendo cada um expresso em função do anterior.
Aula 07
Algoritmos de Ordenação Eficientes
MergeSort:
. Uso de recursão;
. Método da Divisão e Conquista;
. Ponto do vetor em que ocorrerá a divisão ocorre sempre no meio.
Exemplo: https://shre.ink/Qsv2
QuickSort:
. Uso de recursão;
. Método da Divisão e Conquista;
. Ponto do vetor em que ocorrerá a divisão chamado de pivô (nem sempre será no meio do vetor).
Exemplo: https://shre.ink/Qsvc
	
EFICIÊNCIA de Algoritmos
	
MergeSort
	Função Logarítmica
	O(n log n)
	
QuickSort
	Função Quadrática
	O(n²)
	
Conhecemos novos algoritmos de ordenação que, baseados na técnica da recursividade, conseguem ser mais eficientes que os algoritmos de ordenação elementares.
Aula 08
A criação de um objeto de uma classe é feita pela seguinte sintaxe:
nome_classe nome_objeto = new nome_classe(valores_dos_atributos)
Chamar um método de um objeto, utiliza-se a seguinte sintaxe:
nome_objeto <ponto> nome_método
Exercícios Gerais
Depois de criado um array não podemos adicionar ou remover posições.
Para encontrar o elemento do meio em um vetor com tamanho par, você pode seguir os seguintes passos:
Obtenha o tamanho do vetor.
Divida o tamanho por 2, arredondando para baixo, se necessário. Isso fornecerá a posição do elemento do meio.
Acesse o elemento do vetor com a posição obtida no passo anterior.
Aqui está um exemplo { 5, 10, 12, 38, 45, 61, 65, 69, 81, 89, 98, 100 }:
O tamanho do vetor é 12.
12 dividido por 2 é igual a 6.
O elemento do meio está na posição 6.
Acessando o elemento na posição 6, encontramos o valor 61.
Portanto, o elemento que ocupa o meio do vetor é 61.
Método Auxiliar Não Recursivo do MergeSort = Intercalar
Método Auxiliar Não Recursivo do QuickSort = Particionar