\input ReportFormat.tex \input Portuguese.tex

\begfile{CNPR83b.tex of December 28, 1983 2:21 pm --- Stolfi}

\title{JORGE STOLFI --- Relat\'orio de Atividades\lb
{\smallcaps abril a setembro de 1983}}

% Reference macros

\sect{1. Sum\'ario.}

{\bf JUNK -- REWRITE!!!}

Nos tres meses de ver\ao\ (julho a setembro) de 1981 dediquei-me a um trabalho de pesquisa na \'area de ``Computer Graphics'', sob a orienta\cao\ do prof. Leonidas J. Guibas, que consistiu 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. Alem disso, escrevi, em colabora\cao\ com o prof. Guibas, um artigo a respeito do trabalho desenvolvido no ver\ao. Este artigo foi publicado na revista {\it ACM Transactions on Graphics}, e apresentado 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.

Estou presentemente estudando v\'arios problemas na \'area de Geometria Computacional, sob a orienta\cao\ do prof. Guibas, com vistas \`a escolha de um assunto para a tese de doutoramento.

Em plano secund\'ario, continuei assistindo \'a serie de palestras semanais {\it Algorithms for Lunch}; completei o primeiro ano do curso de l\I ngua japonesa em Stanford; assisti como ouvinte a um curso de F\I 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, e meus planos para o pr\'oximo ano letivo.

\vfill\eject

\sect{2. Pesquisa em ``Computer Graphics''.}

A maior parte dos sistemas de gr\'aficos por computador produzidos hoje em dia s\ao baseados na representa\cao\ de imagens por matrizes bidimensionais (imagens rasterizadas, ou ``bitmaps''), cada elemento das quais indica a intensidade (e, eventualmente, a cor) de um ponto espec\I 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 (da ordem de um milh\ao\ de bits por imagem). Quando tais processamentos s\ao\ executados em computadores de uso geral, com pouco ou nenhum ``hardware'' especializado, \'e indispens\'avel utilizar-se ao m\'aximo a capacidade do processador central; em particular, \'e necess\'ario combinar numa \'unica ``palavra'' o maior n\'umero possivel de pontos da imagem, e pocessar os mesmos simultaneamente.

Devido a estas 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, tanto assim que alguns dos computadores mais recentes possuem instru\coes especialmente projetadas para facilitar a programa\cao\ de tais tarefas. Tais instru\coes\ t\>em se mostrado extremamente valiosas e eficientes, mas infelizmente as idiosincrasias do ``hardware'' introduzem complica\coes\ desnecess\'arias na sintaxe e sem\>antica das mesmas, e impedem seu uso generalizado.

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\I 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, projetei a linguagem algor\I tmica MUMBLE, baseada no c\'alculo acima mencionado, que permite a codifica\cao\ sucinta e leg\I vel de programas para a manipula\cao\ de imagens rasterizadas. Estamos presentemente desenvolvendo um interpretador para a mesma, que permitir\'a a utiliza\cao\ ``on-line'' das sub-rotinas do sistema BOP.

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

\sect{3. Pesquisa em Geometria Computacional.}

No trimestre de inverno (janeiro a mar\,co) de 1982 prestei servi\,cos de monitoria para o curso {\bf CS445 - 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. Entre outros, foram estudados m\'etodos para determinar o fecho convexo de um conjunto de pontos, a intersec\cao de pol\I gonos, a localiza\cao de um ponto numa subdivis\ao\ poligonal do plano, a decomposi\cao de figuras em partes convexas, o diagrama de Voronoi e suas aplica\coes.

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], em anexo), numa nota\cao\ uniforme e incluindo v\'arios resultados recentes que ainda n\ao chegaram a ser publicados. Em vista do interesse que essas notas despertaram, resolvemos tentar publicar uma vers\ao ampliada das mesmas, na qual estamos trabalhando no momento.

Durante a elabora\cao\ dessas notas, tive ocasi\ao\ de desenvolver ou melhorar alguns algoritmos para problemas de Geometria Computacional, sobre os quais estou presentemente escrevendo artigos. Um algoritmo permite determinar a intersec\cao de dois pol\I gonos simples com $n$ v\'ertices em tempo $O(n\log n + I)$, onde $I$ \'e o n\'umero de v\'ertices da intersec\c c\s ao; 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\I 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\I gono simples de $n$ v\'ertices no menor n\'umero poss\I 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.

