"Your life as it has been is over.
We will add your biological and technological distinctiveness to our own.
For this time forward you will serve us.
You will be assimilated.
Resistence is futile."
Fonte: Discurso de recepção aos calouros
ou "The Borg -- Star Trek, The Next Generation".
Bem-vindo à MAC0323 Algoritmos e Estruturas de Dados II. Esta é uma segunda disciplina em estruturas de dados e projetos de algoritmos. Abaixo está uma descrição de alguns dos ingredientes principais desta disciplina.
Os responsáveis por está edição de MAC0323 são Gustavo Silva, José Coelho de Pina e Mateus Barros Rodrigues.
IntroduçãoProgramas 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:
Apesar dos termos tipo de dados, tipo abstrato de dados 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 abstrato 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 os tipos abstratos de dados são chamados de 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.
ObjetivosEm 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 (ou classes) 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 que veremos nesta disciplina 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 desta disciplina fornecer aos estudantes elementos e técnicas que possam auxiliá-los a escrever bons algoritmos e estruturas de dados. Pré-requisitosPara 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ópicosMAC0323 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:
|
"Programadores iniciantes tendem a colocar a culpa dos erros no
compilador, na biblioteca, no mau tempo, . . .
Programadores experientes gostariam de ser iniciantes para ter
a quem culpar, além deles mesmos . . ."
The Practice of Programming
Brian Wilson Kernighan e Robert C. Pike
"Testes mostram a presença de erros,
mas não a ausência."
Edsger W. Dijkstra
A nota final na disciplina será baseada em dois componentes:
MEP = X/Sonde X é o total de pontos acumulado pelo aluno e S é o total de pontos possíveis.
MP = (P1 + 2×P2 + 2×P3)/5onde, P1, P2 e P3 são as notas das três provas.
se MP ≥ 5 e MEP ≥ 5 , então NF = MP + MEP , senão NF = min{MP,MEP} .Em código temos
#define min(m,n) ((m) < (n) ? (m) : (n))
float
nota_final (float mp, float mep)
{
if (mp < 5 || mep < 5) return min(mp,me);
return (mp + me) / 2;
}
NR = (Prec + NF )/2,