\def\Fourier{1}
\def\Opt{2}
\def\Edm{3}
\def\Furst{4}
\def\GSBOP{5}
\def\GSNotes{6}
\def\Jap{7}
\def\CLang{8}
\def\Kirk{9}
\def\ShHo{???}
\def\LeeP{10}
\def\VLSI{11}

Nos tres meses de ver\ao\ (julho a setembro) de 1981 trabalhei sob a orienta\cao\ do Prof. Leo Guibas no desenvolvimento e implementa\cao\ de uma linguagem para a manipula\cao\ de imagens discretizadas.

No outono (outubro a dezembro) de 1981, cursei as disciplinas EE271 {\it Introduction to VLSI Systems} e EE262 {\it Two-dimensional Images}, obtendo grau {\bf A} em ambas. Em colabora\cao\ com o prof. Guibas, escrevi tambem um artigo a respeito do trabalho desenvolvido no ver\ao, artigo esse que que apresentamos no congresso SIGGRAPH '82 (Boston, 23 a 29 de julho de 1982).

No inverno (janeiro a mar\,co) de 1982, cursei a disciplina EE272 {\it Testing and Simulation of VLSI Circuits}, continua\cao\ do curso EE271, e fui monitor da disciplina CS445 {\it Computational Geometry}, ministrada pelo prof. Guibas. Como parte desta \'ultima tarefa, elaborei um conjunto de notas de aula que estamos presentemente revendo e expandindo para publica\cao\ em formato de livro. No decorrer dessa atividade, tive ocasi\ao\ de melhorar alguns dos resultados existentes nessa \'area.

No ver\ao\ de 1982, estudei e implementei v\'arios algoritmos para a constru\cao\ do diagrama de Voronoi de uma cole\cao\ de pontos no plano. Como parte desse estudo, desenvolvi uma nova estrutura de dados para a representa\cao\ de diagramas planares. Essa estrutura permite a descri\cao\ simult\>anea de um diagrama e de seu dual, e permite manipular a topologia do diagrama independentemente dos seus aspectos geom\'etricos. Outra propriedade importante dessa estrutura \'e que a cria\cao\ e manipula\cao\ da mesma exige apenas duas opera\coes\ fundamentais. Tais propriedades me permitiram simplificar consider\'avelmente o algoritmo de Shamos e Hoey para a constru\cao\ do diagrama de Voronoi.

Em plano secund\'ario, continuei assistindo \'a serie de palestras semanais {\it Algorithms for Lunch}; completei o primeiro ano do curso de l\ii ngua japonesa em Stanford; assisti como ouvinte a um curso de F\ii sica de Interiores de Planetas; e estudei alguns problemas em ar\'eas variadas, notadamente An\'alise Num\'erica e Matem\'atica Discreta.

Segue uma descri\cao\ mais detalhada das atividades acima relacionadas.

\vfill\eject

Na maioria dos sistemas de gr\'aficos por computador produzidos atualmente, a informa\cao a ser impressa ou exibida 'e representada internamente por uma matriz bidimensional (imagem rasterizada, ou ``bitmap''), cada elemento da qual indica a intensidade (e, eventualmente, a cor) de um ponto espec\ii fico da imagem. Esta representa\cao\ \'e especialmente conveniente para a apresenta\cao\ das imagens em tubos de raios cat\'odicos de varredura fixa, em impressoras fotogr\'aficas e xerogr\'aficas, e em muitos outros dispositivos gr\'aficos. Al\'em disso, ela permite uma flexibilidade virtualmente ilimitada na composi\cao\ e transforma\cao\ das imagens.

Em geral, o processamento de imagens neste formato requer a aplica\cao de procedimentos relativamente simples a um grande n\'umero de dados, de cem mil a um milh\ao\ de bits por imagem. Muitos computadores e dispositivos gr\'aficos existentes no mercado, particularmente em aplica\coes\ de tempo real ou grande volume, incluem circuitos especializados para esse fim. Entretanto, dispositivos assim equipados ainda constituem uma pequena fra\cao\ dos dispositivos gr\'aficos atualmente em uso: em geral, o processamento de imagens rasterizadas ainda \'e efetuado em computadores com arquitetura convencional.

