Pesquisa de padrões

10 janeiro 2022, 13:30 • Paulo Alexandre Carreira Mateus

Pesquisa de padrões. Solução naive O(nm). Autómatos finitos. Solução baseada por Autómatos finitos. Autómato finito que aceita sequências cujos sufixos são o padrão. Análise da complexidade. Algoritmo de Knuth-Morris-Pratt.

Aula 5

10 janeiro 2022, 11:30 • Luís Carlos Miguelote Dias

Mais métodos da classe Graph: coGraph(), stronglyConnectedQ(), SCC() (strongly connected components e  shortestPath(o,d).

Pesquisa de padrões

10 janeiro 2022, 09:30 • Paulo Alexandre Carreira Mateus

Pesquisa de padrões. Solução naive O(nm). Autómatos finitos. Solução baseada por Autómatos finitos. Autómato finito que aceita sequências cujos sufixos são o padrão. Análise da complexidade. Algoritmo de Knuth-Morris-Pratt.

Quinta aula prática

17 dezembro 2021, 15:30 • Francisco Miguel Alves Campos de Sousa Dionísio

Definição da classe Graph usando para representação de um grafo quer uma matriz de adjacência quer uma listas de adjacência (e dimensão). Construtor e métodos addEdge(o,d), removeEdge(o,d), edgeQ(o,d), offspring(o) (lista dos descendentes diretos), BFS(o) (lista dos descendentes descobertos por pesquisa em largura), DFS(o) (lista dos descendentes descobertos por pesquisa em profundidade).

Nova definição desta classe usando listas de adjacência. Definição dos mesmos métodos para esta nova representação.

Quinta aula prática

17 dezembro 2021, 13:30 • Francisco Miguel Alves Campos de Sousa Dionísio

Definição da classe Graph usando para representação de um grafo quer uma matriz de adjacência quer uma listas de adjacência (e dimensão). Construtor e métodos addEdge(o,d), removeEdge(o,d), edgeQ(o,d), offspring(o) (lista dos descendentes diretos), BFS(o) (lista dos descendentes descobertos por pesquisa em largura), DFS(o) (lista dos descendentes descobertos por pesquisa em profundidade).

Nova definição desta classe usando listas de adjacência. Definição dos mesmos métodos para esta nova representação.