Algoritmos e Estruturas de Dados - Revision history

Root: /* Algoritmos elementares */

2016-10-09T22:15:05Z

Algoritmos elementares

← Older revision		Revision as of 22:15, 9 October 2016
Line 92:		Line 92:

	=== Algoritmos elementares ===		=== 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 (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 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 ===

Root: /* Introdução ao C; Controlo de Fluxo; Funções; Programas */

2016-10-09T22:00:29Z

Introdução ao C; Controlo de Fluxo; Funções; Programas

← Older revision		Revision as of 22:00, 9 October 2016
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.

Root: /* Introdução ao C; Controlo de Fluxo; Funções; Programas */

2016-10-09T21:59:42Z

Introdução ao C; Controlo de Fluxo; Funções; Programas

← Older revision		Revision as of 21:59, 9 October 2016
Line 17:		Line 17:
	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 ===

Root: /* Linguagem C */

2016-10-09T21:57:10Z

Linguagem C

← Older revision		Revision as of 21:57, 9 October 2016
Line 25:		Line 25:
	=== 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.

Root: /* Argumentos Variáveis; Bibliotecas */

2016-10-09T21:55:46Z

Argumentos Variáveis; Bibliotecas

← Older revision		Revision as of 21:55, 9 October 2016
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 ===

Root: /* Problemas Comuns em C; Aspectos de Desempenho */

2016-10-09T21:54:13Z

Problemas Comuns em C; Aspectos de Desempenho

← Older revision		Revision as of 21:54, 9 October 2016
Line 51:		Line 51:
	=== Problemas Comuns em C; Aspectos de Desempenho ===		=== Problemas Comuns em C; Aspectos de Desempenho ===

	~~Problemas comuns na~~ programação em C. Apresentação e discussão de exemplos.		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.

Root: /* Estruturas de Dados Elementares */

2016-10-09T21:51:58Z

Estruturas de Dados Elementares

← Older revision		Revision as of 21:51, 9 October 2016
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.

Root: /* Estruturas de Dados Elementares */

2016-10-09T21:50:09Z

Estruturas de Dados Elementares

← Older revision		Revision as of 21:50, 9 October 2016
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).

Root: /* Introdução à Análise de Algoritmos */

2016-10-09T21:48:52Z

Introdução à Análise de Algoritmos

← Older revision		Revision as of 21:48, 9 October 2016
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) ==

Root: /* Tipos de Dados Abstractos (ADTs) */

2016-10-09T21:47:53Z

Tipos de Dados Abstractos (ADTs)

← Older revision		Revision as of 21:47, 9 October 2016
Line 75:		Line 75:
	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 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 ==