Nesses casos, o grande volume de dados exige que a capacidade do processador central seja utilizada ao m\'aximo. Em particular, \'e necess\'ario combinar o maior n\'umero possivel de pontos da imagem numa \'unica ``palavra'' do computador, de forma a permitir seu processamento simult\>aneo. Devido a essas considera\coes, os mais simples problemas gr\'aficos (como, por exemplo, mover uma parte da imagem para um ponto diferente da tela) exigem programas surpreendentemente longos e complexos. \'E portanto necess\'ario em tais sistemas fornecer ao programador um conjunto de opera\coes\ elementares para manipula\cao\ de imagens rasterizadas. Essas opera\coes\ podem ser implementadas na forma de sub-rotinas inclu\ii na biblioteca padr\ao do sistema, ou de instru\coes\ micro-programadas, como \'e o caso de algumas m\'aquinas mais recentes.

Tais pacotes de opera\coes\ b\'asicas t\>em se mostrado extremamente \'uteis na pr\'atica. Infelizmente, na maioria dos casos a estrutura dessas opera\coes\ \'e excessivamente influenciada pelos detalhes da arquitetura da m\'aquina. Em consequ\>encia, sua sintaxe e sem\>antica s\ao\ desnecessariamente complexas, e sua portabilidade \'e pr\'aticamente nula.

Minhas pesquisas no ver\ao\ de 1981 foram voltadas para esses problemas. Nesses tres meses, desenvolvi um modelo matem\'atico e uma nota\cao\ uniforme (um ``c\'alculo'') para expressar opera\coes\ com imagens rasterizadas, e um esquema autom\'atico para converter f\'ormulas dessa nota\cao\ em programas eficientes. Baseado nesses princ\ii pios, projetei e implementei um conjunto coerente de sub-rotinas para a manipula\cao de imagens rasterizadas (BOP), que implementei e testei no computador Dorado usando a linguagem Cedar, ambos desenvolvidos pelo Palo Alto Research Center (PARC) da Xerox Corp.. Al\'em disso, desenvolvi o projeto preliminar uma linguagem algor\ii tmica (MUMBLE), baseada no c\'alculo acima mencionado, que permite a codifica\cao\ sucinta e leg\ii vel de programas para a manipula\cao\ de imagens rasterizadas.

Este trabalho foi desenvolvido sob a orienta\cao\ do prof. Leonidas J. Guibas de Stanford, em colabora\cao\ com o qual escrevi no trimestre seguinte um artigo [\GSBOP] expondo os resultados da pesquisa. Este artigo foi publicado na revista {\it Transactions on Graphics} publicada pela Association for Computing Machinery (ACM). Nos dias 23-29 de julho de 1982, participei do congresso SIGGRAPH '82, em Boston, Mass. (organizado pelo Special Interest Group in Computer Graphics da ACM), onde apresentamos o trabalho supracitado.

\vfill\eject

No trimestre de inverno (janeiro a mar\,co) de 1982 prestei servi\,cos de monitoria para o curso CS445 {\it Computational Geometry}, ministrado pelo prof. Guibas. O programa do curso cobriu algoritmos e t\'ecnicas para a solu\cao\ de problemas geom\'etricos em computadores digitais. Exemplos de poblemas t\ii picos dessa \'area s\ao: determinar o fecho convexo de um conjunto de pontos, a intersec\cao\ de pol\ii gonos, a localiza\cao de um ponto numa subdivis\ao\ poligonal do plano, a decomposi\cao de figuras em partes convexas, e assim por diante.

Considerada a completa inexist\>encia de material did\'atico sobre essa \'area, decidimos produzir e distribuir durante o curso uma cole\cao\ de notas de aula [\GSNotes], numa nota\cao\ uniforme e incluindo v\'arios resultados recentes que ainda n\ao chegaram a ser publicados. Estamos atualmente procurando transformar essas notas numa monografia para eventual publica\cao.

