Algoritmos e Estruturas de Dados

Lição n.º 1 “Algoritmos e Estruturas de Dados”

“Algoritmos e Estruturas de Dados” •  Logística •  Tecnologia •  Aulas •  Avaliação

•  Programa da cadeira •  O ambiente de programação

20140210 Algoritmos e Estruturas de Dados 2

Tecnologia •  Linguagem: Java. •  Componente gráfica: Processing. •  Estilo: Checkstyle. •  Ambiente: Eclipse, linha de comando. •  Sistema operativo: Windows, MacOS, Linux. •  Avaliador automático: Mooshak. •  Tutoria: Moodle.

20140210 Algoritmos e Estruturas de Dados 3

Aulas •  Teóricas: Pedro Guerreiro. •  Práticas: Hamid Shahbazkia.

20140210 Algoritmos e Estruturas de Dados 4

Bibliografia principal Algorithms, quarta edição (2011), Robert Sedgewick e Kevin Wayne. Book site: http://algs4.cs.princeton.edu/

20140210 Algoritmos e Estruturas de Dados 5

http://www.amazon.co.uk/Algorithms-Robert-Sedgewick/dp/032157351X/

Bibliografia de interesse •  Introduction to Algorithms, 3.ª

edição, Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. http://www.amazon.co.uk/Introduction-Algorithms-T-Cormen/

•  The Art of Computer Programming, Donald Knuth. http://www.amazon.co.uk/Art-Computer-Programming-Volumes-1-4a/

•  Algorithms + Data Structures = Programs, Niklaus Wirth (1975). http://www.amazon.co.uk/Algorithms-Structures-Prentice-Hall-automatic-computation/

20140210 Algoritmos e Estruturas de Dados 6

Coursera Algorithms, Part I •  Instructors: Robert Sedgewick, Kevin Wayne. •  “This course covers the essential information that every

serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers (…) union-find algorithms; basic iterable data types (stack, queues, and bags); sorting algorithms (quicksort, mergesort, heapsort) and applications; priority queues; binary search trees; red-black trees; hash tables; and symbol-table applications.”

20140210 Algoritmos e Estruturas de Dados 7

https://www.coursera.org/course/algs4partI

Mais Coursera Algorithms, Part II •  “Part II covers graph-processing algorithms, including

minimum spanning tree and shortest paths algorithms, and string processing algorithms, including string sorts, tries, substring search, regular expressions, and data compression, and concludes with an overview placing the contents of the course in a larger context.”

20140210 Algoritmos e Estruturas de Dados 8

https://www.coursera.org/course/algs4partII

Programa de AED •  Conceitos fundamentais

•  Modelo de programação •  Sacos, pilhas e filas •  “Union-Find” •  Análise de algoritmos

•  Ordenação •  Algoritmos elementares •  Mergesort, quicksort •  Filas com prioridade

•  Busca •  Árvores binárias de busca •  Árvores equilibradas •  Tabelas de dispersão

•  Grafos •  Busca em profundidade •  Busca em largura •  Árvores de cobertura •  Caminho mais curto

•  Cadeias de carateres •  Busca de subcadeias •  Compressão de dados

•  Estratégias programativas •  Divisão-conquista •  Algoritmos gananciosos •  Programação dinâmica

•  Intratabilidade

20140210 Algoritmos e Estruturas de Dados 9

Algoritmos de programação •  Busca linear •  Busca dicotómica •  Bubblesort •  Quicksort •  Conversão numérica •  Reversão numérica •  Máximo, mínimo de um array •  Remoção de duplicados •  Comparação lexicográfica de arrays

20140210 Algoritmos e Estruturas de Dados 10

Algoritmos no ensino secundário •  Fatorização •  Máximo divisor comum •  Simplificação de frações •  Regra de Ruffini •  Método de Gauss

20140210 Algoritmos e Estruturas de Dados 11

Algoritmos da escola primária •  Adição •  Subtração •  Multiplicação •  Divisão •  (Sucessor)

20140210 Algoritmos e Estruturas de Dados 12

Algoritmos clássicos •  Algoritmo de Euclides.

•  Método para o cálculo de π, de Arquimedes.

•  Crivo de Eratóstenes.

20140210 Algoritmos e Estruturas de Dados 13

Algoritmo de Euclides •  Calcula o máximo divisor comum de dois números

inteiros positivos. •  É o mais antigo algoritmo inventado pelo espírito

