14 de Setembro Exame disponível aqui.

25 de Fevereiro Notas do exame disponíveis nesta página.

4 de Fevereiro Resolução sucinta do teste disponível aqui .

3 de Fevereiro Notas do teste disponíveis nesta página.

20 de Janeiro Teste (13 de Janeiro) disponível aqui.

29 de Dezembro Sessões de dúvidas: uma primeira sessão terá lugar na 5a.fa. 8 de Janeiro, às 16:00 no anfiteatro DI-A2.

17 de Dezembro Encontra-se no piso -2 do DI uma folha para marcação das entregas dos trabalhos práticos da disciplina, que terão lugar nos dias 5, 6, e 7 de Janeiro.

12 de Novembro Disponibilizadas hoje duas colecções de exercícios de exame.

21 de Outubro Disponível o enunciado do mini-projecto. As questões sobre o mesmo que forem colocadas por email à equipa docente serão disponibilizadas numa FAQ.

20 de Outubro Actualizados os slides disponíveis nesta página (todo o primeiro capítulo disponível).

17 Setembro Tiveram hoje início as aulas teóricas. As aulas TP, e respectiva marcação de turnos, iniciar-se-ão na próxima semana.

Equipa Docente

• Jorge Sousa Pinto, T+TP. Atendimento: 4a.fa. 14h-17h
• Maria João Frade, TP. Atendimento: 5ª fa. 16h-19h
• José Barros, TP. Atendimento:

Material de Apoio

• Slides aulas teóricas, Cap. 1
• Slides aulas teóricas, Cap. 2
• Slides aulas teóricas, Cap. 3
• Exercícios (exames 2001-2004)
• Exames (2005-2008)
• Algoritmo de Prim (código C)

Programa

1. Estruturas de Dados para pesquisa: Árvores AVL, hashing
2. Introdução à Análise de Algoritmos: Invariantes de ciclo e análise de correcção; Análise assimptótica do tempo de execução; Recorrências; Análise Amortizada; Casos de estudo.
3. Estudo de Algoritmos sobre Grafos: Fundamentos; Pesquisa em largura e em profundidade; Árvores geradoras mínimas; Caminhos mais curtos; Fecho transitivo.
4. Problemas NP-completos: Problemas de decisão; Algoritmos não-determinísticos; Classes de problemas P e NP; Redução polinomial de problemas.

Sumários Aulas Teóricas

17/9/2008, 11:00-12:00

Apresentação do docente e da disciplina. Método de Avaliação. Programa e bibliografia recomendada.

19/9/2008, 14:00-15:00

Motivação para o estudo dos algoritmos. Conceito de correcção de um algoritmo. Noção de invariante de ciclo. Exemplos.

24/9/2008, 11:00-12:00

Continuação da aula anterior: exemplos de invariantes de programas. Introdução ao estudo da análise de tempo de execução dos algoritmos.

26/9/2008, 14:00-15:00

Exemplos de análise do tempo de execução de algoritmos com ciclos. Análise de melhor caso, pior caso, e caso médio. Introdução à notação assimptótica para a variação do tempo de execução com a dimensão do input.

1/10/2008, 11:00-12:00

Conclusão do estudo da notação assimptótica. Caso de estudo: algoritmo "insertion sort". Análise de correcção. Análise temporal de melhor caso.

3/10/2008, 14:00-15:00

Conclusão do estudo do algoritmo "insertion sort": análise de pior caso. Caso de estudo: algoritmo "merge sort". Análise da função de fusão de sequências ordenadas. Introdução ao estudo das equações de recorrência.

8/10/2008, 11:00-12:00

Resolução de recorrências. Método da substituição. Análise da árvore de recursão do algoritmo "merge sort". Prova pelo método da substituição do tempo de execução N lg N. Caso de estudo: algoritmo "quick sort". Estudo do tempo de execução da função de partição.

10/10/2008, 14:00-15:00

Conclusão do estudo do algoritmo "quick sort": análise de pior caso e melhor caso. Breve referência à análise de caso médio. Algoritmo "quick sort" com alietoriedade.

15/10/2008, 11:00-12:00

Algoritmos de ordenação com base em comparações. Análise por contagem de comparações. Árvores de decisão e traços de execução. Teorema do limite inferior para o tempo de execução no pior caso de um algoritmo de ordenação com base em comparações.

17/10/2008, 14:00-15:00

Algoritmos de ordenação de tempo linear. Algoritmo "counting sort". Análise do tempo de execução. Propriedade de estabilidade de um algoritmo de ordenação. Algoritmo de ordenação "radix sort".

