apostila

. . . . . . . . . . . . . . . . . . . . . 163
10.2 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.2.1 Matrizes em Pascal . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.2.2 Exemplos elementares . . . . . . . . . . . . . . . . . . . . . . . 180
10.2.3 Procurando elementos em matrizes . . . . . . . . . . . . . . . . 186
10.2.4 Inserindo uma coluna em uma matriz . . . . . . . . . . . . . . . 188
10.2.5 Aplicac¸o˜es de matrizes em imagens . . . . . . . . . . . . . . . . 190
10.2.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
10.3 Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10.3.1 Introduc¸a˜o aos registros . . . . . . . . . . . . . . . . . . . . . . 209
10.3.2 Vetores de registros . . . . . . . . . . . . . . . . . . . . . . . . . 210
10.3.3 Registros com vetores . . . . . . . . . . . . . . . . . . . . . . . . 212
10.3.4 Observac¸o˜es importantes . . . . . . . . . . . . . . . . . . . . . . 213
10.3.5 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
11 Desenvolvendo programas de maior porte 225
11.0.1 Campo minado . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
11.1 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12 Tipos abstratos de dados 241
12.1 Tipo Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
12.2 Tipo Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
12.2.1 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
6 SUMA´RIO
Cap´ıtulo 1
Introduc¸a˜o
Este material conte´m notas de aulas da disciplina CI055 – Algoritmos e Estruturas de
Dados I, ministrada para os curso de Bacharelado em Cieˆncia da Computac¸a˜o (BCC),
Matema´tica Industrial (MatInd) e para o Bacharelado em Informa´tica Biome´dica
(BIB) da Universidade Federal do Parana´.
Esta disciplina e´ ministrada no primeiro semestre (para os calouros) e e´ a primeira
das quatro que cobrem o conteu´do ba´sico de algoritmos sem o qual um curso de
computac¸a˜o na˜o faz sentido. As disciplinas subsequentes sa˜o:
• Algoritmos e Estruturas de Dados II;
• Algoritmos e Estruturas de Dados III; e
• Algoritmos e Teoria dos Grafos.
A orientac¸a˜o da Coordenac¸a˜o dos cursos e´ que este deve ter um conteu´do forte
em conceitos de algoritmos no qual a implementac¸a˜o final em uma linguagem de pro-
gramac¸a˜o e´ vista apenas como um mecanismo facilitador ao aprendizado dos conceitos
teo´ricos.
O texto esta´ dividido em duas partes bem definidas, a primeira entre os cap´ıtulos 2
e 9, conte´m os princ´ıpios ba´sicos da construc¸a˜o de algoritmos elementares, incluindo
a parte de subprogramas, com especial atenc¸a˜o a questo˜es tais como passagem de
paraˆmetros e varia´veis locais e globais. A noc¸a˜o de modularidade e´ bastante explorada.
A segunda parte, a partir do cap´ıtulo 10, conte´m princ´ıpios de estruturas de dados
ba´sicas, onde se introduz a noc¸a˜o de vetores unidimensionais, a primeira das estruturas
de dados. Nesta estrutura, praticamos a elaborac¸a˜o de algoritmos modulares e ja´ na˜o
escrevemos um co´digo inteiro, mas sim um conjunto de func¸o˜es e procedimentos que,
em uma abordagem por refinamentos sucessivos (top down), sa˜o constru´ıdos passo a
passo.
Alguns algoritmos importantes sa˜o estudados em suas verso˜es ba´sicas: busca e
ordenac¸a˜o de vetores. Noc¸o˜es de complexidade de algoritmos sa˜o mencionadas, ainda
que de modo informal, pois isto e´ conteu´do de per´ıodos mais avanc¸ados. Contudo, e´
importante ao aprendiz ter noc¸a˜o clara da diferenc¸a de custo entre diferentes algorit-
mos.
7
8 CAPI´TULO 1. INTRODUC¸A˜O
As u´ltimas estruturas de dados relevantes para o primeiro per´ıodo sa˜o as matrizes
e o conceito de registro. Havendo tempo, tambe´m se discute estruturas um pouco
mais sofisticadas, misturando-se vetores, registros e matrizes.
Finalmente se oferece um desafio aos alunos. O objetivo e´ o de mostrar uma
aplicac¸a˜o interessante dos conceitos que eles ja´ dominam. Normalmente trabalha-se
em sala de aula o desenvolvimento de um programa que tem sido a construc¸a˜o de um
jogo simples que pode ser implementado em uma estrutura de matriz, eventualmente
com registros. A ideia e´ que eles possam fazer um programa mais extenso para
treinarem a construc¸a˜o de programas modulares. Este material constitui o u´ltimo
cap´ıtulo deste material.
O estudante na˜o deve iniciar uma parte sem antes ter compreendido o conteu´do
das anteriores. Tambe´m na˜o deve iniciar um novo cap´ıtulo sem ter compreendido os
anteriores.
Sobre a linguagem, o estudante e´ encorajado a buscar apoio na literatura e nos
guias de refereˆncia dispon´ıveis para o compilador escolhido (Free Pascal), incluindo
um guia de refereˆncia ba´sico que foi escrito pelos monitores da disciplina no ano de
2009.
A leitura destas notas de aula na˜o isenta o estudante de buscar literatura comple-
mentar, sempre bem-vinda. Em particular, uma o´tima histo´ria da computac¸a˜o pode
ser encontrada em [Tre83]. Alguns excelentes textos introduto´rios em algoritmos esta˜o
em [Car82], [Sal98], [Med05] e [Wir78]. Para mais detalhes de programac¸a˜o em Pascal
o leitor pode consultar [Far99] e tambe´m os guias de refereˆncia da linguagem [Gui].
Finalmente, embora talvez de dif´ıcil compreensa˜o para um iniciante, recomendamos
pelo menos folhear o material em [Knu68].
Cap´ıtulo 2
Sobre problemas e soluc¸o˜es
Vamos iniciar nosso estudo com uma breve discussa˜o sobre problemas e soluc¸o˜es. O
objetivo e´ deixar claro desde o in´ıcio que:
• na˜o existe, em geral, uma u´nica soluc¸a˜o para o mesmo problema;
• algumas soluc¸o˜es sa˜o melhores do que outras, sob algum crite´rio;
• alguns problemas sa˜o casos particulares de outros similares;
• as vezes, e´ melhor resolver o problema mais gene´rico, assim, resolve-se uma
classe de problemas, e na˜o apenas um.
Sera˜o apresentados dois problemas reais e para cada um deles segue uma discussa˜o
sobre a existeˆncia de diversas soluc¸o˜es para um dado problema. A eˆnfase sera´ dada
nas diferenc¸as entre as soluc¸o˜es e tambe´m na discussa˜o sobre ate´ que ponto deve-se
ficar satisfeito com a primeira soluc¸a˜o obtida ou se ela pode ser generalizada para
problemas similares.
2.1 Contando o nu´mero de presentes em um evento
No primeiro dia letivo do primeiro semestre de 2009, um dos autores deste material
colocou o seguinte problema aos novos alunos: quer´ıamos saber quantos estudantes
estavam presentes na sala de aula naquele momento. A sala tinha capacidade aproxi-
mada de 100 lugares e a naquele momento estava razoavelmente cheia.
Os estudantes discutiram va´rias possibilidades. Apresentamos todas elas a seguir.
Primeira soluc¸a˜o
A primeira soluc¸a˜o parecia ta˜o o´bvia que levou algum tempo ate´ algum aluno verbali-
zar: o professor conta os alunos um por um, tomando o cuidado de na˜o contar algue´m
duas vezes e tambe´m de na˜o esquecer de contar algue´m.
Quais sa˜o as vantagens deste me´todo? Trata-se de uma soluc¸a˜o simples, fa´cil de
executar e produz o resultado correto. E´ uma soluc¸a˜o perfeita para salas de aula com
9
10 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O˜ES
poucos alunos, digamos, 20 ou 30. Outro aspecto considerado foi o fato de que este
me´todo na˜o exige nenhum conhecimento pre´vio de quem vai executar a operac¸a˜o, a
na˜o ser saber contar. Tambe´m na˜o exige nenhum equipamento adicional.
Quais as desvantagens? Se o nu´mero de alunos na sala for grande, o tempo ne-
cessa´rio para o te´rmino da operac¸a˜o pode ser insatisfato´rio. Para piorar, quanto
maior o nu´mero, maior a chance de aparecerem erros na contagem. Foi discutida a
adequac¸a˜o desta soluc¸a˜o para se contar os presentes em um comı´cio ou manifestac¸a˜o
popular numa prac¸a pu´blica. Concluiu-se pela