AED 2004/2005 - Revision history

Root at 14:47, 6 April 2015

2015-04-06T14:47:13Z

← Older revision		Revision as of 14:47, 6 April 2015
Line 108:		Line 108:

	[[category:AED]]		[[category:AED]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root: /* Aula 25: Introdução Ã Análise de Algoritmos */

2008-11-12T09:53:59Z

Aula 25: Introdução Ã Análise de Algoritmos

← Older revision		Revision as of 09:53, 12 November 2008
Line 66:		Line 66:
	(na aula 21 foram feitas revisões para o primeiro teste)		(na aula 21 foram feitas revisões para o primeiro teste)

	== Aula 25: Introdução Ã Análise de Algoritmos ==		== Aula 25: 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. 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.

	== Aula 26: Tipos de Dados Abstractos (ADTs) ==		== Aula 26: Tipos de Dados Abstractos (ADTs) ==

Root at 09:53, 12 November 2008

2008-11-12T09:53:33Z

Root at 09:51, 12 November 2008

2008-11-12T09:51:20Z

← Older revision	Revision as of 09:51, 12 November 2008
(No difference)

Root at 09:51, 12 November 2008

2008-11-12T09:51:03Z

Root at 15:12, 16 March 2008

2008-03-16T15:12:29Z

← Older revision		Revision as of 15:12, 16 March 2008
Line 109:		Line 109:
	[[category:AED]]		[[category:AED]]
	[[category:Teaching]]		[[category:Teaching]]
	~~[[category:IST]]~~

Root at 21:15, 25 July 2007

2007-07-25T21:15:52Z

← Older revision		Revision as of 21:15, 25 July 2007
Line 108:		Line 108:

	[[category:AED]]		[[category:AED]]
	[[category:~~Aulas~~]]		[[category:Teaching]]
			[[category:IST]]

Root at 17:12, 16 July 2007

2007-07-16T17:12:24Z

← Older revision		Revision as of 17:12, 16 July 2007
Line 1:		Line 1:
	{{TOCright}}== Aulas 1 a 3: Apresentação; Introdução ao C ==		{{TOCright}}
			== Aulas 1 a 3: Apresentação; Introdução ao C ==

	Apresentação da disciplina. Apresentação do programa e do método de avaliação.		Apresentação da disciplina. Apresentação do programa e do método de avaliação.

Root at 17:12, 16 July 2007

2007-07-16T17:12:16Z

← Older revision		Revision as of 17:12, 16 July 2007
Line 1:		Line 1:
	== Aulas 1 a 3: Apresentação; Introdução ao C ==		{{TOCright}}== Aulas 1 a 3: Apresentação; Introdução ao C ==

	Apresentação da disciplina. Apresentação do programa e do método de avaliação.		Apresentação da disciplina. Apresentação do programa e do método de avaliação.

Root at 06:37, 28 September 2005

2005-09-28T06:37:29Z

← Older revision		Revision as of 06:37, 28 September 2005
Line 105:		Line 105:

	Uso de cutoff: insert sort para vectores pequenos. Discussão.		Uso de cutoff: insert sort para vectores pequenos. Discussão.

			[[category:AED]]
			[[category:Aulas]]

← Older revision		Revision as of 09:53, 12 November 2008
Line 54:		Line 54:
	== Aulas 19 a 24: Estruturas de Dados Elementares ==		== Aulas 19 a 24: 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: 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.

	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: 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.
Line 74:		Line 74:
	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: [[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.

	== Aula 27: ADTs de ~~1Âª~~ ordem ==		== Aula 27: ADTs de 1ª ordem ==

	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]] com base em amontoado. [[ADTs de 1ª ordem: Fila de Prioridade#Algoritmo de Ordenação\|Ordenação com base em fila de prioridade]].

	== Aulas 28 a 32 ~~Ãrvores~~ Binárias ==		== Aulas 28 a 32 Á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: 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".

	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.

	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 e árvores red-black. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo.

	== Aulas 33 a 34 Algoritmos de Ordenação ==		== Aulas 33 a 34 Algoritmos de Ordenação ==

← Older revision		Revision as of 09:51, 12 November 2008
Line 12:		Line 12:
	== Aulas 4 a 6: Controlo de Fluxo; Funções; Programas ==		== Aulas 4 a 6: Controlo de Fluxo; Funções; Programas ==

	Revisões sobre tipos básicos e matéria associada. Revisões sobre operadores. 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.		Revisões sobre tipos básicos e matéria associada. Revisões sobre operadores. 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.

	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: 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]].
Line 24:		Line 24:
	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.

	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.		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 [[Gestão de Memória (exemplo com pilha)\|exemplo prático de gestão de memória]]. [[Pilha de Strings (controlo de falha)\|Pilha de strings]].		Apresentação e discussão de [[Gestão de Memória (exemplo com pilha)\|exemplo prático de gestão de memória]]. [[Pilha de Strings (controlo de falha)\|Pilha de strings]].
Line 38:		Line 38:
	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 <tt>assert</tt>.		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 <tt>assert</tt>.

	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.		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.

	== Aula 16: Argumentos Variáveis; Bibliotecas ==		== Aula 16: Argumentos Variáveis; Bibliotecas ==
Line 56:		Line 56:
	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: 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.

	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: 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).

	(na aula 21 foram feitas revisões para o primeiro teste)		(na aula 21 foram feitas revisões para o primeiro teste)
Line 68:		Line 68:
	== Aula 25: Introdução Ã Análise de Algoritmos ==		== Aula 25: 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. 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.

	== Aula 26: Tipos de Dados Abstractos (ADTs) ==		== Aula 26: Tipos de Dados Abstractos (ADTs) ==
Line 82:		Line 82:
	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: 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".

	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.

	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 e árvores red-black. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo.

	== Aulas 33 a 34 Algoritmos de Ordenação ==		== Aulas 33 a 34 Algoritmos de Ordenação ==
Line 93:		Line 93:

	=== Algoritmos elementares ===		=== Algoritmos elementares ===
	Algoritmos apresentados (para vectores): 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 (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 apresentados (para vectores): 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 (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~~.		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.

	=== 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 e do heapsort.		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 e do heapsort.

	Ordenação por fusão: mergesort. 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. 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.		Uso de cutoff: insert sort para vectores pequenos. Discussão.