22/10/2008, 11:00-12:00

Breve referência à necessidade de utilização de técnicas amortizadas para a análise do tempo de execução de sequências de operações sobre estruturas de dados. Análise agregada de sequências de operações. Exemplos: "stack" com operação "multipop"; sequência de operações de inserção de elementos em árvores binárias de pesquisa.

Introdução do segundo capítulo do programa: conceitos básicos sobre grafos e tipos de grafos.

24/10/2008, 14:00-15:00

Representação de grafos em computador: matrizes de adjacências e listas de adjacências. Discussão. Travessia / pesquisa de grafos. Algoritmo de travessia em largura.

29/10/2008, 11:00-12:00

Continuação do estudo do algoritmo de travessia de grafos em largura. Propriedades da árvore de travessia construída; Cálculo da distância entre dois nós. Análise do tempo de execução.

31/10/2008, 14:00-15:00

Algoritmo de travessia de grafos em profundidade (versão recursiva). "Timestamps". Propriedades da árvore de travessia em profundidade. Análise do tempo de execução.

5/11/2008, 11:00-12:00

Árvores geradoras mínimas de um grafo. Algoritmo de Prim para a construção de AGMs. Prova de correcção.

7/11/2008, 14:00-15:00

Análise do tempo de execução do algoritmo de Prim. Problemas de caminhos mais curtos num grafo. Introdução ao algoritmo de Dijkstra.

12/11/2008, 11:00-12:00

Estudo do algoritmo de Dijkstra. Variantes do problema de caminhos mais curtos: "single pair", "single source", "single destination", "all pairs". A estratégia algorítmica "greedy". Problemas com sub-estrutura óptima.

14/11/2008, 14:00-15:00

Fecho transitivo de um grafo. Algoritmo de Warshall. Adpatação para a resolução do problema "all pairs shortest paths".

19/11/2008, 11:00-12:00

Introdução ao estudo dos problemas NP-completos. Problemas de decisão e problemas de optimização. Exemplos de problemas "difíceis".

21/11/2008, 14:00-15:00

A classe de problemas "P". Noção de algoritmo não-determinístico. A classe de problemas "NP".

26/11/2008, 11:00-12:00

Discussão da questão P=?NP.

28/11/2008, 14:00-15:00

Redução polinomial de um problema a outro.

3/12/2008, 11:00-12:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

5/12/2008, 14:00-15:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

10/12/2008, 11:00-12:00

Definição de problema NP-completo. Restrições sobre problemas; problemas aparentemente semelhantes.

12/12/2008, 14:00-15:00

Os problemas NP-completos SAT e k-SAT. Redução de 3-SAT ao problema da existência de uma "clique" num grafo. Redução de problemas NP-completos: algoritmos aproximados.

Sumários Aulas Teórico-Práticas

TP2

25/9/2008, 14:00-16:00

Exercícios de revisão: programação com listas ligadas em C. Implementação de uma biblioteca de filas de espera.

2/10/2008, 14:00-16:00

Análise do tempo de execução das funções de pesquisa e inserção em árvores binárias de pesquisa. Análise de melhor e pior caso. Importância da profundidade de uma árvore. Motivação da utilização de árvores AVL.

9/10/2008, 14:00-16:00

Árvores AVL: desenvolvimento da função de inserção.

16/10/2008, 14:00-16:00

Árvores AVL: conclusão do desenvolvimento da função de inserção. Tabelas de "hash": introdução e princípios básicos. Resolução de colisões por "linear probing" (endereçamento aberto). Algoritmos de inserção, pesquisa, e remoção.

23/10/2008, 14:00-16:00

Tabelas de "hash" encadeadas: implementação das funções de inserção, remoção, pesquisa, e actualização. Discussão comparativa com a implementação por "linear probing".

30/10/2008, 14:00-16:00

Resolução de exercícios sobre análise de algoritmos iterativos: Avaliação de polinómios e pesquisa linear. Invariantes e análise do tempo de execução.

6/11/2008, 14:00-16:00

Resolução de exercícios sobre análise de algoritmos iterativos e recursivos: Algoritmos de ordenação incrementais ("bubble sort", "max sort", "insertion sort"). Análise do tempo de execução. Equações de recorrência e árvores de recursão.

13/11/2008, 14:00-16:00

Resolução de exercícios sobre "heaps". Implementação dinâmica.

20/11/2008, 14:00-16:00

Resolução de exercícios sobre "heaps". Implementação Estática.

27/11/2008, 14:00-16:00