No momento, estou estudando o {\it problema da localiza\cao\ numa sub-divis\ao\ do plano}: dada uma parti\cao\ do plano em $n$ pol\'\i gonos convexos, e dado um ponto arbitr\'ario $p$, determinar o pol\'\i gono que contem $p$.

Este problema \'e um dos mais importantes na \'area de Geometria Computacional, uma vez que o mesmo possui um grande n\'umero de aplica\coes\ e \'e frequentemente a etapa das mesmas que consome a maior parte do tempo de processamento. \'E poss\I vel resolver este problema em tempo $O(\log n)$ e espa\,co $O(n)$, usando-se um algoritmo devido a D. Kirkpatrick [\Kirk]; infelizmente, a complexidade desse algoritmo impede seu uso generalizado na pr\'atica. Estou portanto analisando possiveis simplifica\coes do algoritmo de Kirkpatrick, tanto no caso geral quanto no caso de aplica\coes espec\'ificas. Alem disso, estou examinando tambem um algoritmo devido a D. T. Lee e F. Preparata [\LeeP], que, apesar de ligeiramente mais demorado (tempo $O(\log n)^2$), parece ser mais f\'acil de implementar na pr\'atica.

Com refer\A encia a este problema, provei que uma decomposi\cao arbitr\'aria do plano em $2n$ tri\A angulos pode ser dividida em duas partes, cada uma contendo $n$ tri\A angulos, por uma linha poligonal monot\>onica, e que esta linha pode ser determinada em tempo $O(n)$. Este resultado permite simplificar bastante a constru\cao\ das estruturas de dados usadas no algoritmo de Lee e Preparata.

Uma das aplica\coes\ mais importantes do problema da localiza\cao\ \'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 $P
i$ do plano, tal que $q$ pertence a $P
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\I 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. Certas propriedades deste \'ultimo (que n\ao\ s\ao\ compartilhadas por ourtras decomposi\coes\ convexas do plano) prometem conduzir a vers\oes\ mais simples dos algoritmos de localiza\cao\ acima mencionados.

Outro problema que estou presentemente estudando \'e o da representa\cao\ interna de tais sub-divis\oes\ do plano. Topologicamente, uma sub-divis\ao\ dessas \'e equivalente a um grafo n\ao\ dirigido imerso na superficie de uma esfera, que por sua vez \'e apenas um caso particular de uma variedade bidimensional orient\'avel. No momento, estou analisando diversas estruturas de dados para a representa\cao\ de tais imers\oes\ (com base no trabalho de J. Edmonds [\Edm]), e estou desnvolvendo uma cole\cao\ de operadores b\'asicos para a manipula\cao\ das mesmas.

\vfill\eject

\sect{4. Outras pesquisas.}

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\I 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$), sendo 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\A 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 \'\i ndice $i$; os demais podem ser reconstru\'idos \'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

\sect{5. Cursos.}

\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\I 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\I vel de m\'ascaras de fabrica\cao) de um dispositivo VLSI a partir de sua especifica\cao funcional ou algor\I 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\I 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\I citas. A partir dessa lista, um conjunto de programas auxiliares permite a visualiza\cao\ do circuito em terminais de v\I 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\I 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\I 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\I 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\I 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\I 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\I 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\I 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\I 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\I 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\I 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

