"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 à MAC0122 Princípios de Desenvolvimento de Algoritmos. Esta é uma disciplina introdutória em estruturas de dados e projetos de algoritmos. Abaixo está uma descrição de alguns dos ingredientes principais desta disciplina.
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çaõ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 bool 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 difinidas 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 os tipos abstratos de dados são chamados de classes e as operações sobre os dados ou objetos são chamadas 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.
Em programação orientada a objetos essa coleção de variáveis recebe o
nome de
|
ObjetivosEm MAC0122 estudaremos, através de exemplos, a correção, a análise de eficiência e projeto de algoritmos muito bacanas e que são amplamento 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 em MAC0122 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. É pretençã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 em disciplinas de Introdução à Computação como MAC0110, MAC0115 ou MAC2166. Principais tópicosMAC0122 estuda algoritmos para alguns problemas computacionais básicos. Isso serve de motivação para introduzir vários conceitos e idéias importantes. Alguns dos tópicos de MAC0122 são:
|