Resolução de exercícios sobre grafos. Conversão de representações. Ordenações topológicas. Resolução do problema por travessias em profundidade e em largura.

4/12/2008, 14:00-16:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

11/12/2008, 14:00-16:00

Algoritmos "greedy": Implementação em C dos algoritmos de Prim e de Dijkstra.

TP3

25/9/2008, 16:00-18:00

Exercícios de revisão: programação com listas ligadas em C. Implementação de uma biblioteca de filas de espera.

2/10/2008, 16:00-18:00

Análise do tempo de execução das funções de pesquisa e inserção em árvores binárias de pesquisa. Análise de melhor e pior caso. Importância da profundidade de uma árvore. Motivação da utilização de árvores AVL.

9/10/2008, 16:00-18:00

Árvores AVL: desenvolvimento da função de inserção.

16/10/2008, 16:00-18:00

Árvores AVL: simulação de uma sequência de inserções. Tabelas de "hash": introdução e princípios básicos. Resolução de colisões por "linear probing" (endereçamento aberto). Algoritmos de inserção, pesquisa, e remoção.

23/10/2008, 16:00-18:00

Tabelas de "hash" encadeadas: implementação das funções de inserção, remoção, pesquisa, e actualização. Discussão comparativa com a implementação por "linear probing".

30/10/2008, 16:00-18:00

Resolução de exercícios sobre análise de algoritmos iterativos: Avaliação de polinómios e pesquisa linear. Invariantes e análise do tempo de execução.

6/11/2008, 16:00-18:00

Resolução de exercícios sobre análise de algoritmos iterativos e recursivos: Algoritmos de ordenação incrementais ("bubble sort", "max sort", "insertion sort"). Análise do tempo de execução. Equações de recorrência e árvores de recursão.

13/11/2008, 16:00-18:00

Resolução de exercícios sobre "heaps". Implementação dinâmica.

20/11/2008, 16:00-18:00

Resolução de exercícios sobre "heaps". Implementação estática.

27/11/2008, 16:00-18:00

Resolução de exercícios sobre grafos. Conversão de representações. Ordenações topológicas. Resolução do problema por travessias em profundidade e em largura.

4/12/2008, 16:00-18:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

11/12/2008, 16:00-18:00

Algoritmos "greedy": Implementação em C dos algoritmos de Prim e de Dijkstra.

50 Recent Changes in TWiki Web retrieved at 16:23 (GMT)

See also: RSS feed, recent changes with 50, 100, 200, 500, 1000 topics, all changes

Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on only two things: (1) the algorithms chosen and (2) the suitability and efficiency of the various layers of implementation. Good algorithm design is therefore crucial for the performance of al l software systems. Moreover, the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or any other implementation aspect. An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of well-defined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area.

in IEEECS-ACM Computing Curricula 2001

O objectivo principal da disciplina de Algoritmos e Complexidade é a introdução de técnicas para o desenho e análise de algoritmos. O ênfase é colocado nos algoritmos como objectos passíveis de serem analisados formalmente, mas também nos aspectos pragmáticos da sua execução. Esta abordagem requer pois dos alunos um trabalho quer ao nível teórico quer ao nível prático, laboratorial.

Education/AeC Web Preferences

The following settings are web preferences of the Education.AeC web. These preferences overwrite the site-level preferences in TWiki.TWikiPreferences and Main.TWikiPreferences, and can be overwritten by user preferences (your personal topic, eg: TWikiGuest in the Main web).

Web Preferences Settings

These settings override the defaults for this web only. See full list of defaults with explanation. Many of the settings below are commented out. Remove the # sign to enable a local customisation.

Natural Skin configuration

• Set SKIN=nat

• Set SKINSTYLE = Plain
• Set STYLEBORDER = thin
• Set STYLEBUTTONS = off
• Set STYLESIDEBAR = left
• Set STYLEVARIATION = none
• Set STYLESEARCHBOX = off

• Set PAGETITLE=Algoritmos e Complexidade

• Set NATWEBLOGO = Algoritmos e Complexidade

• Set WEBCOPYRIGHT = Copyright © by the contributing authors. Ideas, requests, problems? Send feedback.

• List of topics of the Education/AeC web:
  • #Set WEBTOPICLIST = Changes | Index | Search | Go

• Web-specific background color: (Pick a lighter one of the StandardColors).
  • Set WEBBGCOLOR = #D0D0D0
  • Note: This setting is automatically configured when you create a web

• Image, URL and alternate tooltip text of web's logo.
  Note: Don't add your own local logos to the TWikiLogos topic; create your own logos topic instead.

