Skip to content

joaopauloaramuni/fundamentos-de-projeto-e-analise-de-algoritmos

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

414 Commits
ARTIGOS
ARTIGOS
 
 
CHEATSHEETS
CHEATSHEETS
 
 
EXEMPLOS
EXEMPLOS
 
 
EXERCICIOS
EXERCICIOS
 
 
LISTAS
LISTAS
 
 
PDF
PDF
 
 
PLANO DE ENSINO
PLANO DE ENSINO
 
 
PROJETOS
PROJETOS
 
 
TRABALHOS
TRABALHOS
 
 
img
img
 
 
vid
vid
 
 
README.md
README.md
 
 

Repository files navigation

pucminas

Repo Fundamentos de Projeto e Análise de Algoritmos

Disciplina do curso de Engenharia de Software da PUC Minas

  • 1°Sem 2025
  • 2°Sem 2025

Sumário:

Links úteis:

📚 Livros recomendados:
📐 Fundamentos de Projeto
🧠 Análise de Algoritmos
🐍 Algoritmos e Estruturas de Dados com Python
💼 Entrevistas Técnicas e Algoritmos
🔧 Recursos e ferramentas para Python:
🧰 IDE recomendada:
⬇️ Veja o passo a passo de como obter o GitHub Student Developer Pack
🎓 Como obter o PyCharm Professional gratuitamente com o GitHub Student Developer Pack

Ao se cadastrar no GitHub Student Developer Pack, você garante acesso gratuito à versão profissional das ferramentas da JetBrains, como o PyCharm Professional 🧠💻. Essa é uma excelente oportunidade para utilizar recursos avançados de desenvolvimento, como depuração visual, análise de código, suporte a frameworks e muito mais — tudo sem custo para estudantes! 🚀

✅ Passo a passo:

1️⃣ Adicione seu e-mail institucional da PUC Minas (terminado em @sga.pucminas.br) como e-mail secundário na sua conta do GitHub em https://github.com/settings/emails
2️⃣ Acesse a caixa de entrada do e-mail e clique no link de confirmação enviado pelo GitHub.
3️⃣ Ao acessar o GitHub Student Developer Pack, permita que o navegador compartilhe sua localização atual 🌍.
4️⃣ Selecione "PUC Minas" como sua instituição, envie um print da sua carteirinha digital do app PUC Mobile ou um comprovante de matrícula recente como forma de verificação. Depois, aguarde até 2 dias úteis para que o selo GitHub Pro 🏅 seja ativado na sua conta.
5️⃣ Acesse: https://www.jetbrains.com/shop/eform/students
 ➡ Vá até a aba GitHub e clique em "Authorize with GitHub" 🔑.
6️⃣ Instale o PyCharm e, ao abrir o programa, vá em "Ativar licença". Escolha a opção "Log in with GitHub", faça login com sua conta GitHub (que já possui o selo GitHub Pro 🏅 e que você autorizou previamente no site da JetBrains — passo 5), e a licença Professional será ativada automaticamente 🎉.

🏁 Pronto! Agora você pode aproveitar todos os benefícios do GitHub Pro 🏅, incluindo:

  • Acesso gratuito às ferramentas profissionais da JetBrains, como o PyCharm Professional 🧠💻
  • GitHub Copilot com sugestões inteligentes de código (com testes gratuitos por tempo limitado) 🤖
  • Repositórios privados ilimitados 🔒
  • Insights avançados de contribuições, métricas e estatísticas dos seus projetos 📊
  • Ferramentas de CI/CD integradas com GitHub Actions ⚙️
  • Integrações com dezenas de serviços e ferramentas educacionais 🧩

Esses recursos ajudam a elevar seu aprendizado, organizar seus projetos e turbinar sua produtividade como desenvolvedor 💼🚀

🔗 Confira todos os detalhes do plano GitHub Pro para estudantes aqui:

🐍 Python:
🐢 Python Tutor:
🖥️ Programiz:
Algorithm Visualizer:
📋 Cheat Sheets:
📈 Big-O Cheat Sheet:
🔢 Recursion Cheat Sheet:
📚 Sorting Algorithms Cheat Sheet:
  • Sound of Sorting - SoS - CheatSheet Um resumo visual dos principais algoritmos de ordenação, ilustrando seus passos, comparações e trocas de forma clara e didática, facilitando o entendimento do funcionamento interno de cada algoritmo.
  • Sorting Algorithms Cheat Sheet - Interview Cake
    Um resumo visual e prático dos principais algoritmos de ordenação, incluindo suas complexidades de tempo no melhor, médio e pior caso, além de características como estabilidade, memória usada e estratégias básicas.
