Algoritmos e Estruturas de Dados: Difference between revisions
From Wiki**3
(16 intermediate revisions by the same user not shown) | |||
Line 13: | Line 13: | ||
=== Introdução ao C; Controlo de Fluxo; Funções; Programas === | === Introdução ao C; Controlo de Fluxo; Funções; Programas === | ||
Instrodução ao ANSI C. Exemplo de programa: hello world. Tipos básicos e aspectos relacionados. Declarações de constantes e variáveis. | Instrodução ao ANSI C. Exemplo de programa: hello world. Tipos básicos e aspectos relacionados '''[KR:2]'''. Declarações de constantes e variáveis. | ||
Literais em C. Caracteres e cadeias de caracteres: organização em memória. Operadores aritméticos, lógicos e relacionais. Operadores de atribuição. Exemplos. Discussão de problemas. | Literais em C. Caracteres e cadeias de caracteres: organização em memória. Operadores aritméticos, lógicos e relacionais. Operadores de atribuição. Exemplos. Discussão de problemas. | ||
Operador condicional. Ordem de execução. Conversão de tipos implícita e explícita. Discussão de aspectos associados. Controlo de fluxo em programas: instruções e blocos. if e if/else. | Operador condicional. Ordem de execução. Conversão de tipos implícita e explícita. Discussão de aspectos associados. Controlo de fluxo em programas '''[KR:3]''': instruções e blocos. if e if/else. | ||
Controlo de execução em C: ciclos while, for, do/while. Exemplos. Comparação entre ciclos while e ciclos for. Interrupção do desenrolar normal de um ciclo: break e continue. Análise de comportamento nos diferentes ciclos. Funções em C: estrutura geral de uma função. Argumentos e retorno. Exemplos simples: função pop para uma [[Pilha de Inteiros (versão simples)|pilha de inteiros]]. | Controlo de execução em C '''[KR:3]''': ciclos while, for, do/while. Exemplos. Comparação entre ciclos while e ciclos for. Interrupção do desenrolar normal de um ciclo: break e continue. Análise de comportamento nos diferentes ciclos. Funções em C: estrutura geral de uma função. Argumentos e retorno. Exemplos simples: função pop para uma [[Pilha de Inteiros (versão simples)|pilha de inteiros]]. | ||
Funções e módulos. Compilação separada. Utilização do pré-processador de C. Visibilidade de variáveis e funções. O uso de static. Exemplos de funções e módulos. Exemplos de funções simples: [[Leitura de Caracteres (programa em C)|leitura interactiva de caracteres]]. Aplicação de switch. | Funções e módulos '''[KR:4]'''. Compilação separada. Utilização do pré-processador de C. Visibilidade de variáveis e funções. O uso de static. Exemplos de funções e módulos. Exemplos de funções simples: [[Leitura de Caracteres (programa em C)|leitura interactiva de caracteres]]. Aplicação de switch. | ||
=== Ponteiros e Gestão de Memória === | === Ponteiros e Gestão de Memória === | ||
Introdução ao uso de ponteiros em C: ponteiros e endereços; ponteiros e vectores/tabelas. Notação (introdução ao uso dos operadores * e &). [[Strings vs. Vectores de Caracteres|Vectores de caracteres]]. Organização da memória. Apresentação e discussão de exemplos. | Introdução ao uso de ponteiros em C '''[KR:5]''': ponteiros e endereços; ponteiros e vectores/tabelas. Notação (introdução ao uso dos operadores * e &). [[Strings vs. Vectores de Caracteres|Vectores de caracteres]]. Organização da memória. Apresentação e discussão de exemplos. | ||
Ponteiros e vectores: semelhanças e diferenças. Aritmética de ponteiros. Conversão de ponteiros. Passagem de ponteiros e vectores como argumentos de funções. Apresentação e discussão de exemplos. | Ponteiros e vectores: semelhanças e diferenças. Aritmética de ponteiros. Conversão de ponteiros. Passagem de ponteiros e vectores como argumentos de funções. Apresentação e discussão de exemplos. | ||
Line 37: | Line 37: | ||
=== Estruturas em C === | === Estruturas em C === | ||
Tipos estruturados em C. Acesso a campos de estruturas. Ponteiros para estruturas; sintaxes de acesso alternativas. Estruturas e vectores. Apresentação e discussão de exemplos. | Tipos estruturados em C '''[KR:6]'''. Acesso a campos de estruturas. Ponteiros para estruturas; sintaxes de acesso alternativas. Estruturas e vectores. Apresentação e discussão de exemplos. | ||
Estruturas auto-referenciadas. Apresentação e discussão de exemplos: [[Pilha (dimensão variável)|pilha de dimensão arbitrária]] ([[Gestão de Memória (pilha elástica)|exemplo de cliente]]). Revisões sobre ponteiros para funções. Definição de tipos utilizando typedef. | Estruturas auto-referenciadas. Apresentação e discussão de exemplos: [[Pilha (dimensão variável)|pilha de dimensão arbitrária]] ([[Gestão de Memória (pilha elástica)|exemplo de cliente]]). Revisões sobre ponteiros para funções. Definição de tipos utilizando typedef. | ||
Line 47: | Line 47: | ||
=== Argumentos Variáveis; Bibliotecas === | === Argumentos Variáveis; Bibliotecas === | ||
Argumentos variáveis: stdarg. Apresentação de [[Exemplo de stdargs: miniprintf|exemplo]] e discussão das condições de utilização. Bibliotecas em C. [[Funções da Biblioteca Padrão (ficheiros)|Funções para manipulação de ficheiros]]. | Argumentos variáveis: stdarg. Apresentação de [[Exemplo de stdargs: miniprintf|exemplo]] e discussão das condições de utilização. Bibliotecas em C. [[Funções da Biblioteca Padrão (ficheiros)|Funções para manipulação de ficheiros]] '''[KR:7]'''. Interface de sistema '''[KR:8]'''. | ||
=== Problemas Comuns em C; Aspectos de Desempenho === | === Problemas Comuns em C; Aspectos de Desempenho === | ||
Aspectos problemáticos da programação em C (exemplos de "C Traps and Pitfalls"): problemas lexicais, sintácticos e semânticos. Operadores e ordem de execução. Caracteres e cadeias de caracteres. Declarações.. Apresentação e discussão de exemplos. | |||
Aspectos de desempenho de programas em C: apresentação de programa ilustrativo dos problemas que afectam o desempenho. Apresentação e discussão de algumas alternativas de solução. | Aspectos de desempenho de programas em C: apresentação de programa ilustrativo dos problemas que afectam o desempenho. Apresentação e discussão de algumas alternativas de solução. | ||
Line 57: | Line 57: | ||
== Estruturas de Dados Elementares == | == Estruturas de Dados Elementares == | ||
Introdução às estruturas de dados. Estruturas de dados elementares: vectores, listas ([[Listas Simplesmente Ligadas|simplesmente]] e [[Listas Duplamente Ligadas (inteiros)|duplamente]] ligadas). Uso de sentinelas. Apresentação e discussão de exemplos. | Introdução às estruturas de dados. Estruturas de dados elementares '''[S:3]''': vectores, listas ([[Listas Simplesmente Ligadas|simplesmente]] e [[Listas Duplamente Ligadas (inteiros)|duplamente]] ligadas). Uso de sentinelas. Apresentação e discussão de exemplos. | ||
Vectores e listas. Algoritmos e dependência da estrutura de dados. Apresentação de ordenação por inserção (isort) com vector e lista ligada sem sentinela. Discussão de aspectos relacionados com as soluções. | Vectores e listas. Algoritmos e dependência da estrutura de dados. Apresentação de ordenação por inserção (isort) com vector e lista ligada sem sentinela. Discussão de aspectos relacionados com as soluções. | ||
Line 63: | Line 63: | ||
Discussão de aspectos relacionados com o uso de sentinelas numa versão de [[Ordenação por Inserção|ordenação por inserção]] (isort) numa lista ligada. Árvores binárias completas, equilibradas e completamente preenchidas: organização de elementos. [[Amontoados]]: propriedades e organização de dados. Algoritmos de [[Amontoados#Algoritmo fixUp|fixUp]] e [[Amontoados#Algoritmo fixDown|fixDown]]. Inserção e remoção de elementos em/de um amontoado. Discussão de aspectos de eficiência sem considerar implementações concretas. | Discussão de aspectos relacionados com o uso de sentinelas numa versão de [[Ordenação por Inserção|ordenação por inserção]] (isort) numa lista ligada. Árvores binárias completas, equilibradas e completamente preenchidas: organização de elementos. [[Amontoados]]: propriedades e organização de dados. Algoritmos de [[Amontoados#Algoritmo fixUp|fixUp]] e [[Amontoados#Algoritmo fixDown|fixDown]]. Inserção e remoção de elementos em/de um amontoado. Discussão de aspectos de eficiência sem considerar implementações concretas. | ||
Amontoados: estrutura de dados e representação em memória. Implementação com vector: algoritmos [[Amontoados#Algoritmo fixUp|fixUp]] e [[Amontoados#Algoritmo fixDown|fixDown]]. Algoritmo de ordenação de vectores com base em amontoados ([[Heapsort|heapsort]]). Discussão de aspectos de eficiência. | Amontoados '''[S:9]''': estrutura de dados e representação em memória. Implementação com vector: algoritmos [[Amontoados#Algoritmo fixUp|fixUp]] e [[Amontoados#Algoritmo fixDown|fixDown]]. Algoritmo de ordenação de vectores com base em amontoados ([[Heapsort|heapsort]]). Discussão de aspectos de eficiência. | ||
Filas de prioridades. Impacto da implementação na eficiência: implementação com amontoado e com vector. Discussão. Algoritmo de ordenação baseado em fila de prioridade (PQsort). Introdução aos tipos de dados abstractos (ADTs). | Filas de prioridades. Impacto da implementação na eficiência: implementação com amontoado e com vector. Discussão. Algoritmo de ordenação baseado em fila de prioridade (PQsort). Introdução aos tipos de dados abstractos (ADTs). | ||
Line 69: | Line 69: | ||
== Introdução à Análise de Algoritmos == | == Introdução à Análise de Algoritmos == | ||
Introdução à análise de algoritmos. Crescimento de funções. Notação assimptótica ("notação O"). [[Complexidade de Algoritmos (exemplos)|Comportamentos em várias situações]]: média, pior caso e melhor caso. Recorrências. Apresentação e discussão de exemplos. | Introdução à análise de algoritmos '''[S:2]''', '''[C:3,4]'''. Crescimento de funções. Notação assimptótica ("notação O"). [[Complexidade de Algoritmos (exemplos)|Comportamentos em várias situações]]: média, pior caso e melhor caso. Recorrências. Apresentação e discussão de exemplos. | ||
== Tipos de Dados Abstractos (ADTs) == | == Tipos de Dados Abstractos (ADTs) == | ||
Tipos de dados abstractos: [[Tipos de Dados Abstractos#Interface|interface]], [[Tipos de Dados Abstractos#Implementação|implementação]], [[Tipos de Dados Abstractos#Cliente|cliente]], item. Motivação para o uso de ADTs. Exemplos de ADTs: pilha; fila de prioridades; fila simples (FIFO) com base em vector e em lista ligada. Exemplos de clientes. | Tipos de dados abstractos '''[S:4]''': [[Tipos de Dados Abstractos#Interface|interface]], [[Tipos de Dados Abstractos#Implementação|implementação]], [[Tipos de Dados Abstractos#Cliente|cliente]], item. Motivação para o uso de ADTs. Exemplos de ADTs: pilha; fila de prioridades; fila simples (FIFO) com base em vector e em lista ligada. Exemplos de clientes. | ||
Tipos de dados de primeira ordem: motivação. Exemplo de tipo de dados de 1ª ordem: [[Tipos de Dados de 1ª Ordem: números complexos|números complexos]]. Reescrita como ADT de 1ª ordem. Justificação para o procedimento. Exemplos de ADTs de primeira ordem: [[ADTs de 1ª ordem: Fila|FIFO]]; [[ADTs de 1ª ordem: Fila de Prioridade|fila de prioridade]] com base em amontoado. [[ADTs de 1ª ordem: Fila de Prioridade#Algoritmo de Ordenação|Ordenação com base em fila de prioridade]]. | Tipos de dados de primeira ordem: motivação. Exemplo de tipo de dados de 1ª ordem: [[Tipos de Dados de 1ª Ordem: números complexos|números complexos]]. Reescrita como ADT de 1ª ordem. Justificação para o procedimento. Exemplos de ADTs de primeira ordem: [[ADTs de 1ª ordem: Fila|FIFO]]; [[ADTs de 1ª ordem: Fila de Prioridade|fila de prioridade]] '''[S:9]''' com base em amontoado. [[ADTs de 1ª ordem: Fila de Prioridade#Algoritmo de Ordenação|Ordenação com base em fila de prioridade]]. | ||
== Árvores Binárias == | == Árvores Binárias == | ||
Anatomia de uma árvore: nós internos e externos; nós vs. folhas. "Rooted trees" vs. "free trees". Árvores genéricas: exemplos. Introdução às árvores binárias: definição de árvore binária; [[Estruturas de suporte à implementação de BSTs|implementação]] vs. conceito. Estruturas de suporte à implementação de árvores binárias. [[Exemplos de Algoritmos Básicos com Árvores|Algoritmos básicos com árvores]]: contagem de nós e cálculo da altura de uma árvore. [[Travessias sobre BSTs|Travessias]] recursivas: "pre-order", "in-order", "post-order". | Anatomia de uma árvore '''[S:5]''': nós internos e externos; nós vs. folhas. "Rooted trees" vs. "free trees". Árvores genéricas: exemplos. Introdução às árvores binárias (BSTs): definição de árvore binária '''[S:12]''', '''[C:12]'''; [[Estruturas de suporte à implementação de BSTs|implementação]] vs. conceito. Estruturas de suporte à implementação de árvores binárias. [[Exemplos de Algoritmos Básicos com Árvores|Algoritmos básicos com árvores]]: contagem de nós e cálculo da altura de uma árvore. [[Travessias sobre BSTs|Travessias]] recursivas: "pre-order", "in-order", "post-order". | ||
Travessias: algoritmos não recursivos: "pre-order" e "level-order". Discussão: algoritmos recursivos vs. iterativos. Árvores binárias de procura (BSTs - binary search trees). Métodos de construção, de [[Procura numa BST|procura]] e de [[Inserção numa BST|inserção]]. [[Operações de Rotação sobre Árvores Binárias|Operações de rotação à esquerda e à direita]]. [[ADT para tabela de símbolos]]: [[Implementação do ADT Tabela de Símbolos (BST)|implementação baseada em BSTs]]. Apresentação e discussão de implementações dos algoritmos de inserção e procura. | Travessias: algoritmos não recursivos: "pre-order" e "level-order". Discussão: algoritmos recursivos vs. iterativos. Árvores binárias de procura (BSTs - binary search trees). Métodos de construção, de [[Procura numa BST|procura]] e de [[Inserção numa BST|inserção]]. [[Operações de Rotação sobre Árvores Binárias|Operações de rotação à esquerda e à direita]]. [[ADT para tabela de símbolos]]: [[Implementação do ADT Tabela de Símbolos (BST)|implementação baseada em BSTs]]. Apresentação e discussão de implementações dos algoritmos de inserção e procura. | ||
Line 85: | Line 85: | ||
Algoritmos sobre árvores binárias de procura (BSTs): [[Selecção da k-ésima Menor Chave (BST)|selecção da k-ésima menor chave]]; [[Partição pela k-ésima Menor Chave (BST)|partição pela k-ésima menor chave]]; [[Inserção numa BST#Inserção na Raiz|inserção na raiz]]; [[Junção de duas BSTs arbitrárias|junção de árvores]]; [[Remoção de Elementos de uma BST|remoção de um elemento]]. Discussão de aspectos de organização e eficiência; discussão de aspectos relacionados com os processos recursivos. | Algoritmos sobre árvores binárias de procura (BSTs): [[Selecção da k-ésima Menor Chave (BST)|selecção da k-ésima menor chave]]; [[Partição pela k-ésima Menor Chave (BST)|partição pela k-ésima menor chave]]; [[Inserção numa BST#Inserção na Raiz|inserção na raiz]]; [[Junção de duas BSTs arbitrárias|junção de árvores]]; [[Remoção de Elementos de uma BST|remoção de um elemento]]. Discussão de aspectos de organização e eficiência; discussão de aspectos relacionados com os processos recursivos. | ||
Árvores equilibradas. Problemas de eficiência das BSTs. Discussão de possíveis soluções: balanceamento explícito e recurso à aleatorização. Árvores 2-3-4 e árvores red-black. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo. | Árvores equilibradas. Problemas de eficiência das BSTs. Discussão de possíveis soluções: balanceamento explícito e recurso à aleatorização. Árvores 2-3-4 '''[S:13]''' e árvores red-black '''[C:13]'''. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo. | ||
== Algoritmos de Ordenação == | == Algoritmos de Ordenação == | ||
Line 92: | Line 92: | ||
=== Algoritmos elementares === | === Algoritmos elementares === | ||
Algoritmos | Algoritmos elementares '''[S:6]''': selection sort, bubble sort, [[Ordenação por Inserção|insert sort]]. Discussão de aspectos de eficiência. Exemplos. Shell sort. Noção de h-sortedness. Discussão da influência da sequência h na eficiência do algoritmo. Comparação do Shell sort com o insert sort simples. Apresentação e discussão de exemplos de aplicação. [[Avaliação Experimental (ordenação)#Algoritmos Elementares|Avaliação experimental dos algoritmos de ordenação elementar]]: insert sort, selection sort e bubble sort. [[Avaliação Experimental (ordenação)#Shell Sort|Avaliação experimental do algoritmo Shell sort]]. Estabilidade dos algoritmos. | ||
=== Algoritmos baseados em propriedades das chaves === | === Algoritmos baseados em propriedades das chaves === | ||
Ordenação por contagem: ''[[Counting Sort|counting sort]]''. Princípio de funcionamento; estabilidade. Apresentação de exemplo e discussão de aspectos de eficiência. '''[S:6]''', '''[C:8]''' | Ordenação por contagem: ''[[Counting Sort|counting sort]]''. Princípio de funcionamento; estabilidade. Apresentação de exemplo e discussão de aspectos de eficiência. '''[S:6]''', '''[C:8]''' | ||
=== Algoritmos eficientes === | === Algoritmos eficientes === | ||
Introdução aos algoritmos de ordenação eficientes: [[Heapsort|heapsort]] (revisões: princípio de funcionamento do algoritmo; aspectos de implementação; aspectos de eficiência); princípios básicos do funcionamento do [[Quicksort|quicksort]]. Função de partição: influência da escolha do pivot: discussão e exemplos de alternativas. [[Avaliação Experimental (ordenação)#Quicksort vs. Heapsort|Avaliação experimental comparativa]] do quicksort '''[S:7]''' e do heapsort '''[S:9]''' | Introdução aos algoritmos de ordenação eficientes: [[Heapsort|heapsort]] (revisões: princípio de funcionamento do algoritmo; aspectos de implementação; aspectos de eficiência); princípios básicos do funcionamento do [[Quicksort|quicksort]]. Função de partição: influência da escolha do pivot: discussão e exemplos de alternativas. [[Avaliação Experimental (ordenação)#Quicksort vs. Heapsort|Avaliação experimental comparativa]] do quicksort '''[S:7]''' e do heapsort '''[S:9]''' | ||
Ordenação por fusão: mergesort '''[S:8]''', '''[C:2]'''. Operação de fusão de vectores ordenados. Fusão abstracta in-place. Versões top-down e bottom-up do algoritmo mergesort. Requisitos para a estabilidade da ordenação. Apresentação de exemplos de aplicação. Discussão de aspectos de eficiência em espaço e tempo. Mergesort sem cópia. Avaliação experimental do mergesort. | Ordenação por fusão: mergesort '''[S:8]''', '''[C:2]'''. Operação de fusão de vectores ordenados. Fusão abstracta in-place. Versões top-down e bottom-up do algoritmo mergesort. Requisitos para a estabilidade da ordenação. Apresentação de exemplos de aplicação. Discussão de aspectos de eficiência em espaço e tempo. Mergesort sem cópia. Avaliação experimental do mergesort. | ||
Line 106: | Line 106: | ||
Uso de cutoff: insert sort para vectores pequenos. Discussão. | Uso de cutoff: insert sort para vectores pequenos. Discussão. | ||
Radix sort: conceitos básicos. Exemplos de motivação de aplicação do método de ordenação com base no dígito mais significativo (MSD) e no dígito menos significativo (LSD). '''[S:10]''', '''[C:8]'''. | Radix sort: conceitos básicos. Exemplos de motivação de aplicação do método de ordenação com base no dígito mais significativo (MSD) e no dígito menos significativo (LSD). '''[S:10]''', '''[C:8]''' | ||
== Hashing == | |||
Tabelas de dispersão. Funções de dispersão. Métodos de resolução de colisões. '''[S:14]''' | |||
[[category:AED]] | [[category:AED]] | ||
[[category:Ensino]] | [[category:Ensino]] |
Latest revision as of 22:15, 9 October 2016
Bibliografia
- [KR:#] The C Programming Language (Kernighan & Ritchie);
- [S:#] Algorithms in C, 3rd edition (Sedgewick); página do autor, código e erratas
- [C:#] Introduction to Algoritms - Second Edition (Cormen et al.).
Note-se que a bibliografia recomendada apenas inclui [KR:*] e [S:*].
Linguagem C
Introdução ao C; Controlo de Fluxo; Funções; Programas
Instrodução ao ANSI C. Exemplo de programa: hello world. Tipos básicos e aspectos relacionados [KR:2]. Declarações de constantes e variáveis.
Literais em C. Caracteres e cadeias de caracteres: organização em memória. Operadores aritméticos, lógicos e relacionais. Operadores de atribuição. Exemplos. Discussão de problemas.
Operador condicional. Ordem de execução. Conversão de tipos implícita e explícita. Discussão de aspectos associados. Controlo de fluxo em programas [KR:3]: instruções e blocos. if e if/else.
Controlo de execução em C [KR:3]: ciclos while, for, do/while. Exemplos. Comparação entre ciclos while e ciclos for. Interrupção do desenrolar normal de um ciclo: break e continue. Análise de comportamento nos diferentes ciclos. Funções em C: estrutura geral de uma função. Argumentos e retorno. Exemplos simples: função pop para uma pilha de inteiros.
Funções e módulos [KR:4]. Compilação separada. Utilização do pré-processador de C. Visibilidade de variáveis e funções. O uso de static. Exemplos de funções e módulos. Exemplos de funções simples: leitura interactiva de caracteres. Aplicação de switch.
Ponteiros e Gestão de Memória
Introdução ao uso de ponteiros em C [KR:5]: ponteiros e endereços; ponteiros e vectores/tabelas. Notação (introdução ao uso dos operadores * e &). Vectores de caracteres. Organização da memória. Apresentação e discussão de exemplos.
Ponteiros e vectores: semelhanças e diferenças. Aritmética de ponteiros. Conversão de ponteiros. Passagem de ponteiros e vectores como argumentos de funções. Apresentação e discussão de exemplos.
Matrizes em C. Acesso multidimensional. Diferenças entre matrizes, vectores e ponteiros: organização da memória. Passagem de argumentos por referência. Gestão de memória dinâmica utilizando malloc e free. Apresentação e discussão de exemplos.
Apresentação e discussão de exemplo prático de gestão de memória. Pilha de strings.
Ponteiros para funções. Apresentação e discussão de exemplo de utilização: algoritmo de procura binária parametrizado com comparador.
Estruturas em C
Tipos estruturados em C [KR:6]. Acesso a campos de estruturas. Ponteiros para estruturas; sintaxes de acesso alternativas. Estruturas e vectores. Apresentação e discussão de exemplos.
Estruturas auto-referenciadas. Apresentação e discussão de exemplos: pilha de dimensão arbitrária (exemplo de cliente). Revisões sobre ponteiros para funções. Definição de tipos utilizando typedef.
Apresentação de exemplo de utilização de estruturas em C. Lista duplamente ligada; funções de iteração parametrizadas; funções de inserção e remoção nos extremos: "push" e "pop". Considerações sobre alguns problemas da solução. O uso de assert.
Apresentação e discussão de exemplo de aplicação de estruturas em C: construção de uma tabela de símbolos com recurso a função de dispersão; ênfase nos aspectos de organização e gestão de memória, assim como na simplicidade relativa dos acessos aos dados.
Argumentos Variáveis; Bibliotecas
Argumentos variáveis: stdarg. Apresentação de exemplo e discussão das condições de utilização. Bibliotecas em C. Funções para manipulação de ficheiros [KR:7]. Interface de sistema [KR:8].
Problemas Comuns em C; Aspectos de Desempenho
Aspectos problemáticos da programação em C (exemplos de "C Traps and Pitfalls"): problemas lexicais, sintácticos e semânticos. Operadores e ordem de execução. Caracteres e cadeias de caracteres. Declarações.. Apresentação e discussão de exemplos.
Aspectos de desempenho de programas em C: apresentação de programa ilustrativo dos problemas que afectam o desempenho. Apresentação e discussão de algumas alternativas de solução.
Estruturas de Dados Elementares
Introdução às estruturas de dados. Estruturas de dados elementares [S:3]: vectores, listas (simplesmente e duplamente ligadas). Uso de sentinelas. Apresentação e discussão de exemplos.
Vectores e listas. Algoritmos e dependência da estrutura de dados. Apresentação de ordenação por inserção (isort) com vector e lista ligada sem sentinela. Discussão de aspectos relacionados com as soluções.
Discussão de aspectos relacionados com o uso de sentinelas numa versão de ordenação por inserção (isort) numa lista ligada. Árvores binárias completas, equilibradas e completamente preenchidas: organização de elementos. Amontoados: propriedades e organização de dados. Algoritmos de fixUp e fixDown. Inserção e remoção de elementos em/de um amontoado. Discussão de aspectos de eficiência sem considerar implementações concretas.
Amontoados [S:9]: estrutura de dados e representação em memória. Implementação com vector: algoritmos fixUp e fixDown. Algoritmo de ordenação de vectores com base em amontoados (heapsort). Discussão de aspectos de eficiência.
Filas de prioridades. Impacto da implementação na eficiência: implementação com amontoado e com vector. Discussão. Algoritmo de ordenação baseado em fila de prioridade (PQsort). Introdução aos tipos de dados abstractos (ADTs).
Introdução à Análise de Algoritmos
Introdução à análise de algoritmos [S:2], [C:3,4]. Crescimento de funções. Notação assimptótica ("notação O"). Comportamentos em várias situações: média, pior caso e melhor caso. Recorrências. Apresentação e discussão de exemplos.
Tipos de Dados Abstractos (ADTs)
Tipos de dados abstractos [S:4]: interface, implementação, cliente, item. Motivação para o uso de ADTs. Exemplos de ADTs: pilha; fila de prioridades; fila simples (FIFO) com base em vector e em lista ligada. Exemplos de clientes.
Tipos de dados de primeira ordem: motivação. Exemplo de tipo de dados de 1ª ordem: números complexos. Reescrita como ADT de 1ª ordem. Justificação para o procedimento. Exemplos de ADTs de primeira ordem: FIFO; fila de prioridade [S:9] com base em amontoado. Ordenação com base em fila de prioridade.
Árvores Binárias
Anatomia de uma árvore [S:5]: nós internos e externos; nós vs. folhas. "Rooted trees" vs. "free trees". Árvores genéricas: exemplos. Introdução às árvores binárias (BSTs): definição de árvore binária [S:12], [C:12]; implementação vs. conceito. Estruturas de suporte à implementação de árvores binárias. Algoritmos básicos com árvores: contagem de nós e cálculo da altura de uma árvore. Travessias recursivas: "pre-order", "in-order", "post-order".
Travessias: algoritmos não recursivos: "pre-order" e "level-order". Discussão: algoritmos recursivos vs. iterativos. Árvores binárias de procura (BSTs - binary search trees). Métodos de construção, de procura e de inserção. Operações de rotação à esquerda e à direita. ADT para tabela de símbolos: implementação baseada em BSTs. Apresentação e discussão de implementações dos algoritmos de inserção e procura.
Algoritmos sobre árvores binárias de procura (BSTs): selecção da k-ésima menor chave; partição pela k-ésima menor chave; inserção na raiz; junção de árvores; remoção de um elemento. Discussão de aspectos de organização e eficiência; discussão de aspectos relacionados com os processos recursivos.
Árvores equilibradas. Problemas de eficiência das BSTs. Discussão de possíveis soluções: balanceamento explícito e recurso à aleatorização. Árvores 2-3-4 [S:13] e árvores red-black [C:13]. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo.
Algoritmos de Ordenação
Noção de estabilidade.
Algoritmos elementares
Algoritmos elementares [S:6]: selection sort, bubble sort, insert sort. Discussão de aspectos de eficiência. Exemplos. Shell sort. Noção de h-sortedness. Discussão da influência da sequência h na eficiência do algoritmo. Comparação do Shell sort com o insert sort simples. Apresentação e discussão de exemplos de aplicação. Avaliação experimental dos algoritmos de ordenação elementar: insert sort, selection sort e bubble sort. Avaliação experimental do algoritmo Shell sort. Estabilidade dos algoritmos.
Algoritmos baseados em propriedades das chaves
Ordenação por contagem: counting sort. Princípio de funcionamento; estabilidade. Apresentação de exemplo e discussão de aspectos de eficiência. [S:6], [C:8]
Algoritmos eficientes
Introdução aos algoritmos de ordenação eficientes: heapsort (revisões: princípio de funcionamento do algoritmo; aspectos de implementação; aspectos de eficiência); princípios básicos do funcionamento do quicksort. Função de partição: influência da escolha do pivot: discussão e exemplos de alternativas. Avaliação experimental comparativa do quicksort [S:7] e do heapsort [S:9]
Ordenação por fusão: mergesort [S:8], [C:2]. Operação de fusão de vectores ordenados. Fusão abstracta in-place. Versões top-down e bottom-up do algoritmo mergesort. Requisitos para a estabilidade da ordenação. Apresentação de exemplos de aplicação. Discussão de aspectos de eficiência em espaço e tempo. Mergesort sem cópia. Avaliação experimental do mergesort.
Uso de cutoff: insert sort para vectores pequenos. Discussão.
Radix sort: conceitos básicos. Exemplos de motivação de aplicação do método de ordenação com base no dígito mais significativo (MSD) e no dígito menos significativo (LSD). [S:10], [C:8]
Hashing
Tabelas de dispersão. Funções de dispersão. Métodos de resolução de colisões. [S:14]