\sect{6. Planos para o Pr\'oximo Per\'\i odo.}

Conforme mencionei no sum\'ario, pretendo escolher o assunto para minha disserta\cao\ de doutoramento dentre os problemas de Geometria Computacional que estou estudando no momento. At\'e o fim deste ano, deverei ter oficializado minha escolha, e deverei ter conseguido formar uma banca examinadora para a mesma.

Para a escolha e desenvolvimento do assunto, contarei com a orienta\cao\ do professor Guibas, Pesquisador Associado do Departamento de Ci\A encia da Computa\cao de Stanford e membro do Palo Alto Research Center (PARC) da Xerox Corp., cujas especialidades s\ao Geometria Computacional e An\'alise de Algoritmos. O professor Donald E. Knuth concordou gentilmente em participar da banca examinadora e em servir como meu orientador oficial junto \'a Universidade, uma vez que esta fun\cao\ s\'o pode ser exercida por um membro integrante do Conselho Acad\A emico de Stanford.

N\ao espero ter maiores dificuldades na composi\cao de uma banca julgadora, pois o prof. Andrew Yao (que se tinha transferido para a Universidade de Berkeley) retornou a este Departamento, que conta tambem com dois novos docentes --- Vaughan Pratt e Ernst Mayr --- com excelentes qualifica\coes na \'area de An\'alise de Algoritmos.

Incu\I ndo os cursos acima relacionados, completei at\'e agora um total de 67 cr\'editos, distribu\I dos pelos seguintes departamentos: Computer Science, 37; Mathematics, 3; Electrical Engineering, 12; Asian Languages, 15. Estes cr\'editos mais que perfazem o total exigido pelo Departamento.

No pr\'oximo trimestre letivo deverei completar 10.5 trimestres de ``tuition'' integral, o que signfica que poderei me matricular como ``terminal graduate student'' (TGR) nos trimestres subseq\"uentes. Isso implicar\'a numa consider\'avel redu\cao\ das taxas escolares, j\'a que n\ao\ pretendo me matricular em cursos para cr\'editos nesse per\I odo\foot1{A taxa b\'asica de ``tuition'' para alunos TGR \'e cerca de US\$ 250 por trimestre; entretanto, eventuais cursos tomados para cr\'edito devem ser aprovados pelo orientador, e pagos \'a raz\ao\ de (aproximadamente) US\$ 200 por cr\'edito.}.

\date{31/agosto/1982}
\signed{Jorge Stolfi}

\vfill\eject

\sect{Bibliografia}

\paref\ \Fourier. {\smc Bracewell, R. N.}\titsp{\it The Fourier transform and its applications.} McGraw-Hill (1978).

\paref\ \Opt. {\smc Dixon, L. C. W.}\titsp{\it Nonlinear optimization.} Crane, Russack & co., N.Y. (1972).\par

\paref\ \Edm. {\smc Edmonds, J.}\titsp{\it A combinatorial representation for polyhedral surfaces.} {\rm Notices of the American Mathematical Society}, 7 (1960), p. 646.\par

\paref\ \Furst. {\smc Furst, M.} e {\smc Hopcroft, J.,} e {\smc Luks, E.}\titsp{\it Polynomial-time algorithms for permutation groups.} {\rm IEEE 21$\null^{\hbox{st}}$ Ann. Symp. on Foundations of Computer Science,} Syracuse, N. Y. (1980), pp. 36--41.\par

\paref\ \GSBOP. {\smc Guibas, L. J.,} e {\smc Stolfi, J.}\titsp{\rm A language for bitmap manipulation.} {\rm ACM Transactions on Graphics}, Vol. 1 No. 3 (julho 1982), pp. 191--214. (separata em anexo).\par

\paref\ \GSNotes. {\smc Guibas, L. J.,} e {\smc Stolfi, J.}\titsp{\it Introduction to Computational Geometry.} (a ser publicado; vers\ao preliminar em anexo).\par

\paref\ \Jap. {\smc Jorden, E. H.}\titsp{\it Beginning Japanese.} Yale University Press (1963).

\paref\ \CLang. {\smc Kernighan, B. W.,} e {\smc Ritchie, D. M.}\titsp{\it The ``C'' programming language.} Prentice-hall (1978).\par

\paref\ \Kirk. {\smc Kirkpatrick, D.}\titsp{\it Optimal search in planar subdivisions.} {\rm Technical report 81-13,} Dept. of Computer Science, Univ. of British Columbia, Vancouver.\par

\paref\LeeP. {\smc Lee, D. T.,} e {\smc Preparata, F.}\titsp{\it Location of a point in a palanar subdivision and its applications.} {\rm SIAM J. of Computing}, 6 (1977), pp. 594--606.\par

\paref\VLSI. {\smc Mead, C.} e {\smc Conway, L.}\titsp{\it Introduction to VLSI systems.} Addison-Wesley (1980).

\par\vfill\eject\end