Durante o preparo dessas notas, tive ocasi\ao\ de desenvolver ou melhorar alguns algoritmos para problemas de Geometria Computacional. Um algoritmo (desenvolvido en conjunto com Harry Mairson, de Stanford) permite determinar a intersec\cao\ de dois pol\ii gonos simples com $n$ v\'ertices em tempo $O(n\log n + i)$, onde $i$ \'e o n\'umero de v\'ertices da intersec\cao; o melhor algoritmo conhecido at\'e o momento exigia tempo $O((n+i)\log n)$.

Outro algoritmo (desenvolvido em conjunto com Alan Siegel, de Stanford) permite determinar a tangente comum a dois pol\ii gonos convexos de $n$ v\'ertices em tempo $O(\log n)$, utilizando uma variante da t\'ecnica de bissec\cao. Este algoritmo \'e consideravelmente mais simples que o pr\'eviamente conhecido, apesar de ter a mesma efici\A encia assint\'otica.

Consegui tambem melhorar ligeiramente um algoritmo devido a Daniel Greene, que decomp\oe\ um pol\ii gono simples de $n$ v\'ertices no menor n\'umero poss\ii vel de partes convexas; a vers\ao\ melhorada exige apenas $O(n^2)$ espa\,co de mem\'oria, em vez dos $O(n^3)$ da vers\ao\ original.

Outro assunto que estudei neste per\ii odo \'e o {\it problema do ponto mais pr\'oximo}: dados $n$ pontos $p
1, p
2, ... p
n$ no plano, e um ponto arbitr\'ario $q$, determinar qual dos $p
i$ est\'a mais pr\'oximo de $q$. Se a cada um dos $p
i$ associarmos uma regi\ao\ $\Vscr
i$ do plano, tal que $q$ pertence a $\Vscr
i$ se e somente se $q$ est\'a mais pr\'oximo de $p
i$ do que de qualquer outro $p
j$, obteremos uma decomposi\cao\ do plano em $n$ pol\ii gonos convexos, conhecida como o {\it diagrama de Voronoi} dos pontos $p
i$. Obviamente, a determina\cao\ do ponto $p
i$ mais pr\'oximo a $q$ reduz-se ao da localiza\cao\ de $q$ no diagrama de Voronoi.

No decorrer do ver\ao\ de 1982 implementei dois algoritmos para a constru\cao do diagrama de Voronoi. Um dos algoritmos \'e incremental; isto \'e, os pontos $p
i$ s\ao\ introduzidos um de cada vez, e o diagrama recalculado ap\'os cada inser\cao. O outro algoritmo \'e recursivo, de acordo com a estrat\'egia de ``dividir para conquistar'', e \'e baseado num algoritmo publicado por M. I. Shamos e D.Hoey [\ShHo].

Ao implementar esses algoritmos, constatei que a manipula\cao\ do {\it diagrama de Delaunay}, o dual geom\'etrico do diagrama de Voronoi, apresenta grandes vantagens pr\'aticas do ponto de vista computacional. Esta observa\cao\ motivou-me a desenvolver uma estrutura de dados capaz de representar um diagrama planar (ou seja, um grafo n\ao-dirigido embebido no plano) e seu dual, simultanea e uniformemente, usando apenas alguns bits adicionais por aresta. Desenvolvi uma nota\cao\ matem\'atica para manipular tais estruturas de dados, e descobri que elas podem ser construidas e modificadas usando-se apenas duas opera\coes\ fundamentais: uma que cria novas arestas, e uma que junta ou separa vertices e/ou faces do diagrama.

\vfill\eject

Em car\'ater secund\'ario, e independentemente das pesquisas descritas acima, trabalhei por conta pr\'opria em dois outros problemas, nas \'areas de c\'alculo num\'erico e an\'alise combinat\'oria.

Na \'area de c\'alculo num\'erico, estou procurando desenvolver um algoritmo para a minimiza\cao\ de uma fun\cao\ real $f(x
1, x
2, ... x
n)$, utilizando apenas $O(n)$ espa\,co, e sem utilizar as derivadas parciais da fun\cao\ $f$.

O problema da minimiza\cao\ de fun\coes\ a $n$ vari\'aveis j\'a foi extensivamente estudado, e existem in\'umeros algoritmos eficientes para o mesmo (veja-se, por exemplo, [\Opt]). Entretanto, esses m\'etodos geralmente utilizam $O(n^2)$ espa\,co, impedindo seu uso em problemas com grande n\'umero de vari\'aveis.