🧩 Data Structures Cheat Sheet:
  • Data Structures Cheat Sheet - Tel Aviv University
    Resumo abrangente com estruturas como árvores, heaps, hashing, union-find, algoritmos de ordenação e seleção, além de conceitos fundamentais como ordens de crescimento e análise amortizada. Ideal para revisão rápida e aprofundamento teórico.
  • Data Structures Cheat Sheet - Rice University
    Tabela comparativa com as operações mais comuns em estruturas como Array, List, LinkedList, Stack, Queue e Dictionary. Inclui as complexidades de inserção, remoção, acesso e busca, ajudando a escolher a estrutura ideal para cada situação.
🎯 States-Based Models & MDP Cheat Sheet:
🔎 Graph Algorithms Cheat Sheet:
🛠️ Bibliotecas e Frameworks Python para análise e visualização de algoritmos
🚀 PyGMO:
🎮 PyGame:
🎨 PyAlgoViz:
  • PyAlgoViz
    Biblioteca focada em visualização animada de algoritmos, especialmente de ordenação e busca, para fins educacionais.
🌐 NetworkX:
⏱️ timeit (módulo Python padrão):
  • timeit - Documentação oficial
    Módulo para medir o tempo de execução de pequenos trechos de código, essencial para análise experimental de algoritmos.
🔍 cProfile / Profile (módulos Python padrão):
🗺️ Graphviz / PyGraphviz:
📖 Leituras fundamentais e clássicas

Esta lista reúne artigos clássicos e essenciais para compreender a análise de algoritmos, incluindo fundamentos teóricos, complexidade computacional, paradigmas de projeto, estruturas de dados e algoritmos randômicos.

📜 Artigos históricos e fundacionais

  1. Alan Turing – "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936)

    • Origem da máquina de Turing e da noção de computabilidade.
    • Trabalho seminal que fundamenta toda a teoria da computação.
    • PDF

  2. Alan Turing – "Computing Machinery and Intelligence" (1950)

    • Propõe o "Teste de Turing" e discute a possibilidade de máquinas pensarem.
    • Marco inicial na inteligência artificial.
    • PDF

  3. Stephen Cook – "The Complexity of Theorem-Proving Procedures" (1971)

    • Introduz o conceito de NP-completude, base da teoria da complexidade.
    • Fundamenta a distinção entre problemas eficientes e intratáveis.
    • PDF
📘 Clássicos da Análise de Algoritmos

  1. Edsger Dijkstra – "A Note on Two Problems in Connexion with Graphs" (1959)

    • Introduz o algoritmo de caminhos mínimos em grafos (algoritmo de Dijkstra).
    • Artigo clássico e fundamental para grafos e otimização.
    • PDF

  2. Robert Floyd – "Algorithm 97: Shortest Path" (1962)

    • Introduz o algoritmo de Floyd-Warshall para encontrar caminhos mínimos entre todos os pares de vértices.
    • PDF

  3. Anatolii Karatsuba & Yu. Ofman – "Multiplication of Multidigit Numbers on Automata" (1962)

    • Primeiro algoritmo de multiplicação de números grandes com complexidade subquadrática (Karatsuba).
    • PDF

  4. Richard Bellman – "Dynamic Programming" (1957)

    • Artigo fundacional do paradigma de programação dinâmica.

    • Também autor do livro Dynamic Programming (1972), que expande e consolida a teoria.

    • 7.1 Richard Bellman – "Dynamic Programming" (1957, RAND Paper P-392)

      • Artigo curto 10 páginas que introduz o paradigma de programação dinâmica.
      • Enfatiza a ideia de decompor problemas em subproblemas sobrepostos.
      • Publicado originalmente como um relatório técnico da RAND Corporation.
      • PDF

    • 7.2 Richard Bellman – Dynamic Programming (Livro, 1972 – Sixth Printing, Princeton University Press)

      • Versão expandida e consolidada da teoria com aplicações matemáticas, físicas e econômicas.
      • Contém 365 páginas na edição de 1972 (Sexta impressão).
      • Uma das obras mais citadas sobre o tema na literatura científica.
      • PDF
