Home Page of Luis Caires

Lecture Notes para apoio à UC de Fundamentos de Programação (LEFT) [download]
Pasta Google Drive com Sample Code [open]

  • M1 – Computação, Computadores, Programação, Introdução à linguagem Python.
  • M2 – Como abordar um problema de programação. Estruturas básicas da programação imperativa.
  • M3 – Estruturas básicas da programação imperativa em Python: Comandos básicos, expressões, afetações. Comando alternativo (if then else else if); Ciclos (while, for). I/O básico no terminal (input / print).
  • M4 – Condicionais e Ciclos, combinação de ciclos e condicionais, acumulação de informação durante o ciclo, limitada e ilimitada.
  • M5 – Estruturação de programas e sua importância; funções; parâmetros; variáveis Locais; excepções (introdução); declarações de tipos (introdução).
  • M6 – Modularização de programas em funções (1); Manipulação de Pontos e Rectângulos; Representações de dados usando tipos estruturados; Tuplos; Dataclasses; Anotações de Tipos e verificação usando a extensão MyPy.
  • M7 – Processamento de strings; Algoritmos simples de processamento de texto; Slicing de strings e sequências
  • M8 – Modularização de programas em funções (2): Desenvolvimento de App Phone Book. Listas e Dicionários com Dataclasses; Variáveis Locais e Globais; I/O básico para ficheiro.
  • M9 – Modularização de programas em funções (3): Simulação de movimento de foguetão espacial usando modelo físico detalhado: Cálculo Numérico; aproximação computacional de sistema dinâmico através de diferenças finitas; Deteção de extremos (máximos e ou mínimos); Visualização gráfica usando PyGame.
  • M10 -Modularização de programas em funções (4); Máquina de Estado (Conceitos fundamentais); Máquina de Estado Universal.
  • M11 – Grafos: representação de grafo usando dicionário e listas. Algoritmos de Grafos. Deteção de ciclos. Algoritmo de Pesquisa em Largura num Grafo (BFS).
  • M12 – Modularização de programas por decomposição funcional top-down (1). Ordenação usando a função sort de Python; I/O; Ficheiros de texto; Processamento de Texto; Cross-reference e Multiplicidade de Palavras;
  • M13 – Modularização de programas por decomposição funcional top-down (2). Geração de números (pseudo-aleatórios), biblioteca Python random. Anotações de Tipo. I/O Ficheiros de texto. Caso de Estudo: Modelo de Linguagem NanoLM usando uma cadeia de markov e bigramas.
  • M14 – Modelo de Memória da linguagem Python; Memória; Objectos; Referências; Modos de cópia shallow copy / deep copy; Visualização de estruturas de dados ligadas
  • M15 – Algoritmos de Inserção e Pesquisa em arrays (memória de acesso sequencial / linear): inserção linear em posição indicada : O(n); inserção linear no fim: O(1) em geral; pesquisa linear: O(n): pesquisa ordenada: O(n): inserção ordenada: O(n). Introdução à complexidade e notação Big O.
  • M16 – Algoritmos de Ordenação: insertion sort, selection sort. Análise simplificada de complexidade temporal: O(n) e O(n2). Complexidade de operações associadas aos tipos nativos de Python
  • M17 – Pesquisa Binária. Algoritmos recursivos de divisção e conquista. Análise simplificada de complexidade temporal: O(log n). Análise Empírica da eficiência O(log n).
  • M18 – Algoritmos de Ordenação: heap sort. Análise simplificada de complexidade temporal: O(nlog n). Modelação de fila com proridade usando um heap.
  • M19 – Algoritmos de Grafos. Noção de Grafo. Problema do Caminho mais curto num grafo pesado. Algoritmo de Dijkstra. Análise de Complexidade do Algpritmo de Dijkstra, solução O(n2) e solução O(nlog n) usando fila com prioridades em heap.
  • M20 – Recursão. Programação funções definidos recursivamente. Exemplos: factorial, máximo divisor comum, combinações binomiais. Use de memorização.
  • M21 – Definição de estruturas de dados recursivas. Árvores Binárias de Pesquisa: inserção; pesquisa; remoção; percurso em-ordem.
  • M22 – Algoritmos recursivos de ordenação. TreeSort. QuickSort. Análise Simplificada de Complexidade.
  • M23 – Programação Funcional em Python. Princípios de Programação sem estado mutável. Combinadores. Funções lambda. Parâmetros Funcionais. Funções de Ordem Superior. Map e Reduce. Compreensão de listas. Geradores.
  • M24 – Programação com Objectos em Python. Objectos e Classes. Variáveis de instância e métodos. Tipos Abstratos de Dados e Encapsulamento. Estruturação de Programas em classes. Programando uma classe Fila de Espera usando objectos. Reprogramando a app Phone Book (M8) em estilo OO.