O m\'etodo que estou testando \'e vagamente relacionado com os chamados {\it m\'etodos dos gradientes conjugados}, em particular com o algoritmo de Powell [\Opt]. Em vez de armazenar integralmente os $n$ vetores utilizados por esses m\'etodos, meu algoritmo armazena apenas as duas componentes mais significativas de cada um. No caso da fun\cao\ $f$ ser quadr\'atica nas vizinhancas do m\ii nimo, esta aproxima\cao\ reduz a converg\>encia do m\'etodo de segunda para primeira ordem; espero mostrar que a redu\cao\ do espa\,co para $O(n)$ compensa esta desvantagem, pelo menos em algumas aplica\coes.

Na \'area de an\'alise combinat\'oria, estudei o algoritmo de M. Furst e J. Hopcroft [\Furst] para a representa\cao\ de grupos de permuta\coes. A finalidade desse algoritmo \'e a seguinte: dado um conjunto $\Gamma$ de permuta\coes\ sobre os inteiros $1, 2, ..., n$, e uma permuta\cao\ $\pi$ dos mesmos elementos, decidir se $\pi$ pertence ao grupo $G=\langle \Gamma\rangle$ gerado por $\Gamma$.

Para esse fim, o algoritmo de Furst e Hopcroft constr\'oi uma {\it t\>orre de subgrupos} $G
1, G
2, ..., G
n$ de $G$, sendo que $G
i$ \'e o conjunto de todas as permuta\coes\ de $G$ que n\ao\ movem nenhum dos elementos \penalty-50 $i+1, i+2, ..., n$. Estes subgrupos podem ser representados em espa\,co $O(n^3)$ por meio de uma tabela de geradores $\theta
{ij}$ ($1\leq j< i\leq n$) tais que $\theta
{ij}\in G
i$ e $\theta
{ij}(i)=j$ (pode ser que n\ao\ exista uma permuta\cao com tais propriedades; em tal caso, a entrada $\theta
{ij}$ da tabela \'e deixada em branco).

Uma vez construida essa tabela, \'e possivel testar se uma permuta\cao\ $\pi$ pertence a $G=G
n$ em tempo $O(n^2)$: se $\pi$ n\ao\ move $n$, basta determinar se $\pi$ pertence a $G
{n-1}$; se $\pi(n)=k$, para algum $k<n$, basta verificar se $\theta
{nk}$ est\'a definida, e se $\pi\cdot \theta
{nk}^{-1}$ (que n\ao\ move $n$) pertence a $G
{n-1}$. Por indu\cao, o problema acaba se reduzindo ao teste de pertin\>encia em $G
1$, que \'e trivial.

O algoritmo de Furst e Hopcroft permite construir essa tabela em tempo $O(n^5\log n)$ (no pior caso, que parece ocorrer com raridade). Este resultado \'e not\'avel, levando-se em conta que a solu\cao\ deste problema por m\'etodos mais diretos exige tempo exponencial em $n$. Do ponto de vista pr\'atico, esse tempo \'e ainda excessivo; al\'em do que o armazenamento da tabela $\theta
{ij}$ exige $O(n^3)$ posi\coes\ de mem\'oria, o que em alguns casos pode ser uma desvantagem ainda mais s\'eria que o tempo de processamento.

Ao estudar esse algoritmo, descobri que \'e possivel representar a t\>orre de subgrupos usando no ma\'aximo $n$ geradores: essencialmente, para cada $j$ basta armazenar apenas o gerador $\theta
{ij}$ que tiver o menor \ii ndice $i$; os demais podem ser reconstru\ii dos \`a medida que for necess\'ario. Esta modifica\cao\ permite reduzir o espa\,co utilizado pelo algoritmo para $O(n^2)$, \`as custas de um fator adicional de $O(n)$ no tempo de execu\cao.

\vfill\eject

\disc {EE262 -- Two-dimensional Images.}
\curit Instrutor: {Ronald Bracewell.}
\curit T\'opicos: {Esta disciplina tratou de imagens no sentido ``cl\'assico'', i.e. consideradas como fun\coes\ reais definidas numa regi\ao\ do plano. Os principais t\'opicos tratados foram: sensibilidade espacial de antenas e sistemas \'oticos; correla\cao\, convolu\cao\ e transformada de Fourier em duas dimens\oes; transformadas de Hankel e Abel, e sua rela\cao\ com fun\coes\ de Bessel; filtragem, restaura\cao\ e real\,camento de imagens; interferometria; tomografia e a transformada de Radon.}
\curit Livro texto: {{\it The Fourier Tranform and Its Applications}, R. Bracewell [\Fourier].}
\curit Coment\'arios: {Apesar do fato de, hoje em dia, o processamento de imagens ser baseado quase que exclusivamente em t\'ecnicas digitais, o curso mal mencionou estas \'ultimas, preferindo se concentrar nos processos anal\'ogicos, que em geral s\ao\ respons\'aveis pelos primeiros est\'agios na forma\cao\ de imagens. Os exemplos e a motiva\cao\ para a parte te\'orica incluiram antenas de micro-ondas, telesc\'opios e r\'adio-telesc\'opios, c\>ameras fotogr\'aficas e de televis\ao, radar e outros sistemas semelhantes.}
\curit Cr\'editos: 3 \curit Grau: A

\disc {EE271 -- Introduction to VLSI Systems.}
\curit Instrutores: {Robert Matthews e John Newkirk.}
\curit T\'opicos: {Esta disciplina foi uma vers\ao\ melhorada do curso de mesmo nome oferecido no ver\ao\ de 1980, e tratou do projeto de circuitos integrados em larga escala (Very Large Scale Integrated Systems) usando tecnologia nMOS. No decorrer do curso cada grupo de dois alunos projetou un circuito integrado completo (com 1000-2000 transistores em m\'edia) que foi efetivamente fabricado por uma firma especializada e entregue aos alunos para teste no trimestre seguinte. O projeto foi desenvolvido usando-se uma linguagem simb\'olica para a descri\cao\ de circuitos integrados, e uma bateria completa de programas para verifica\cao, an\'alise e simula\cao\ dos projetos.}
\curit Livro texto: {{\it Introduction to VLSI Systems}, C. Mead e L. Conway [\VLSI].}
\curit Coment\'arios: {Apesar da carga hor\'aria exidida ser habitualmente muito acima da m\'edia, este \'e um dos cursos mais procurados do momento\foot1{o curso \'e oferecido duas v\>ezes ao ano, com 50 vagas de cada vez. No outono de 1981, mais de 30 inscritos foram exclu\ii dos por falta de vaga.}. Al\'em da \'obvia import\A ancia econ\>omica do assunto, sua popularidade \'e devida a seu enfoque metodol\'ogico: a premissa b\'asica do curso \'e que todas os possibilidades e restri\coes\ determinadas pela tecnologia de fabrica\cao\ dos circuitos integrados podem ser simplificadas e resumidas num conjunto extremamente reduzido de {\it regras de projeto}. As regras de projeto para a tecnologia nMOS, por exemplo, podem ser descritas numas poucas p\'aginas, e n\ao\ exigem familiaridade com teoria de circuitos, dispositivos eletr\>onicos ou tecnologia de semicondutores. Elas permitem que pesquisadores em ci\>encia da computa\cao, n\ao\ necessariamente especialistas em circuitos integrados, produzam o projeto completo (ao n\ii vel de m\'ascaras de fabrica\cao) de um dispositivo VLSI a partir de sua especifica\cao funcional ou algor\ii tmica.

\pcur O computador \'e uma ferramenta essencial para o projeto de circuitos integrados, e por essa raz\ao\ boa parte do curso foi dedicada ao estudo de sistemas de ``software'' para automa\cao\ de tais projetos. O sistema utilizado no curso consistiu de tr\>es componenetes principais: uma linguagem simb\'olica (CLL) para a descri\cao\ de circuitos integrados, um programa para a verifica\cao\ das regras de projeto, e um simulador ao n\'ivel de portas l\'ogicas.

\pcur A linguagem CLL permite a descri\cao\ das v\'arias m\'ascaras para a fabrica\cao do ``chip'' em termos de umas poucas formas b\'asicas (ret\A angulos, ``fios'', contatos entre camadas). As dimens\oes e coordenadas desses componentes podem ser especificadas por meio de express\oes alg\'ebricas. Uma caracter\ii stica essencial da linguagem \'e o fato de ela permitir definir sub-circuitos, ou ``c\'elulas'', e utilizar os mesmos repetidamente em qualquer ponto do projeto como se f\>ossem novos elementos b\'asicos. O compilador CLL expande automaticamente as refer\>encias a essas c\'elulas, e reduz a descri\cao\ de cada m\'ascara a uma lista de ret\>angulos com dimens\oes\ e coordenadas expl\ii citas. A partir dessa lista, um conjunto de programas auxiliares permite a visualiza\cao\ do circuito em terminais de v\ii deo ou impressoras xerogr\'aficas; a mesma \'e tambem usada para controlar diretamente os equipamentos autom\'aticos que produzem as m\'ascaras para a fabrica\cao\ do ``chip''.

\pcur Um programa separado verifica se regras de projeto (que especificam o espa\,camento e as dimens\oes\ m\ii nimas dos componentes) foram respeitadas, e aponta graficamente as viola\coes. Finalmente, um terceiro conjunto de programas analisa a descri\cao\ das m\'ascaras, transforma-a numa descri\cao do circuito ao n\ii vel de componentes el\'etricos (transistores e suas conex\oes), e simula o funcionamento do mesmo, sob contr\>ole do usu\'ario, permitindo a dete\cao\ de \>erros conceituais no projeto e seu diagn\'ostico.

\pcur Atualmente, existem v\'arios universidades e empr\>esas privadas capazes de fabricar os ``chips'' autom\'aticamente a partir da descri\cao\ num\'erica das m\'ascaras produzida pelo compilador CLL. Para diminuir os custos de fabrica\cao, v\'arios projetos s\ao\ combinados num \'unico ``super-chip'', e cada ``wafer'' fabricado cont\'em c\'opias de diversos ``super-chips''. Ap\'os a fabrica\cao, separa\cao\ e montagem destes \'ultimos, cada embalagem tem seus pinos conectados a um ``chip'' espec\ii fico, de modo a produzir uns cinco exemplares de cada projeto. Desta vez, a fabrica\cao dos ``chips'' levou aproximadamente dois meses, contados a partir da entrega dos projetos aos instrutores.

\pcur Nosso projeto consistiu de um controlador program\'avel para dispositivos el\'etricos de dois estados (l\A ampadas, motores, rel\'es, etc.). O prot\'otipo cont\'em, num \'unico ``chip'' de $3\times4$mm, uma mem\'oria de acesso sequencial de 105 bits, uma matriz l\'ogica de contr\A ole de 20 entradas, 30 t\A ermos e 40 sa\ii das, v\'arios registradores e contadores, 26 terminais para conex\oes externas, e v\'arias dezenas de circuitos especializados. O ``chip'' \'e capaz de ligar e desligar independentemente quatro dispositivos externos, a intervalos de tempo vari\'aveis, conforme especificado pelo conte\'udo da mem\'oria. O ``chip'' tambem permite ao usu\'ario examinar, inserir, apagar ou modificar as instru\coes armazenadas na mem\'oria, bem como iniciar ou interromper sua execu\cao\u. O projeto \'e integralmente modular, de modo que tanto a mem\'oria quanto o n\'umero de dispositivos controlados podem ser aumentados sem grandes dificuldades.}
\curit Cr\'editos: 3
\curit Grau: A

\disc {EE272 -- Testing and Simulation of VLSI Circuits.}
\curit Instrutores: {Robert Matthews e John Newkirk.}
\curit T\'opicos: {A parte central deste curso foi o teste, an\'alise dos defeitos, corre\cao e simula\cao do projeto desenvolvido no trimestre anterior.}
\curit Livro texto: {Notas de aula.}
\curit Coment\'arios: {Nesta disciplina foi apresentada uma nova metodologia para o teste de circuitos integrados em larga escala, baseada no uso de simuladores em ``software'' e de equipamento computadorizado para teste de circuitos integrados. De acordo com essa metodologia, o teste \'e controlado por um programa, escrito pelo autor do projeto, que especifica tanto o ``est\ii mulo'' (a sequ\A encia de sinais) a ser aplicado ao circuito, quanto a ``resposta'' que o mesmo deveria produzir se estivesse correto.

\pcur Este programa pode ser usado para controlar diretamente um testador de circuitos integrados, que aplica o est\ii mulo ao ``chip'' e compara sua resposta com a prevista pelo programa. Alternativamente, ele pode ser usado em conjunto com o simulador l\'ogico em ``software'', para testar a validade do projeto antes do ``chip'' ser fabricado. Esta segunda op\cao permite tambem determinar se o comportamento anormal do ``chip'' \'e devido a problemas de fabrica\cao ou a erros de projeto, e, neste \'ultimo caso, facilita imensamente a localiza\cao do erro.

\pcur Para codificar o programa, utilizamos a linguagem ICTEST, que foi recentemente implementada por pesquisadores de Stanford. ICTEST \'e baseada na linguagem de programa\cao ``C'' [\CLang], \`a qual foram adicionados novos comandos que permitem a descri\cao\ sucinta de sinais digitais. Sequ\A encias independentes de sinais l\'ogicos, incluindo dados num\'ericos, podem ser facilmente produzidas, sincronizadas e combinadas, nos formatos serial, paralelo ou segmentado.

\pcur Uma primeira vers\ao do ``chip'', fabricada em janeiro de 1982, foi testada por esse m\'etodo, revelando alguns erros l\'ogicos que n\ao\ tinham sido detectados no trimestre anterior. O projeto foi corrigido e simulado novamente, e esperamos ter oportunidade no futuro para obter uma nova vers\ao do ``chip''.}
\curit Cr\'editos: 3
\curit Grau: A

\disc {ALJ001/002/003 - First-year Modern Japanese}
\curit Instrutores: {Hiroshi Sakamoto e Kimie Nebrig.}
\curit T\'opicos: {Este curso objetivou dar ao aluno a habilidade de compreender e falar a l\ii ngua japonesa moderna, com \>enfase maior nas estruturas gramaticais usadas em transa\coes t\'ecnicas e comerciais. Al\'em da gram\'atica, vocabul\'ario e pr\'atica de conversa\cao, o programa do curso incluiu os alfabetos sil\'abicos {\it hiragana} e {\it katakana}, e cerca de 50 caracteres ideogr\'aficos ({\it kanji}).}
\curit Livro texto: {{\it Beginning Japanese}, de E. H. Jorden [\Jap]}
\curit Coment\'arios: {A carga did\'atica consistiu de uma hora di\'aria de aula (principalmente conversa\cao e exerc\'icios orais), mais meia hora di\'aria de estudo individual (fitas e livro texto). Os professores souberam conduzir muito bem o curso, cobrindo integralmente os dois volumes do livro texto, sem que isso exigisse nenhum esfor\,co especial por parte dos alunos.

\pcur Uma das raz\oes pelas quais decidi fazer este curso \'e a import\A ancia cada vez maior que o Jap\ao\ vem assumindo na \'area de computadores. Por enquanto, o maior crescimento tem-se verificado na ind\'ustria de ``hardware''; entretanto, em vista dos maci\,cos investimentos que o gov\>erno japon\>es tem realizado no setor acad\>emico e em pesquisa b\'asica, \'e de se esperar que esse pa\'is venha a se tornar tamb\'em um centro te\'orico de relev\>ancia. Em tal caso, o conhecimento da l\ii ngua japonesa pode vir a ser t\ao\ \'util para um cientista de computa\cao\ quanto o alem\ao\ ou franc\>es o s\ao\ hoje em dia.}
\curit Cr\'editos: {5+5+5}
\curit Graus: {A, B+, B}

\disc {GPH 195 - Physics of Planetary Interiors}
\curit Instrutor: {Norman Sleep.}
\curit T\'opicos: {O programa cobriu diversos t\'opicos da geof\ii sica do interior dos planetas do Sistema Solar, com maior \>enfase nos de composi\cao\ rochosa (Merc\'urio, V\>enus, Terra e Marte). Foram estudadas diversas teorias a respeito da forma\cao\ do Sistema Solar e suas implica\coes\ com rela\cao\ \'a composi\cao\ dos planetas; a origem da Lua; a estrutura prov\'avel do interior da Terra; o aquecimento dos planetas devido \'a radioatividade e \'a queda de meteoritos; esfriamento por convec\cao, forma\cao\ e deslocamento de continentes; contra\cao\ e deforma\cao\ da litosfera. Examinou-se tambem a distribui\cao dos elementos vol\'ateis entre os plan\>etas pr\'oximos, a quantidade de \a'gua existente em V\>enus e Marte, a composi\cao\ e estrutura de suas atmosferas, e o equil\ii brio quimico entre as mesmas e as respectivas litosferas.}
\curit Coment\'arios: {Assisti a este curso na categoria de ouvinte, por int\A eresse pessoal. O professor \'e uma das maiores autoridades no assunto; muitos dos resultados que ele apresentou foram frutos de pesquisas recentes, muitas ainda n\ao publicadas, baseadas nos dados colhidos pelas sondas planet\'arias Viking 1--2, Voyager 1--2, Pioneer 11 e Venera 13--14 h\'a menos de um ano.}

\vfill\eject

\date{28 de Dezembro de 1983}
\signed{Jorge Stolfi}

\vfill\eject

\def\refauth#1{\unskip {\smc #1}} % Author (s)
\def\reftit#1{\unskip\unskip, {\it #1}} % Title
\def\refpub#1{ {\rm #1}} % Publication
\parindent 0pt

\ref [\Fourier] {\refauth{R. N. Bracewell}
\reftit{The Fourier transform and its applications.}
\refpub{McGraw-Hill, 1978.}}

\ref [\Opt] {\refauth{L. C. W. Dixon}
\reftit{Nonlinear optimization.}
\refpub{Crane, Russack & co., N.Y., 1972.}}

\ref [\Edm] {\refauth{J. Edmonds}
\reftit{A combinatorial representation for polyhedral surfaces.}
\refpub{Notices of the American Mathematical Society Vol. 7, 1960, p. 646.}}

\ref [\Furst] {\refauth{M. Furst, J. Hopcroft, {\rm e} E. Luks}
\reftit{Polynomial-time algorithms for permutation groups.}
\refpub{21$\null^{\hbox{st}}$ Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1980, 36--41.}}

\ref [\GSBOP] {\refauth{L. J. Guibas {\rm e} J. Stolfi}
\reftit{A language for bitmap manipulation.}
\refpub{ACM Transactions on Graphics Vol. 1 No. 3, julho/1982, 191--214. (separata em anexo)}}

\ref [\GSNotes] {\refauth{L. J. Guibas {\rm e} J. Stolfi}
\reftit{Introduction to Computational Geometry.}
\refpub{(a ser publicado; vers\ao\ preliminar em anexo).}}

\ref [\Jap] {\refauth{E. H. Jorden}
\reftit{Beginning Japanese.}
\refpub{Yale University Press, 1963.}}

\ref [\CLang] {\refauth{B. W. Kernighan {\rm e} D. M. Ritchie}
\reftit{The ``C'' programming language.}
\refpub{Prentice-Hall, 1978.}}

\ref [\ShHo] {\refauth{M. I. Shamos {\rm e} D. Hoey}
\reftit{Closest-point problems.}
\refpub{Proc. 16$\null^{\hbox{th}}$ Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1975, 151--162.}}

\ref [\Kirk] {\refauth{D. Kirkpatrick}
\reftit{Optimal search in planar subdivisions.}
\refpub{Technical Report 81-13, Dept. of Computer Science, Univ. of British Columbia, Vancouver.}}

\ref [\LeeP] {\refauth{D. T. Lee {\rm e} F. Preparata}
\reftit{Location of a point in a planar subdivision and its applications.}
\refpub{SIAM Journal of Computing Vol. 6, 1977, 594--606.}}

\ref [\VLSI] {\refauth{C. Mead {\rm e} L. Conway}
\reftit{Introduction to VLSI systems.}
\refpub{Addison-Wesley, 1980.}}