🧠 Complexidade e Classes de Problemas

  1. Richard Karp – "Reducibility Among Combinatorial Problems" (1972)

    • Lista os primeiros 21 problemas NP-completos, formalizando a teoria da NP-completude.
    • Artigo fundamental para o estudo da complexidade computacional e algoritmos.
    • PDF

  2. Leonid Levin – "Universal Sequential Search Problems" (1973)

    • Publicado originalmente em russo como "Universal’nye perebornye zadachi" na revista Problemy Peredachi Informatsii, vol. 9, nº 3.
    • Artigo independente, publicado quase simultaneamente ao de Stephen Cook, que introduz formalmente a noção de problemas de busca NP-completos.
    • Levin define seis problemas universais que capturam a dificuldade intrínseca dos problemas em NP.
    • Reconhecido como co-descobridor da teoria da NP-completude.
    • PDF

  3. Michael Sipser – Introduction to the Theory of Computation (Primeira edição: 1996; Terceira edição: 2012)

    • Livro didático referência para teoria da computação, complexidade computacional e automatos.
    • Aborda detalhadamente classes de problemas como P, NP, NP-completos e problemas indecidíveis.
    • Muito utilizado em cursos de graduação e pós-graduação como base teórica para análise de algoritmos e teoria da complexidade.
    • Livro na Amazon
🔁 Paradigmas de Projeto de Algoritmos

  1. Cormen, Leiserson, Rivest, Stein – Introduction to Algorithms (Primeira edição: 1990; Quarta edição: 2024)

    • Livro referência para design e análise de algoritmos, cobrindo uma ampla gama de tópicos e paradigmas.
    • Fundamental para estudantes de engenharia de software e ciência da computação.
    • Livro na Amazon

  2. Kenneth H. Rosen – Discrete Mathematics and Its Applications (8º edição: 2018)

    • Um dos livros mais utilizados em cursos de matemática discreta para ciência da computação e engenharia.
    • Abrange lógica, conjuntos, relações, grafos, combinatória e apresenta bons capítulos sobre algoritmos gulosos e programação dinâmica.
    • Livro na Amazon

  3. Donald Knuth – The Art of Computer Programming (Volumes publicados a partir de 1968)

    • Série clássica que compila algoritmos e análise formal detalhada.

    • Referência essencial para aprofundamento teórico e histórico.

    • 13.1 Livro – The Art of Computer Programming

      • Primeira edição publicada em 1968.
      • Volumes sucessivos abrangem análise de algoritmos, estruturas de dados, técnicas avançadas, e mais.
      • Boxed Set na Amazon

    • 13.2 Donald Knuth – Tese: Finite Semifields and Projective Planes (1963)

      • Tese de doutorado que contribui para matemática discreta e teoria dos planos projetivos.
      • PDF
🧮 Algoritmos Randômicos e Probabilísticos

  1. Michael Rabin – "Probabilistic Algorithm for Testing Primality" (1980)

    • Primeiro algoritmo probabilístico eficiente para teste de primalidade.
    • Abre caminho para a utilização de aleatoriedade na construção de algoritmos rápidos.
    • PDF

  2. Rajeev Motwani & Prabhakar Raghavan – Randomized Algorithms (Primeira edição: 1995)

    • Livro que compila diversos algoritmos randômicos com fundamentação teórica rigorosa.
    • Amplamente usado em cursos avançados de algoritmos.
    • Livro na Amazon
🧱 Estruturas de Dados fundamentais

  1. Robert Tarjan – "Efficiency of a Good But Not Linear Set Union Algorithm" (1975)

    • Introduz melhorias no algoritmo Union-Find, fundamentais para muitas aplicações em grafos.
    • Combina técnicas de path compression e union by rank para eficiência quase linear.
    • PDF

  2. Michael L. Fredman & Robert E. Tarjan – "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms" (1987)

    • Estrutura de dados avançada que melhora complexidade de operações em heaps.
    • Aplicações em algoritmos de otimização de redes e grafos.
    • PDF

  3. Jon Bentley – Programming Pearls (1986)

    • Série clássica sobre design e implementação prática de algoritmos.

    • 18.1 Livro – Programming Pearls (1986)

      • Coleção expandida de colunas originalmente publicadas na Communications of the ACM.
      • Explora problemas reais, otimização e clareza de código em situações do cotidiano.
      • Muito citado por engenheiros de software e usado em entrevistas técnicas.
      • Livro na Amazon

    • 18.2 Artigo – "Programming Pearls: Little Languages" (1986)

      • Um dos artigos originais da série, publicado na Communications of the ACM.
      • Foca em "linguagens pequenas" (little languages) como ferramentas poderosas para resolver problemas específicos.
      • Documento curto de 11 páginas, frequentemente citado como inspiração para soluções elegantes.
      • PDF
📚 Extras avançados

  1. Leslie Valiant – "A Theory of the Learnable" (1984)

    • Introduz o modelo PAC (Provably Approximately Correct) para aprendizagem computacional.
    • Importante conexão entre algoritmos, teoria da complexidade e inteligência artificial.
    • PDF

  2. Shafi Goldwasser & Silvio Micali – "Probabilistic Encryption" (1984)

    • Trabalho seminal na criptografia moderna, utilizando conceitos de complexidade computacional.
    • Define a segurança semântica e o uso de algoritmos probabilísticos para encriptação.
    • PDF