humano.

20140210 Algoritmos e Estruturas de Dados 14

public static int euclidAlgorithm(int x, int y) { while (x != y) if (x < y) y -= x; else x -= y; return x; } Isto será um método

estático de alguma classe, em Java.

Algoritmo de Euclides, variantes recursivas •  Formulação recursiva

•  Formulação recursiva, curto-circuito:

20140210 Algoritmos e Estruturas de Dados 15

public static int euclid(int x, int y) { return x < y ? euclid(x, y-x) : x > y ? euclid(x-y, y) : x; }

public static int greatestCommonDivisor(int x, int y) { int result = x; if (y != 0) result = greatestCommonDivisor(y, x % y); return result; } Esta versão substitui uma

sequência de subtrações x -= y até x ser menor que y por x % y.

Algoritmo de Euclides, versão de combate •  Normalmente, usamos a seguinte variante iterativa:

20140210 Algoritmos e Estruturas de Dados 16

public static int gcd(int x, int y) { while (y != 0) { int r = x % y; x = y; y = r; } return x; }

Tenha esta sempre à mão!

Comparando as versões iterativas •  Eis uma função de teste para comparar na consolas

duas versões iterativas:

20140210 Algoritmos e Estruturas de Dados 17

public static void testIterativeVersions() { while (!StdIn.isEmpty()) { int x = StdIn.readInt(); int y = StdIn.readInt(); int z1 = euclidAlgorithm(x, y); StdOut.println(z1); int z2 = gcd(x, y); StdOut.println(z2); } }

Lemos e escrevemos usando a biblioteca stdlib.jar, que teremos juntado ao projeto no Eclipse, importando-a e acrescentando-a ao build path.

Classes StdIn e StdOut •  Usaremos a classe StdIn para ler e a classe StdOut

para escrever na consola.

20140210 Algoritmos e Estruturas de Dados 18

StdIn

StdOut

A função main •  Em cada classe, a função main apenas chamará as

funções de teste. •  Por enquanto, só temos uma função de teste:

•  A função main e todas as outras formam a classe Euclid, que teremos desenvolvido no Eclipse.

20140210 Algoritmos e Estruturas de Dados 19

public static void main(String[] args) { testIterativeVersions(); }

Classe Euclid

20140210 Algoritmos e Estruturas de Dados 20

public final class Euclid { public static int euclid(int x, int y) { return x < y ? euclid(x, y - x) : x > y ? euclid(x - y, y) : x; } // ... public static void testIterativeVersions() { while (!StdIn.isEmpty()) { int x = StdIn.readInt(); int y = StdIn.readInt(); int z1 = euclidAlgorithm(x, y); StdOut.println(z1); int z2 = gcd(x, y); StdOut.println(z2); } } public static void main(String[] args) { testIterativeVersions(); } }

Correndo no Eclipse

20140210 Algoritmos e Estruturas de Dados 21

Correndo no Eclipse, a interação dá-se na consola do Eclipse, terminando com ctrl-z (Windows) ou ctrl-d (Mac ou Linux).

Correndo na linha de comando •  Para correr na linha de comando, colocamo-nos da

diretoria bin, dentro do projecto, no workspace. •  Aí damos o comando •  Observe:

20140210 Algoritmos e Estruturas de Dados 22

java –cp ../stdlib.jar:. Euclid

Note que estamos “dentro” da diretoria bin e que a biblioteca stdlib.jar está “ao lado” da diretoria bin.

Testando as funções todas •  Eis uma segunda função de teste, para comparar os

resultados das quatro funções:

20140210 Algoritmos e Estruturas de Dados 23

public static void testAllVersions() { while (!StdIn.isEmpty()) { int x = StdIn.readInt(); int y = StdIn.readInt(); int z1 = euclid(x, y); int z2 = euclidAlgorithm(x, y); int z3 = greatestCommonDivisor(x, y); int z4 = gcd(x, y); StdOut.printf("%d %d %d %d\n", z1, z2, z3, z4); } }

Argumentos na linha de comando •  Selecionamos a função de teste por meio de um

argumento na linha de comando:

20140210 Algoritmos e Estruturas de Dados 24

public static void main(String[] args) { int choice = 1; if (args.length > 0) choice = Integer.parseInt(args[0]); switch (choice) { case 1: testIterativeVersions(); break; case 2: testAllVersions(); break; default: break; } }