\input REPHDR.tex
% file: CNPR82.tex
% last changed by J. Stolfi September 7, 1982 5:52 PM
\def\header{{\bf Relat\'orio de Atividades\hfil}}
\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\LeeP{10}
\def\VLSI{11}
\hrule
\vskip 3 pt
\hrule
\vskip 4pt
\pn\ctrline{\lbf JORGE STOLFI --- Relat\'orio de Atividades}
\pn\ctrline{\smc julho de 1981 a agosto de 1982}
\pn\ctrline{\smc Processo de Bolsa no exterior 200.583/79}
\par
\vskip 4 pt
\hrule
\vskip 3 pt
\hrule
\vskip 10mm
\sect{1. Sum\'ario.}
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\u. 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\c 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. Leonidas J. 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\u, 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\A em se mostrado
extremamente valiosas e eficientes, mas infelizmente as idiosincrasias do ``hardware'' introduzem complica\coes desnecess\'arias na sintaxe e sem\A 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, desenvolvi
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 uma linguagem algor\I tmica (MUMBLE),
baseada no c\'alculo acima mencionado, que permite a codifica\cao sucinta
e leg\'ivel 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\c co) de 1982 prestei servi\c cos de monitoria
para o curso {\bf CS445 - Computational Geometry}, ministrado pelo
prof. Leo 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\u.
Considerada a completa inexist\A 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\c c\s ao. 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\c 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\c 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\A 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 $p1, p2, ... pn$ no plano, e um ponto arbitr\'ario $q$, determinar qual dos $pi$ est\'a mais pr\'oximo de $q$. Se a cada um dos $pi$ associarmos uma regi\ao $Pi$ do plano, tal que $q$ pertence a $Pi$ se e somente se $q$ est\'a mais pr\'oximo de $pi$ do que de qualquer outro $pj$, obteremos uma decomposi\cao do plano em $n$ pol\I gonos convexos, conhecida como o {\it diagrama de Voronoi} dos pontos $pi$.
Obviamente, a determina\cao do ponto $pi$ 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(x1, x2, ... xn)$, utilizando apenas $O(n)$ espa\c 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\c 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\A encia do m\'etodo de segunda para primeira ordem; espero mostrar que a redu\cao do espa\c 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\A orre de subgrupos} $G1, G2, ..., Gn$ de $G$, sendo que $Gi$ \'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\c co $O(n↑3)$ por meio de uma tabela de geradores $\theta{ij}$ ($1\leq j< i\leq n$), sendo que $\theta{ij}\in Gi$ 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=Gn$ 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 $G1$, 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\A 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\c 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\c camento de imagens;
interferometria; tomografia e a transformada de Radon.}
\curit Livro texto: {{\it The Fourier Tranform and Its Applications}, R. Bracewell [\Fourier].}
Com: {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\A 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\A ezes ao ano, com
50 vagas de cada vez. No outono de 1981, mais de 30 inscritos n\ao conseguiram vaga.}.
Al\'em da \'obvia import\A ancia econ\A 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\A onicos
ou tecnologia de semicondutores. Elas permitem que pesquisadores
em ci\A 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\A 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\A ossem novos elementos b\'asicos. O compilador CLL
expande automaticamente as refer\A encias a essas c\'elulas,
e reduz a descri\cao de cada m\'ascara a uma lista de ret\A 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\c camento e as dimens\oes
m\I nimas dos componentes) foram respeitadas, e aponta graficamente as viola\coes\u.
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\u), e simula o funcionamento do mesmo,
sob contr\A ole do usu\'ario, permitindo a dete\cao de
\A erros conceituais no projeto e seu diagn\'ostico.
\pcur Atualmente, existem v\'arios universidades e empr\A 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 \A 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\c 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\c cos investimentos que o gov\A erno japon\A es tem realizado no setor acad\A 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\A 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\A 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 \A enfase nos de composi\cao rochosa (Merc\'urio, V\A 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\A etas pr\'oximos, a quantidade de \a'gua existente em V\A 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