📖 Leituras, códigos e vídeos complementares:
🧠 Implementações de Algoritmos em Python:
  • 2012 até 2016 - prakhar1989 - Algorithms (GitHub)
    Coleção bem organizada de implementações em Python para algoritmos clássicos e estruturas de dados. Inclui exemplos práticos de grafos, ordenação, busca, programação dinâmica, divisão e conquista, estrutura de pilhas, filas, árvores, heaps e muito mais.
🧩 Sudoku:
🐴 Knight's tour Problem:
🧮 Subset Sum Problem:
👑 N Queens Problem:
🎒 Knapsack Problem:
🧳 Traveling Salesman Problem:
🌊 Flood Fill:
⭐ A* Algorithm:
🧮 Algorithm Complexity and Visualizations:
⏱️ Medição de tempo de execução em diversas linguagens:
🎵 Sound of Sorting - SoS:

🎥 Medição de tempos de execução para 1 bilhão de iterações em loops aninhados - 31 Linguagens:

BenjDicken-1863977678690541570.mp4

🎥 Medição de tempos de execução para o Fibonacci - 14 Linguagens:

BenjDicken-1861811963434770665.mp4

🎥 15 algoritmos de ordenação em 6 minutos: (Habilite o som)

15_Sorting_Algorithms_in_6_Minutes.mp4

📈 Visualizando a complexidade de algoritmos:

🔍 Algoritmos de busca:

min_complexity min_complexity
Cada algoritmo tenta encontrar o número 29 em um conjunto de 40 números ordenados do menor para o maior. Cada algoritmo tenta encontrar o número 83 em um conjunto de 100 números ordenados do menor para o maior.

🔢 Algoritmos de ordenação:

min_complexitysort
Merge Sort vs Bubble Sort

🐴 Caminho do cavalo (Knight's tour):

♟️ Tabuleiro 8x8:

Knights_Tour_8x8 Knights_Tour_8x8_2
O cavalo visita cada casa exatamente uma vez. Duas casas em uma direção (horizontal ou vertical) e uma casa em uma direção perpendicular. O problema do caminho do cavalo é um exemplo do problema do caminho hamiltoniano mais geral na teoria dos grafos.

♟️ Tabuleiro 5x5 e um exemplo de passeio em 8x8:

Knights_Tour_5x5 Knights_Tour_8x8_3
Como você começa em uma casa, você fará 24 movimentos [(n x n) - 1] em um tabuleiro 5×5. Um exemplo de passeio aberto de cavalo em um tabuleiro de xadrez 8x8.

👑 Problema das Oito Rainhas (Eight Queens Puzzle):

♟️ Tabuleiro 8x8:

Eight_Queens_Puzzle Eight_Queens_Puzzle_Min_Conflict
Backtracking para resolver o Problema das Oito Rainhas. Solução de conflitos mínimos para 8 rainhas.

🧳 Caixeiro Viajante (Travelling Salesman Problem):

Uma possível solução para o Problema do Caixeiro Viajante (Travelling Salesman Problem) usando um Algoritmo Evolutivo do PyGMO, um pacote Parallel Global Multiobjective Optimizer para Python:

Travelling_Salesman_Problem Travelling_Salesman
Travelling Salesman Problem with PyGMO Travelling Salesman

🌊 Preenchimento por inundação (Flood-Fill Algorithm):

Uma possível solução para visualizar o Flood Fill usando Python; e uma comparação de algoritmos Flood Fill com JavaScript:

Flood_Fill Flood_Fill_2
Com Python Com JavaScript

🧩 Sudoku com algoritmo de retrocesso (Sudoku Backtracking):

Um Sudoku Autosolver gamificado em Python com Interface Gráfica, Pygame e Algoritmo de Backtracking; e um Sudoku Solver com IA, Deep Learning e OpenCV:

⬇️ Abaixo, outras duas possíveis soluções do Geeks for Geeks com complexidades O(n*9^(n*n)) e O(9^(n*n)):

🛕 Torres de Hanói - com 4 discos:

hanoi_4
Tower of Hanoi with 4 disks
pucminas

About

Repo Fundamentos de Projeto e Análise de Algoritmos

Topics

complexity sorting-algorithms algorithm-analysis backtracking-algorithm complexity-analysis cyclomatic-complexity analysis-algorithms recursive-algorithms big-o-notation asymptotic-complexity

Resources

Readme
Activity

Stars

13 stars

Watchers

1 watching

Forks

1 fork
Report repository

Releases

No releases published

Packages

No packages published

Languages