• Set WEBLOGOURL = WebHome
• Set #WEBLOGOIMG = http://wiki.di.uminho.pt/twiki/pub/Education/PeC/WebHome/petri.tiff
• Set WEBLOGOIMG =
• Set WEBLOGOALT = Algoritmos e Complexidade

• List this web in the SiteMap. If you want the web listed, then set SITEMAPLIST to on, do not set NOSEARCHALL, and add the "what" and "use to..." description for the site map. Use links that include the name of the web, i.e. Education/AeC.Topic links.
  Note: Unlike other variables, the setting of SITEMAPLIST is not inherited from parent webs. It has to be set in every web that is to be listed in the SiteMap
  
  • Set SITEMAPLIST = on
  • Set SITEMAPWHAT = Algoritmos e Complexidade
  • Set SITEMAPUSETO = Licenciatura em Engenharia Informática
  • Note: Above settings are automatically configured when you create a web

• Exclude web from a web="all" search: (Set to on for hidden webs).
  • Set NOSEARCHALL =
  • Note: This setting is automatically configured when you create a web

• Prevent automatic linking of WikiWords and acronyms (if set to on); link WikiWords (if empty); can be overwritten by web preferences:
  • #Set NOAUTOLINK =
  • Note: You can still use the [[...][...]] syntax to link topics if you disabled WikiWord linking. The <noautolink> ... </noautolink> syntax can be used to prevents links within a block of text.

• Default template for new topics for this web:
  • WebTopicEditTemplate? : Default template for new topics in this web. (Site-level is used if topic does not exist)
  • TWiki.WebTopicEditTemplate: Site-level default topic template

• Comma separated list of forms that can be attached to topics in this web. See TWikiForms for more information.
  • Set WEBFORMS =

• Users or groups who are not / are allowed to view / change / rename topics in the Education/AeC web: (See TWikiAccessControl). Remove the # to enable any of these settings. Remember that an empty setting is a valid setting; setting DENYWEBVIEW to nothing means that anyone can view the web.
  • #Set DENYWEBVIEW =
  • #Set ALLOWWEBVIEW =
  • #Set DENYWEBCHANGE =
  • Set ALLOWWEBCHANGE = JorgeSousaPinto
  • #Set DENYWEBRENAME =
  • Set ALLOWWEBRENAME = JorgeSousaPinto

• Users or groups allowed to change or rename this WebPreferences topic: (e.g., TWikiAdminGroup)
  • #Set ALLOWTOPICCHANGE = TWikiAdminGroup
  • Set ALLOWTOPICRENAME = TWikiAdminGroup

• Web preferences that are not allowed to be overridden by user or topic preferences:
  • Set FINALPREFERENCES = NOSEARCHALL, ATTACHFILESIZELIMIT, WIKIWEBMASTER, WEBCOPYRIGHT, WEBTOPICLIST, DENYWEBVIEW, ALLOWWEBVIEW, DENYWEBCHANGE, ALLOWWEBCHANGE, DENYWEBRENAME, ALLOWWEBRENAME

Help on Preferences

• A preference setting is defined by:
  3 or 6 spaces * Set NAME = value
  Example:
  • Set WEBBGCOLOR = #FFFFC0
• A preferences setting can be disabled with a # sign. Remove the # sign to enable a local customisation. Example:
  
  • #Set DENYWEBCHANGE = UnknownUser
• Preferences are used as TWikiVariables by enclosing the name in percent signs. Example:
  • When you write variable %WEBBGCOLOR% , it gets expanded to #D0D0D0
• The sequential order of the preference settings is significant. Define preferences that use other preferences first, i.e. set WEBCOPYRIGHT before WIKIWEBMASTER since %WEBCOPYRIGHT% uses the %WIKIWEBMASTER% variable.
• You can introduce your own preferences variables and use them in your topics and templates.

Related Topics

• TWiki.TWikiPreferences, Main.TWikiPreferences - site-level preferences
• TWikiUsers - list of user topics. User topics can have optional user preferences
• TWikiVariables - list of common %VARIABLES%
• TWikiAccessControl - explains how to restrict access by users or groups

Tools

• Rename, move or delete this web:
  • Rename/move/delete web..., looking for references in all public webs - See also: ManagingWebs

Web Search

Search: \.*

Tópicos

• Apresentação
• Equipa Docente
• Programa
• Bibliografia
• Método de Avaliação
• Sumários
• Material
• Projectos
• Notas

Avisos

Create New Topic in Education/AeC Web

Once you have created the topic, consider adding links in related topics to the new topic so that there are more ways people can discover it.