Entendendo Algoritmos - Aditya Y. Bhargava

Status: leitura em andamento. Próxima etapa: Implementar testes em python para os algoritmos abordados.

Olá! Essas são algumas das minhas anotações e considerações sobre o livro Entendendo Algoritmos de Aditya Y. Bhargava. O autor possui a incrível habilidade de ensinar conceitos complexos de forma divertida e quase palpável. Li este livro pela primeira vez no início do primeiro semestre da faculdade com pouca bagagem teórica, e ainda assim, pude compreender conceitos fundamentais de Ciência da Computação. Retornando a leitura no segundo semestre, posso dizer que é um livro que tem feito total diferença na minha forma de enxergar a programação e como as coisas funcionam por baixo dos panos. Recomendo demais e provavelmente é um livro que lerei novamente outras vezes.

Pilha de Chamada - Call stack#

É uma estrutura de dados do tipo LIFO (Last In, First Out - o último a entrar é o primeiro a sair) - usada pelo interpretador para gerenciar a execução de funções em um programa.

def funcao_c():
    print("Executando C")

def funcao_b():
    funcao_c()
    print("Executando B")

def funcao_a():
    funcao_b()
    print("Executando A")

funcao_a()

Executando C
Executando B
Executando A

Cada elemento inserido na call stack é chamado de Stack Frame (ou quadro de pilha). Cada frame aloca memória para guardar:

• as variáveis locais da função;
• os parâmetros passados para a função
• o endereço de retorno (a instrução de onde a CPU deve ir apos terminar a função)

A call stack possui um limite fixo de memoria alocado pelo ambiente de execução. Se as funções forem empilhadas indefinidamente sem retornar, a memoria da pilha é esgotada, gerando o erro de Stack Overflow.

def recursao_infinita():
	recursao_infinita() # Nunca tem um retorno, empilha infinitamente

recursao_infinita()
#Erro em python: RecursionError: maximum recursion depth exceeded

O custo de usar uma pilha é o espaço que é utilizado na memória. Cada função ocupa um espaço e quando a pilha esta muito cheia temos duas opções:

• Reescrever o codigo usando loops.
• Utilizar tail recursion (recursao de cauda) - topico mais avancado que nao é suportada em todas as linguagens de programacao.

Resumo:

• Recursão é quando uma função chama a si mesma;
• Toda função recursiva tem dois casos: o caso-base e o caso recursivo;
• Uma pilha tem duas operações: push e pop;
• Todas as chamadas de função vão para a pilha de chamada
• A pilha de chamada pode ficar muito grande e ocupar muita memória.

Quicksort - Capítulo 4#

O algoritmo de quicksort é um algoritmo de ordenação que utiliza uma técnica chamada “Dividir para conquistar” - isso significa que dividimos o problema em partes menores usando recursão. Ele é muito utilizado e é mais rápido que a ordenação por seleção.

Para resolver um problema usando DC (dividir para conquistar), devemos seguir dois passos:

1. Descobrir o caso-base, que deve ser o caso mais simples possível;
2. Dividir ou diminuir o problema até que ele se torne o caso-base.

• O array mais simples que um algoritmo de ordenação pode ordenar é um array vazio ou um array com apenas 1 elemento, pois não há necessidade de ordená-los. Sendo assim, eles são o caso-base.

Merge sort versus quicksort#

Hash#

Pode ser feita uma tabela hash ao combinar uma função hash com um array. Colisões são problemas, é necessário haver uma função hash que minimize colisões. Sao extremamente rápidas para pesquisar, inserir e remover itens. Se seu fator de carga for maior que 0,7 será necessário redimensionar a hash. são utilizadas como cache de dados, como no caso do Facebook.

Desempenho#

Tempo constante#

Tempo de execução O(1). Refere-se a um tempo que continuará sempre o mesmo, independentemente de quão grande a tabela hash possa ficar. Ou seja, não importa se a tabela hash tem 1 ou 1 milhão de elementos, o tempo de execução será o mesmo.

Pesquisa em largura - Capítulo 6#

A pesquisa em largura é um tipo de algoritmo que utiliza grafos, permitindo encontrar o menor caminho entre dois objetos. Pode ser usada para:

• escrever um algoritmo de Inteligencia Artificial que calcula o menor numero de movimentos necessários para a vitória em uma partida de damas. Os grafos são uma maneira de modelar como eventos diferentes estão conectados entre si. Ajuda a responder 2 tipos de perguntas:

1. Existe algum caminho do vértice A até o vértice B?
2. Qual o caminho mínimo do vértice A até o vértice B?

Se houver um problema do tipo “encontre o menor X”, tente modelar o seu problema utilizando grafos e use a pesquisa em largura para resolvê-lo.

– Cada vez que você verificar alguém, procure não verificá-lo novamente, isso pode acabar em loop infinito.

Filas#

Estrutura de dados FIFO (First In First Out) push = enqueue pop = dequeue

Algoritmo de Dijkstra - Capítulo 7#

Diferente da pesquisa em largura, que retorna o melhor caminho, com menos segmentos, o Algoritmo de Djikstra atribui um peso a cada segmento. Logo, o algoritmo encontra o caminho com o menor peso total.

Nela, cada aresta tem um peso e um grafo com pesos é chamado de grafo ponderado (ou grafo valorado). Um grafo sem pesos é chamado de grafo não ponderado (ou grafo não valorado).

Você não pode usar o algoritmo de Dijkstra se tiver arestas com pesos negativos.

Algoritmos gulosos - Capítulo 8#

Trata-se de um algoritmo simples! A cada etapa, escolhe-se a solução ideal, e no fim você tem uma solução global ideal.

• Algoritmos gulosos otimizam localmente na esperança de acabar em uma otimização global
• problemas NP-completo não tem uma solução rápida
• se você estiver tentando resolver um problema NP-completo, o melhor a fazer é usar um algoritmo de aproximação.
• algoritmos gulosos são fáceis de escrever e tem tempo de execução baixo, portanto eles são bons algoritmos de aproximação.

Programação Dinâmica - Capítulo 9#

Técnica de resolução de problemas complexos que se baseia na divisão de um problema em subproblemas, os quais são resolvidos separadamente.

• útil quando voce tenta otimizar algo em relação a um limite.
• Voce pode usar a programacao dinamica quando o problema puder ser dividido em subproblemas discretos.
• Todas as solucoes em programacao dinamica envolvem uma tabela.

K-vizinhos mais próximos - Capítulo 10#

ë utilizado na classificacao e tambem na regressao. Ele envolve observar os K-vizinhos mais próximos. Classificacao = classificar em grupos Regressao = adivinhar uma resposta (como um número) Extrair caracteristicas significa converter um item como uma fruta o uusuario, em uma lista de numeros que podem ser comparados. escolher boas caracteristicas é uma parte importante para que um algoritmo dos k-vizinhos mais proximos opere corretamente.

algoritmo DIFIIE-Hellman#

Programacao Linear