MAC0323 Algoritmos e Estruturas de Dados II

Bem-vindo à MAC0323 Algoritmos e Estruturas de Dados II. Esta é uma segunda disciplina em estruturas de dados e projetos de algoritmos. Esta edição de MAC0323 é de responsabilidade de

Beatriz Marouelli (Bia)	Lais Baum (Lais)	Coelho

Introdução

Programas de computador armazenam, acessam e manipulam dados. Programas são uma formulação concreta de algoritmos baseados em uma representação particular dos dados. Muito do que é feito em várias áreas da ciência da computação, tais como compiladores, computação gráfica, sistemas operacionais, . . ., é buscar maneiras de representar os dados para que o armazenamento, acesso e manipulação destes seja feito de maneira eficiente, ou seja, consumindo pouco tempo e espaço.

Sempre que representamos dados no computador consideramos cada um dos seguintes aspectos:

• a maneira que os dados são modeladas;
• o conjunto de operações definidas sobre estes dados;
• a maneira de armazenar os dados;
• os algoritmos usados para manipular os dados.

Apesar dos termos tipo de dados, tipo abstrato de dados (classes) e estrutura de dados parecerem semelhantes eles têm significados diferentes. O tipo de dado de uma variável é o conjunto de valores que ela pode assumir. Por exemplo, uma variável do tipo boolean pode assumir os valores true e false.

Os itens 1 e 2 acima dizem respeito ao tipo abstrato de dados, ou seja, ao modelo junto com uma coleção de operações definidas sobre os dados. Um exemplo de tipo abstrado de dados é o conjunto dos números inteiros com as operações de soma, subtração, multiplicação e divisão. No contexto de orientação a objetos tipos abstratos de dados são implementados em classes e as operações sobre os dados ou objetos são realizadas através de métodos.

Já os itens 3 e 4 estão relacionados a aspectos de implementação. Para representar um tipo abstrato de dados em um computador usamos uma estrutura de dados, que é uma coleção de variáveis, possivelmente de diferentes tipos, relacionadas de diversas maneiras.

Objetivos

Em MAC0323 daremos prosseguimento ao estudo feito em MAC0121. Estudaremos, através de exemplos, a correção, a análise de eficiência e projeto de algoritmos e estruturas de dados muito bacanas e que são amplamente utilizados por programadores.

Veremos alguns tipos abstratos de dados básicos e algumas estruturas de dados elementares para armazenar estes dados juntamente com os algoritmos para manipular estas estruturas. Existem várias estruturas de dados para um mesmo tipo abstrato de dados e em geral não existe uma estrutura de dados que é a melhor para todas as circunstâncias.

Os algoritmos e estruturas de dados em MAC0323 nasceram de aplicações cotidianas em ciência da computação. Novas aplicações irão requerer a criação de novos algoritmos e estruturas de dados. É pretensão de MAC0323 fornecer elementos e técnicas básicas que possam auxiliá-los a implementar bons algoritmos e estruturas de dados.

Pré-requisitos

Para esta disciplina o pré-requisito é o conhecimento de técnicas básicas de programação que são vistas principalmente em MAC0121 Estruturas de Dados e Algoritmos I.

Principais tópicos

MAC0323 estuda algoritmos para alguns problemas computacionais básicos. Isso serve de motivação para introduzir vários conceitos e ideias importantes. Alguns dos tópicos de MAC0323 são:

- Bags, Queues e Stacks;
- Union-find;
- Tabelas de símbolos;
- Árvore binária de busca;
- Árvores balanceadas de busca;
- Tabelas de Hash;
- Grafos orientados e não orientados;
- Caminhos mínimos em grafos;
- Tries; e
- Autômatos e expressões regulares. 

Tudo isso com uma pequena pitada de análise de algoritmos e invariantes. Seguimos os passos do livro Algorithms de Sedgewick & Wayne (S&W). Realizaremos alguns experimentos computacionais para medir o consumo de tempos dos nossos programas. Essas medidas são usadas para propormos ou confirmarmos as nossas avaliações sobre a eficiência dos algoritmos. Procuraremos também medir a memória utilizada pelos nossos programas.

Programmers Life

Fonte: https://www.hongkiat.com/blog/programming-jokes/

Avaliação

A nota final em MAC0323 será devida a vários componentes.

Exercícios-programa

Nesta disciplinas teremos vários exercícios-programa (EPs). Teremos EPs em Java e em C. Os exercícios programas em Java utilizarão a biblioteca algs4. Cada exercício vale um certo número de pontos. A média MEP desses exercícios será a aritmética.

Provinhas

Teremos várias provinhas ao longo do semestre durante o horário das aulas. Cada provinha consumirá cerca de 10 minutos da aula e valerá um certo número de pontos. A média Mp dessas provinhas será a aritmética.

Provas

Teremos 3 provas. A média MP das provas será

    MP = max(P1 + P2 + P3)/3, (PSub + P2 + P3)/3, (P1 + PSub + P3)/3, (P1 + P2 + PSub)/3)

onde, P1, P2 e P3 são as notas das três provas e PSub = Mp.

Nota final

A nota final; NF, será calculada pela regra
se min(MP, MEP) >= 5, então

     NF = 0.5*MP +  0.5*MEP, 

senão

    NF = min(MP, MEP). 

Aqueles e aquelas com NF >=5 estarão aprovados.

Experienced Programmer

Fonte: https://br.pinterest.com/pin/486599934709469290/

Recuperação

Aqueles e aquelas que obtiverem nota final NF maior ou igual a 3 e menor que 5 terão direito a fazer a recuperação. A recuperação consistirá de uma prova e/ou EPs. Se Prec é a nota na prova de recuperação então a nota da recuperação NR, será calculada pela regra

    NR = (Prec + NF)/2, 

A condição para aprovação é NR >= 5.

Conduta ética

Os exercícios, provinhas e provas devem ser feitos individualmente. Você tem responsabilidade sobre cópias feitas de questões de suas provas e de seus programas. Não faça os exercícios em grupos e não compartilhe código: não permita que outro aluno tenha acesso ao seu programa. Você pode consultar seus colegas para esclarecer dúvidas e discutir possíveis soluções, mas não copie os programas.

O Departamento de Ciência da Computação considera qualquer forma de plágio uma infração disciplinar inadmissível.

Na ocorrência de tais casos, o Departamento recomenda que os alunos envolvidos sejam reprovados na disciplina em questão, e que o ocorrido seja relatado à CG para as demais providências.

Leia mais sobre plágio na página Plágio++ em disciplinas de Computação por Arnaldo Mandel e em Colaboração em MAC0323

Matrícula

Verifique seu status no sistema Júpiter depois do período de retificação de matrículas. Seu status deve ser "MATRICULADO". Se for "PENDENTE" ou "INSCRITO", procure imediatamente o Serviço de Alunos de Graduação.