Teoria&MerTrabalho ATC

A Teoria da Computao e o

profissional de informtica

Joo Jos Neto

Resumo

Discute-se neste trabalho a importncia do domnio do conhe-cimento e da fluncia em assuntos tericos e abstratos comoparte da bagagem conceitual dos profissionais da rea de In-formtica. Apresenta-se um quadro panormico geral da rea,tecendo-se comentrios sobre diversos assuntos tericos de inte-resse, procurando-se correlacion-los e mostrar a sua relevnciapara o exerccio competente da prtica profissional.

Palavras-chave: informtica; Computao; Teoria da Computa-

o; abstraes; cincia; tecnologia; fundamentos; prtica; aplica-

o.

Abstract

This paper discusses the importance of mastering and having de-tailed domain of theoretical and abstract knowledge as a part of theconceptual background for professionals in the field of informatics.A broad landscape of this field is shown, a diversity of interestingtheoretical subjects are commented and interrelated, and their re-levance for a competent professional practice is emphasized.

Keywords: informatics; Computation; Theory of Computation;

abstraction; science; technology; foundations; practice; applicati-

ons.

Escola Politcnica da USP PCS

Departamento de Engenharia de

Computao e Sistemas Digitais

Av. Prof. Luciano Gualberto,

Travessa 3, n. 158

Cidade Universitria

CEP 05508-900

So Paulo SP

[email protected]

Revista de Computao e Tecnologia da PUC-SP Departamento de Computao/FCET/PUC-SP ISSN 2176-7998

Vol. I

No. 1

4

1 Introduo

Nos dias de hoje, em que o imediatismo domina anossa sociedade, permeando muitas esferas scio-culturais, e influindo direta e significativamentenos rumos de toda a humanidade, diversos aspec-tos da formao dos profissionais da rea tm sidoalvo de discusses e de mudanas, visando suaadequao aos nossos tempos.

Em particular, tem sido muito questionada aconvenincia e at mesmo a necessidade de se estu-dar, conhecer e dominar assuntos abstratos, dadoque o exerccio profissional geralmente praticadoinduz ao uso mecnico e quase cego de elemen-tos pr-fabricados, de prateleira, parecendo atmuito estranho discutir a eventual importnciapara o profissional de um reforo de formao emconhecimentos complexos, exigentes e abstratos,como aqueles propostos pela Teoria da Computa-o.

Identificam-se a duas tendncias tecnolgicasque, embora complementares, infelizmente costu-mam ser interpretadas como sendo radicalmenteexcludentes: a primeira, sugerindo que se busquepreferencialmente o (re)aproveitamento de produ-tos e resultados de esforos anteriores como formade obteno de recursos humanos produtivos e efi-cientes, e a segunda, priorizando o cultivo da for-mao cientfica como meio de formao de pro-fissionais preparados para o desenvolvimento detrabalhos centrados na criatividade.

Naturalmente, sempre que levadas aos limites,tendncias como essas geralmente acabam porcontrapor-se, suscitando, de um lado, adeptos ex-tremos da explorao direta de capacitaes jconsolidadas, para o uso imediato de soluespreviamente desenvolvidas, e de outro, aquelesque radicalmente consideram legtimas apenas astendncias estritamente investigativas, puramentetericas, talvez sem compromisso com a realidade.

Aqueles se mostram quase sempre refratrios apromoverem investimentos na formao da com-ponente conceitual dos profissionais, e mais favo-rveis a investimentos de rpido retorno, que emgeral correspondem a um preparo mais superficiale utilitarista, menos formal, mais informativo epreponderantemente tecnolgico.

Os outros, por sua vez, por valorizarem maisa busca de conhecimentos novos, acabam priori-zando a pesquisa em reas pouco exploradas, oque exige investimentos de risco, a fundo per-dido, em pesquisa pura, os quais raramente apre-sentam garantias absolutas de retorno do inves-timento, de resultados dos desenvolvimentos naforma de produtos teis sociedade, do cumpri-mento dos prazos inicialmente estimados.

Como diz a sabedoria popular,a virtude nuncaest nos extremos, e assim, torna-se convenienteque seja identificado aquilo que cada vertente temde melhor para oferecer, buscando-se entre elas

um equilbrio aceitvel, de forma que possam cadaqual contribuir a seu modo para uma formaono-polarizada de um profissional que, apoiadona solidez que lhe pode conferir o conhecimentoprofundo das bases fundamentais da Computao,seja capaz de, no dia-a-dia, optar, de forma com-petente, entre a inveno de novas solues e aadequao, aos interesses de cada momento, desolues previamente estabelecidas.

1.1 Motivao

Pode para alguns parecer anacrnico, na nossa erados produtos prontos para o consumo, que conhe-cimentos como os oferecidos pela Teoria da Com-putao sejam propostos como instrumentos detrabalho para pessoas cujas formaes se revelamto diversificadas, e cujos interesses, so mescla-dos com os de outras reas, como o caso de tan-tos profissionais da Informtica, cujos alvos maisdiretos de interesse so os computadores e a com-putao.

No faltaram nem faltaro argumentos de apoioao progressivo esvaziamento de contedo das jto enfraquecidas disciplinas fundamentais doscurrculos de formao dos profissionais da rea,em nome do pouco interesse prtico que se alegaexistir por conhecimentos que, de to especializa-dos e complexos, conseguem fascinar apenas umapequena elite.

Nem faltam justificativas para a adoo de cri-trios cada vez mais restritivos de apoio ao de-senvolvimento da dispendiosa, demorada e incertapesquisa bsica em tantas universidades de todoo planeta, em nome da priorizao daquelas pes-quisas ditas aplicadas e sustentveis, potencial-mente lucrativas, em vista dos resultados que po-dem produzir em menor prazo e com menor custo.

Argumentos dessa natureza infelizmente con-vencem e empolgam a muitos, consequentementefavorecendo, em vrios nveis, tomadas de pos-turas que, em nome dos resultados imediatos ede uma to desejada sustentabilidade, acabameclipsando os efeitos de sua adoo no longo prazo,muitos deles adversos, perigosos, inevitveis, epossivelmente irreversveis, pelas restries queimpem s ideias e criatividade.

Este quadro, to hostil e to presente nos nossosdias, motiva uma reflexo profunda acerca da im-portncia e da necessidade de um rpido retornoao incentivo aos estudos e pesquisa de base,sem objetivos especulativos ou lucrativos, e queno discriminem, em suas metas, os temas maisabstratos da Teoria da Computao, os assuntosemergentes ou desconhecidos, que tipicamente nocostumam estar atrelados produo imediata deresultados ou de benefcios materiais.

Tal postura, vital para a soberania da naono que tange sua capacitao tcnico-cientfica,visa suprir os subsdios essenciais manuteno


Vol. I

No. 1

5

da produo cientfica de vanguarda, bem comopara a formao acadmica e profissional aut-noma daqueles que trabalham na rea, cujo pa-pel se mostra absolutamente essencial gneseno apenas dos fundamentos das futuras tecnolo-gias como tambm, principalmente, preparaodas prximas geraes de profissionais que, ao seutempo, devero estar aptos a capacitar outros, ea conduzir esses complexos desenvolvimentos semrecorrer compulsoriamente importao de profis-sionais, a qual nesse quadro certamente ter sidoprovocada pela ento provvel deficincia da ca-pacitao local.

Considerando-se a importncia que ganha acada momento o aspecto da qualidade, em suasmais variadas manifestaes, levando-se em contaa existncia do diversificado arsenal de ferramen-tas que nos oferecem as teorias conhecidas, muitopoderosas e aplicveis s mais diversas situaesdo dia-a-dia, pode-se constatar, pela simples ob-servao, que muito pouca nfase se tem dado,por ocasio da formao acadmica do profissio-nal, a um srio trabalho explcito de conscientiza-o, tanto aos alunos como aos professores, rela-tivo a toda essa conjuntura.

Torna-se, dessa maneira, muito importante for-mar uma conscincia bem fundamentada do va-lor que pode agregar, tanto qualidade do pro-fissional de Informtica como dos produtos porele desenvolvidos, o conhecimento profundo dosassuntos tericos que constituem os fundamentosconceituais e cientficos da Computao.

O mesmo se pode dizer em relao s indiscu-tveis prerrogativas tcnicas de que gozam os pro-fissionais que amplo domnio possuam sobre essestemas em relao queles que os desconhecem ouque deles prescindem, pois isso tambm invariavel-mente se reflete nem sempre de forma imedi-ata, porm previsvel e inexorvel na qualidadeapresentada pelos resultados do trabalho de cadaum.

Atravs da identificao e da anlise de diver-sos pontos, considerados essenciais formao debases firmes para a conscientizao acerca da im-portncia de uma slida fundamentao tericapara os profissionais de Informtica, o presentematerial pretende constituir uma pequena contri-buio, tanto para reforar convices sobre essefenmeno, como para promover uma possvel mu-dana de postura em relao a esse tema que, em-bora para alguns se mostre bastante bvio, expl-cita ou veladamente, com frequncia para outrosse constata to desnecessariamente controverso.

1.2 Organizao deste artigo

Aps essa motivao, apoiada na observao ena anlise de alguns fatos da realidade atual domundo da Informtica, o presente texto volta-sea uma discusso tcnica destinada a levantar os

principais pontos em que se cruzam as vias da te-oria e da tecnologia.

Para as diversas situaes assim identificadas,procura-se apresentar as principais razes de con-vivncia das duas frentes, citando-se, quandooportuno, opinies importantes a respeito de taisassuntos, emitidas por personagens ilustres da his-tria da Computao.

Para tanto, temas-chave da Teoria da Compu-tao so identificados, delineando-se suas depen-dncias relativas e suas aplicaes, e analisando-sea sua importncia prtica,para que se possa cons-tatar mais facilmente a relevncia que apresenta,para a qualidade profissional de cada um, o do-mnio e a fluncia em cada um dos aspectos doestudo de tais assuntos.

Conclui-se o artigo com um convite a uma sriareflexo acerca do valor da Teoria da Computa-o na formao acadmica dos futuros profissio-nais das inmeras reas de especialidade em quese subdividem as atividades da Informtica.

2 Os Aspectos Tericos da

Computao

Apresenta-se, nesta parte do artigo, a estrutura doambiente contextual histrico e tcnico em que sedesenvolve o tema de interesse central da presentematria.

Em primeiro lugar considerada a rea maisvasta e abrangente do conhecimento, que se refereao estudo da informao e da sua manipulaoautomtica, e que conhecida pelo nome de In-formtica.

Como parte nobre da Informtica, identifica-sea Cincia da Computao, importante membro deuma grande diversidade de compartimentos do co-nhecimento humano associados especialidade, osquais envolvem, entre outros, assuntos relaciona-dos com modelagens, mtodos, clculos, anlises,teorias, etc.

Analisando-se um pouco mais de perto a Cin-cia da Computao vislumbra-se, entre os muitosassuntos tratados, a Teoria da Computao [1,2],o mais importante alicerce de suas bases concei-tuais, em que esto apoiados todos os ramos daComputao. Por essa razo, reconhece-se na Te-oria da Computao um dos mais importantescampos de conhecimento fundamental, do qual de-pendem fortemente todas as demais reas.

Sem pretenses de exaurir o assunto, busca-se neste artigo apontar uma coleo significativade assuntos tratados na Teoria da Computao,identificando-se o inter-relacionamento existenteentre diversos dos temas abrangidos, e realando-se, quando possvel, a importncia de seu estudomediante a indicao do uso que na prtica se temfeito de cada um dos grupos de assuntos tericos.


Vol. I

No. 1

6

2.1 A Informtica

Em toda a histria, constata-se que, antes mesmoque determinadas questes, algumas das quaisbastante complexas, tenham sido sequer formu-ladas pela primeira vez, os cientistas costumamse antecipar apresentado para elas, diversas res-postas interessantes, elegantes e criativas, comoresultados de suas pesquisas.

Embora nem fosse possvel imaginar ento a fu-tura existncia de computadores digitais, e me-nos ainda, que aspecto teriam ou qual importnciaeles viriam a ter nos dias de hoje, j nos meadosdo sculo XIX George Boole brindava a Cinciada Computao com a imensa contribuio repre-sentada pela famosa lgebra que, com justia, levaseu nome.

Com as funes por ele idealizadas, tornou-sepossvel criar modelos precisos, tanto do funcio-namento das volumosas, lentas e dispendiosas re-des de circuitos lgicos eletromecnicos, utilizadasnos primeiros computadores, como igualmente dosgeis, compactos e econmicos circuitos digitaismicroeletrnicos modernos.

O advento da modernidade trouxe a industria-lizao, exigindo progressos tcnicos que permitis-sem s mquinas resolver problemas de forma me-lhor, mais rpida e mais confivel que os operrios.Surgiram ento os primeiros algoritmos, na formade receiturios que visavam preparar tais mqui-nas para o processamento automtico de certostipos de informao.

Importantes nomes apareceram, tais como Tu-ring, Gdel e Church, contribuindo decisivamentenessa fase embrionria da Informtica atravs desua marcante atuao, referente investigao daviabilidade ou no de se resolver certas classesde problemas por aplicao mecnica e sequen-cial de uma restrita variedade de operaes muitoelementares.

Na dcada de 1950, Chomsky, investigando abs-traes para uso em lingustica, plantou os ali-cerces tericos das gramticas gerativas, que maistarde vie-ram a manifestar sua grande utilidadeprtica nessa e em diversas outras aplicaes, comdestaque anlise lxica e sinttica de linguagensde programao, modelagem do comportamentode organismos biolgicos, ao projeto de hardwaree ao processamento de linguagem natural.

Esses desbravadores anteviram, pesquisaram ederam resposta algumas, muito antes da con-cepo dos primeiros computadores a variadase complexas questes, abrindo um caminho bemfundamentado e seguro no somente para o surgi-mento como tambm para a evoluo que condu-ziu a Informtica ao estado em que hoje se encon-tra.

Esta sem dvida uma significativa manifesta-o histrica da importncia de um estudo terico,profundo, da natureza de um problema computa-

cional, precedendo atividades de implementao eat mesmo da idealizao de aparatos fsicos ca-pazes de resolver automaticamente o problema emquesto.

Os resultados pioneiros de pesquisas como as deBoole, Turing, Gdel, Church, Chomsky e de tan-tos outros, apresentados com tanta antecednciaem relao ao advento das tecnologias que os vi-riam a utilizar, revelaram-se verdades gerais, fun-damentais, independentes da tecnologia, imunesao tempo e s reas de aplicao, refratrias moda, poltica, s preferncias e ao mercado,extremamente poderosas e perenes, continuandopor essa razo em pleno uso, incontestes, vlidase atualssimas, at os nossos dias.

2.2 Informtica e a Cincia daComputao

A Informtica dedica-se ao estudo do processa-mento lgico e automtico da informao, que emgeral atualmente realizado com a ajuda de com-putadores digitais. Manifesta-se preponderante-mente no estudo e desenvolvimento de computa-dores, de seus componentes mecnicos e eletrni-cos, e de seus programas, bem como em diversosaspectos da concepo, realizao e uso de lingua-gens de programao, tecnologias de desenvolvi-mento e softwares de aplicao.

Nos dias de hoje, a Informtica se mostra virtu-almente onipresente, manifestando-se em bancos,no comrcio e na indstria, em componentes mi-croeletrnicos embutidos em eletrodomsticos, naetiquetas de produtos, em telefones celulares, au-tomveis, jogos eletrnicos, instrumentos de me-dida, sistemas de comunicao, cmaras fotogr-ficas, equipamentos de laboratrio, robs, dispo-sitivos de sinalizao, de aquisio de dados, desensoriamento remoto e tantos outros.

nessa vasta rea que podem ser localizadas aTeoria da Informao, a anlise numrica, a repre-sentao do conhecimento, a modelagem de pro-blemas, os mtodos tericos e formais, os proces-sos de clculo, e entre todas essas, tambm a Cin-cia da Computao, alvo da presente publicao.

2.3 A Computao

O termo computao costuma ser empregado paradesignar o uso de algoritmos para a resoluo deproblemas. Como se diz formalmente, esse voc-bulo alude execuo de algoritmos como meiopara realizar o clculo de funes. Foi praticadapor milnios no passado, mentalmente ou por es-crito, muitas vezes com o auxlio de tabelas.

Ramo da Matemtica e da Cincia da Computa-o, a Teoria da Computao surgiu no princpiodo sculo XX, antes da inveno dos computado-res, e estuda modelos formais de computao, suaaplicabilidade e sua viabilidade prtica resolu-


Vol. I

No. 1

7

o das diversas classes existentes de problemas.

Desse estudo emergiram propostas, na forma dedife-rentes modelos de computao, representadosatravs de diversificadas abstraes, apresentadasem variadas notaes. Segundo a conjuntura de-nominada Tese de Turing-Church, todos esses mo-delos se equiparam uns aos outros quanto ao seupoder computacional, alm de serem todos tam-bm equivalentes a um computador hipottico queoferecesse uma disponibilidade ilimitada de me-mria:

A Mquina de Turing, que foi propostacomo modelo universal de computao, etrabalha com operadores muito rudimenta-res sobre instrues e dados gravados emuma fita de trabalho de comprimento infi-nito. Dos modelos universais de computa-o existentes, talvez seja o mais conhecidoe famoso, e bastante aderente ao estilo deprogramao representado pelo paradigmaimperativo;

O Clculo Lambda [3], formalismo que foiproposto e empregado na representao deprogramas desenvolvidos segundo o para-digma de programao adotado pelas lin-guagens funcionais, e que se mostra muitoadequado para a representao formal defenmenos computacionais ligados a lingua-gens de programao declarativas;

As Funes Recursivas [2], utilizadas emMatemtica desde pocas muito anteriores dos computadores, podem tambm servircomo um modelo computacional inspiradonaquela cincia, e, ao contrrio da maioriados outros modelos em uso, tm a grandevantagem de permitir a representao e amanipulao direta de valores numricos;

As Gramticas Gerativas [4] permitem a re-presentao de linguagens atravs do uso deregras de substituio, que operam sobresequncias de smbolos, sendo muito empre-gadas na especificao e na representao delinguagens artificiais,como as de programa-o e de outras notaes constitudas de ca-deias de caracteres com lei de formao co-nhecida, tornando natural a formalizao ea manipulao algortmica de textos simb-licos.

Os Dispositivos Adaptativos [5], particular-mente aqueles baseados em autmatos, somodelos de computao capazes de repre-sentar fenmenos computacionais comple-xos atravs de quaisquer abstraes cujocomportamento seja descrito atravs de umconjunto de regras dinamicamente vari-vel. Essa dinmica se obtm associando-se aplicao de cada regra uma ao queespecifica alteraes a serem realizadas so-bre o conjunto de regras. Assim,ao executa-rem essas aes adaptativas, tais dispositi-

vos podem ir alterando, de forma autnoma,seu prprio comportamento,em funo doseu histrico de funcionamento. Com isso,um dispositivo adaptativo torna-se equiva-lente Mquina de Turing, portanto po-der represen-tar o conhecimento adquiridoem sua operao, tendo, no entanto, sobre aMquina de Turing, nesse aspecto, a vanta-gem de concentrar, de forma localizada, emseu prprio conjunto de regras, a represen-tao de tal conhecimento. Assim, torna-sepossvel identificar e acompanhar at mesmode forma incremental a aquisio do conheci-mento por um dispositivo adaptativo, atra-vs da inspeo do seu conjunto de regras eda sua variao toda vez que, durante suaoperao, alguma ao adaptativa for exe-cutada. Por essa e diversas outras razes,os dispositivos adaptativos tm sido conside-rados como alternativas atraentes para a re-presentao de fenmenos de aprendizagem,na rea de inteligncia artificial.

Muitos outros modelos de computao tmsido propostos e podem ser encontrados comfacilidade na literatura, entre os quais po-dem ser destacados: os Sistemas de Post, asCadeias de Markov, as mquinas de Mealy ede Moore, diversas outras variantes das m-quinas de estados, dos autmatos e transdu-tores finitos e de pilha, Mquinas de TuringUniversais, mquinas virtuais diversas, uti-lizadas na execuo de diversas linguagensde programao (P-system, Java byte-code,etc), Redes de Petri, Statecharts, mquinasprobabilsticas, e inmeras outras.

A Teoria da Computabilidade investiga a pos-sibilidade de mquinas computacionais e de cer-tos formalismos tericos adotados como modelosde computao apresentarem ou no a capacidadede realizarem automaticamente determinados ti-pos de computao. Em termos do que se conhecehoje dos computadores e da computao, uma ver-so dessa investigao pode ser traduzida na buscade respostas para a pergunta seguinte: possvelou no construir um algoritmo capaz de resolver

de forma automtica um dado problema atravs da

execuo iterativa de passos de instrues em um

dado dispositivo computacional, como, por exem-

plo, um computador digital ou algum outro modelo

computacional?

Mais abrangente, a Teoria da Computao pro-pe, estuda e compara modelos de computao,as classes de problemas que cada um deles con-segue resolver e os limites a que cada qual estsujeito. Ilustrando, podem ser citados alguns pro-blemas para os quais impossvel criar progra-mas de computador que lhes sirvam de soluo.So esses os problemas ditos incomputveis, entreos quais se destacam: o problema da parada daMquina de Turing; o problema da correspondn-cia de Post; determinar se a interseco de duas


Vol. I

No. 1

8

linguagens livres de contexto arbitrrias tam-bm livre de contexto; determinar, para uma gra-mtica livre de contexto sobre um alfabeto no-unitrio, se a linguagem que ela representa regu-lar;determinar se uma gramtica livre de contextoarbitrria ambgua; determinar se uma lingua-gem livre de contexto arbitrria inerentementeambgua. Muitos outros problemas incomputveisexistem, mas felizmente constata-se a existnciade outra infinidade de problemas computveis, degrande importncia prtica, e isso motiva o seuestudo, do ponto de vista tanto terico como pr-tico.

Dos problemas computveis, alguns se mostramimpraticveis por exigirem um tempo abusivo ouuma quantidade de memria excessiva para suaoperao. Para os decidveis possvel a constru-o de algoritmos que sempre terminam, quais-quer que sejam os dados a eles fornecidos. Paraos indecidveis, possvel elaborar procedimentoscomputacionais, porm estes terminam somentequando se lhes apresentam dados corretos, ade-rentes ao que normalmente se espera, podendo, noentanto, iniciar um ciclo infinito de execuo emresposta aos demais dados.

O estudo da decidibilidade de algoritmos datados anos 1930, quando os estudiosos da rea ten-tavam demonstrar ser invivel realizar raciocniosmatemticos com a ajuda de dispositivos auto-mticos. Um interessante problema nessa rea o das provas automticas dos teoremas de umadada teoria. possvel provar que o excessivotempo de resposta de provadores de teoremas paradeterminadas teorias torna impraticvel seu usocom frmulas grandes. o caso da Aritmtica dePresburger, que se mostra decidvel, porm dupla-mente exponencial em complexidade.

Nos casos de problemas de alta complexidadecomputacional, pode ser interessante determinarpara quais situaes vale a pena desenvolver umasoluo algortmica e para quais outras mais con-veniente efetuar verificaes extensivas de propos-tas de soluo. O estudo das classes P e NP decomplexidade computacional costuma analisar fa-mlias de problemas que ilustram bem esta situa-o.

Se de um lado a Teoria da Computao buscasolues gerais e grandiosas para classes amplasde problemas, por outro lado ocupa-se tambmde determinar modelos de complexidade mnimaque resolvam satisfatoriamente situaes menosgerais, de interesse prtico.

Uma forma de avaliar o poder de expresso deum modelo computacional atravs do estudo daclasse das linguagens formais que esse modelo capaz de representar; o resultado dessa prtica uma taxonomia baseada na hierarquia propostapor Chomsky para as linguagens formais.

Isso tem importantes aplicaes prticas no es-tudo de linguagens, gramticas e autmatos: o

uso extensivo de expresses regulares para a espe-cificao de padres de busca em cadeias de ca-racteres levou diversas linguagens de programa-o e sistemas operacionais a oferecerem recursosnativos especficos com essa finalidade. o casode lingua-gens como Perl e Python, e de sistemasoperacionais como UNIX, Linux e similares.

No mbito das linguagens regulares, notrio ouso de autmatos finitos e de mquinas de estadosfinitos em um grande nmero de aplicaes impor-tantes, tais como no projeto de circuitos sequen-ciais, em alguns sistemas voltados automatiza-o da resoluo de problemas, na construo deprotocolos de comunicao, sequenciadores, con-troladores de interfaces Web, analisadores lxicosde compiladores e interpretadores para linguagensde programao, na especificao de sistemas rea-tivos e de tem-po real, e at mesmo na especifica-o da lgica de determinados tipos de programas.

Linguagens livres de contexto, as respectivasgramticas e os autmatos de pilha ocupam igual-mente seu lugar na imensido de aplicaes quefazem uso das abstraes e dos resultados da te-oria da computao. Assim, formalismos grama-ticais livres de contexto tm sido usados extensi-vamente desde a poca de sua concepo na re-presentao parcial da sintaxe de linguagens deprogramao [4, 6, 7]. Autmatos de pilha podemser empregados na representao de fenmenoslingusticos envolvendo aninhamentos sintticos, eservem assim para modelar o comportamento deprogramas constitudos por um conjunto de proce-dimentos potencialmente interdependentes e mu-tuamente recursivos.

Menos explicitamente exploradas, as linguagensdependentes de contexto esto muito mais disse-minadas no mundo da computao do que podeparecer primeira vista. Linguagens de progra-mao so, em sua quase totalidade, linguagensdependentes de contexto, para cuja representaoas gramticas livres de contexto e os autmatosde pilha se revelam insuficientes. Embora existamdiversos modelos suficientemente expressivos pararepresent-las, seu uso costuma ser evitado porgerar formulaes extensas, complexas e obscuras.Em lugar disso, costuma-se aproximar, na prtica,as linguagens de programao por meio de mode-los sintticos simplificados, livres de contexto, osquais devem ser complementados por trechos decdigo, funes ou procedimentos externos, quese responsabilizem pela representao das depen-dncias de contexto, ausentes na formulao sim-plificada. Esta tem sido prtica corrente na cons-truo de compiladores e de outros processadoresde linguagens de programao.

2.4 A Cincia da Computao

A Cincia da Computao estuda os fundamen-tos e a prtica das computaes, investigandoe explorando, atravs de algoritmos computacio-


Vol. I

No. 1

9

nais, estruturas matemticas que modelam fatosdo mundo real, permitindo assim que processoscomputacionais sejam formulados de maneira pre-cisa para ento manipul-los devidamente, aten-dendo as necessidades das aplicaes desejadas.

Para atingir esses objetivos, oferece ao profis-sional uma srie de contribuies tericas: pro-porciona bases em Linguagens Formais, na Teoriados Autmatos e em Complexidade Computacio-nal, oferece mtodos para que seja verificado seum requisito est sendo atendido ou no, disponi-biliza tcnicas para o desenvolvimento de modelos,e proporciona meios com os quais se pode avaliaro poder dos modelos adotados.

Cada vez mais potentes e mdicos, os compu-tadores digitais constituem os dispositivos tecno-logicamente mais importantes que materializamfisicamente os modelos abstratos oferecidos pelaCincia da Computao. Ao mesmo tempo, osprogramas (softwares) que neles se executam cons-tituem a melhor concretizao das abstraes l-gicas que com eles pode ser realizada no dia-a-dia.

Isso abre inmeras possibilidades para a utili-zao prtica de abstraes computacionais, queratravs do emprego de linguagens de programaobem projetadas e aderentes aplicao, quer paraa construo de compiladores ou interpretadores,permitindo a disponibilizao, nos computadores,dos recursos oferecidos por essas linguagens.

Os caminhos disponveis para a concepo detodas essas abstraes e dispositivos tecnolgicos,assim como os mtodos utilizados para a avaliaodas aplicaes da vida real que com elas so de-senvolvidas contam-se entre as principais contri-buies de cunho prtico proporcionadas pela Ci-ncia da Computao, as quais dificilmente teriamsurgido sem os importantes fundamentos tericosque lhes deram origem.

Pode-se identificar que uma importante caracte-rstica das teorias das quais se ocupa a Cincia daComputao que elas se apiam em bases ma-temticas muito bem estruturadas, constituindoassim um slido corpo de elegantes fundamentos,aplicveis a todas as atividades da rea.

A motivao maior do desenvolvimento desteramo do conhecimento gira em torno da investi-gao do alcance das computaes, da possibili-dade ou no de se efetuarem determinadas com-putaes, culminando no importante conceito dealgoritmo, cuja possibilidade de existncia for-temente associada viabilidade prtica de mate-rializao das computaes realizveis.

O estudo srio dos assuntos cientficos da com-putao proporciona ao interessado um duradourolastro de formao, de largo espectro, a respeitodos assuntos em questo, que lhe garante segu-rana conceitual ao longo de toda sua vida pro-fissional.Tal base tcnica dificilmente pode ser ad-quirida quando a formao do profissional estiverafastada da teoria, mas centrada na digesto fre-

quente de generalidades, de atualidades e de in-formao de divulgao.

Embora para a rea mercadolgica, estratgicae empresarial, esse tipo de preparo seja essencial,para a formao de um profissional com perfil maistcnico tal esquema geralmente se traduz somenteem uma cultura fugaz, especfica e temporria,acerca dos fatos, do estado da arte e da tecno-logia em moda em cada momento histrico, e issocostuma mostrar-se insuficiente para o exercciocompetente dos aspectos profissionais tcnicos dealcance mais profundo.

Em lugar de simplesmente informar o interes-sado, preparando-o a produzir rapidamente paracon-sumo imediato no mercado de trabalho, a for-mao acadmica e profissional baseada em funda-mentos slidos capaz de conceder-lhe algo muitomais verstil e perene: o embasamento de que ne-cessita para dominar os assuntos que constituemas mais profundas razes do conhecimento da rea,que resistam ao tempo, moda e tecnologia.

Isso no deve ser entendido como uma apologia alienao quanto a avanos tecnolgicos, mascomo um alerta para que os atraentes acenos doimediatismo no ofusquem o profissional exata-mente naquele que seria seu melhor momento parapriorizar sua formao conceitual em temas abran-gentes e universais, reduzindo sem anular a pri-oridade da assimilao rpida de atualidades e daabsoro imediata de treinamentos especficos emferramentas tecnolgicas particulares, de interesseimediato e efmero, mas restrito e localizado.

Com uma formao menos restrita e especfica,o profissional de computao sempre ter suadisposio uma gama considervel de conhecimen-tos oriundos da Cincia da Computao, os quaisvirtualmente podero ser utilizados no desenvol-vimento de variadas aplicaes, em qualquer reade sua atuao profissional, bastando para issoque, inicialmente, adquira habilidades para mode-lar adequadamente suas aplicaes usando o fer-ramental terico assim assimilado, de modo quepossa, num segundo momento, convert-los emprogramas executveis, ou seja, representados naforma de algoritmos.

Aqui se pode avaliar bem a importncia de umprofissional da rea conhecer e dominar profunda-mente, em teoria e na prtica, todo o processo deelaborao de algoritmos, desde a sua concepo,passando posteriormente pelos procedimentos deelaborao, materializao, verificao, e implan-tao, tanto de algoritmos representados por pe-quenos trechos de cdigo como dos atualmente fre-quentes sistemas de software, de porte cada vezmaior.

No basta que, durante o seu perodo de prepa-rao acadmica para o mercado, o profissional sedetenha apenas no estudo de um ou outro desseselementos, pois todos eles se mostram essenciais sua formao integral. Mostra-se, assim, de suma


Vol. I

No. 1

10

importncia que os programas dos cursos univer-sitrios da rea levem em considerao essas pon-deraes, equilibrando a nfase que do a essasdiversas componentes formativas de seus alunos.

2.5 A Teoria da Computao

No vasto campo da Cincia da Computao, pode-se dizer com segurana que a Teoria da Computa-o ocupa um merecido lugar de destaque, devido sua importncia como sustentculo conceitualde todos os conhecimentos da rea, tanto dos maisfundamentais e abrangentes como dos mais parti-culares e especficos [810].

Eliminadas as peculiaridades dos problemas es-pecficos e a influncia de idiossincrasias apresen-tadas pelas tecnologias especficas em uso, a Te-oria da Computao investiga, estabelece e inter-preta propriedades intrinsecamente associadas aossistemas computacionais, da tirando conclusesuniversais de ampla aplicabilidade, e que se pro-vam independentes de casos e de especificidades.

Os resultados da Teoria da Computao, nasua maioria obtidos na primeira metade do sculopassado,comprovaram-se totalmente refratrios histria. Ilustrando atravs de um caso particu-lar, na rea da programao pode-se dizer que taisresultados no foram afetados pelas evolues tec-nolgicas refletidas no paradigma de programaoadotado, valendo indiferentemente para progra-mas desenvolvidos em linguagens funcionais, im-perativas, lgicas, orientadas ou no a objetos, eexplorando ou no o paralelismo ou a concorrn-cia.

Devido universalidade de que so dotadas,as poderosas ferramentas tericas proporcionadaspela Teoria da Computao nem sempre so di-reta e imediatamente aplicveis a casos particula-res, a um produto especial ou a alguma tecnologiaespecfica, e esse fato infelizmente leva muitos pro-fissionais por falta de base ou desinteresse aafastar-se delas, a desconsiderar e at a desvalori-zar sua importncia.

No de se esperar que profissionais despre-parados sejam capazes de apreciar o alcance dosrecursos tericos, pois para isso deveriam possuirhabilidades que os capacitassem anlise de situa-es prticas, permitindo-lhe identificar, destacare utilizar, dentre tantos resultados tericos dispo-nveis, aqueles que se aplicam ao seu caso prticoespecfico, mas isso s se consegue com um bompreparo tcnico prvio, que lhes proporcione am-plo domnio sobre os fundamentos dessa teoria.

Reconhecendo a imensa importncia desse ramodo conhecimento, Lewis e Papadimitriou [2] acer-tadamente recomendam seu estudo acadmicoprecoce, como forma de proporcionar no somentea assimilao de habilidades matemticas, essen-ciais ao futuro profissional, como tambm as basesconceituais para um aproveitamento significativa-

mente melhor de todas as disciplinas da rea.

preciso lembrar que, como seria de se espe-rar, a Teoria da Computao se fundamenta emmtodos e tcnicas da Matemtica, em particu-lar, na teoria dos conjuntos. Scheurer [11], alertaque se deveria dar mais ateno aos conhecimen-tos de teoria dos conjuntos ministrados aos futurosprofissionais da rea, de modo que estes possamempreg-los de forma to natural quanto os pro-gramadores utilizam com fluncia as suas lingua-gens de programao.

Recorda ainda esse autor que os processos demodelagem formal e matemtica independem douso ou no de computadores. Afirma ainda que,didaticamente, este importante fato deveria serconsiderado com muita nfase ao se ministrar co-nhecimentos bsicos aos futuros programadores,permitindo-lhes assim assimilar em primeiro lu-gar os fundamentos, para, s depois de adquiridaa devida habilidade de modelagem, comearem autilizar o computador para a implementao dosmodelos.

instrutivo constatar que a Teoria dos Conjun-tos e a Lgica Matemtica funcionam como alicer-ces para muitas reas da computao, merecendodestaque a engenharia de software, o software b-sico e as linguagens de programao, nos quais sepode identificar o uso extensivo dos seus conceitosno estudo e na prtica de mtodos algbricos tra-dicionais, de mtodos formais, da semntica axi-omtica para linguagens imperativas, da semn-tica denotacional para linguagens declarativas, eem tantas outras situaes.

Outra rea, que merece ateno pelo amplo usoque faz de assuntos tericos fundamentais, envolveas Linguagens de Programao [4, 6, 7, 1216] eos correspondentes Paradigmas [17, 18]: impera-tivo, funcional, lgico, orientado a objetos, para-lelo, concorrente, etc., cada qual extensivamenteexplora um ou mais temas associados, da Teoriada Computao.

Na rea da modelagem de dados e na teoria dosBancos de Dados, identificam-se muitos conceitosque se fundamentam em conceitos matemticosbsicos oriundos de temas tais como a teoria dosconjuntos, as relaes e funes, a lgebra e o mo-delo relacional.

Muitas outras reas interessantes poderiam seraqui listadas cujo lastro terico e fundamental estna Teoria da Computao, mas as que foram ante-riormente apresentadas constituem uma amostrasignificativa do alcance exibido por essa impor-tante teoria fundamental da Cincia da Compu-tao, e do papel desempenhado por ela no desen-volvimento e no aprimoramento tcnico das apli-caes computacionais.


Vol. I

No. 1

11

3 Convenincia do Estudo de

Teoria

Em seu prefcio ao livro de F. S. Beckman [19],j em 1980 o corpo editorial da srie escreve queo campo do software bsico surgiu a partir dasoma dos esforos esparsos de inmeros profissi-onais de diversas especialidades, pressionados aproduzirem artesanalmente programas de sistemaque fossem prticos e funcionais.

Adiante, em seu prprio prefcio, esse autor re-conhece a vastido dos temas que compem o as-sunto do livro,e afirma que em suas 443 pginasno se aprofunda suficientemente nos aspectos for-mais da matria, e que por essa razo, o seu li-vro no seria recomendvel para estudantes sriosde matemtica em cursos de graduao ou ps-graduao devotados ao tema.

razo para uma reflexo preliminar um con-fronto entre a opinio emitida pelo autor acercade seu prprio texto e o notrio excelente nvelapresentado pela publicao em pauta, especial-mente se a compararmos com tantos textos hojeadotados em cursos superiores da rea.

Neste ponto, cabe tecer mais algumas conside-raes sobre alguns dos bvios porqus do estudodos assuntos tericos da Computao, os quais la-mentavelmente at mesmo nos dias de hoje, ape-sar das evidncias, continuam sendo consideradospor tantos seguramente por desconhecimento doassunto como desnecessrios, difceis, desagrad-veis e at mesmo inteis.

Uma exposio desses profissionais, sem pre-conceitos, s inmeras belas e profundas questesconceituais que permeiam essa rea do conheci-mento torna-se a estratgia mais eficaz para con-tornar os tantos malefcios advindos desse fen-meno.

Reynolds [20], em seu livro, lembra que, embusca de atividades remuneradas permanentesque os satisfaam, os profissionais costumam,principalmente no incio de suas carreiras, mudarde emprego com uma certa frequncia, e isso re-fora a necessidade que tm de uma base concei-tual slida e abrangente, especialmente na rea daComputao.

Segundo Greenlaw [21], o conhecimento da te-oria auxilia o profissional at mesmo em aspectosde natureza humanstica, como , por exemplo, ocaso da utilizao das complexas tcnicas da crip-tografia para garantir privacidade no computador,e o domnio desse conhecimento influi decisiva-mente na competncia com que o profissional dacomputao exerce sua ocupao.

Referindo-se aos projetos de software da suapoca, Wulf, Shaw e Hilfinger afirmavam [22], jem 1981, que as deficincias principais observadasnos programas de ento no eram decorrentes delimitaes fsicas das mquinas, e sim, consequn-

cia frequente do despreparo, por parte dos pro-fissionais, na compreenso, em profundidade, danatureza dos seus projetos.

Reynolds [20] alerta tambm que de um pro-fissional da rea se espera no apenas competn-cia nas especificidades do assunto de sua especia-lidade, mas que domine muito bem cada um dostemas a ela relacionados, em especial os princpioscientficos subjacentes de maior profundidade.

Enfim, convm ainda notar que um conheci-mento fluente da teoria agua o juzo esttico doprofissional, dando-lhe habilidade para priorizarem seus projetos os aspectos mais naturais, es-pontneos e elegantes dos processos computacio-nais, apurando ainda seu senso esttico, favore-cendo assim a obteno de produtos com maiorbeleza estrutural.

No mundo de hoje, que tende a priorizar umcontnuo e imediato processo de captura e memori-zao das novidades de uma tecnologia em rpidaevoluo, a cultura assim adquirida mostra-se ef-mera e insuficiente, motivando que seja resgatadaa habilidade tcnica do profissional atravs do in-centivo ao uso freqente e sistemtico do racioc-nio abstrato para a recuperao e expanso plenados seus processos mentais.

Num cenrio como esse, torna-se indispensvelo exerccio da habilidade de raciocinar, e no ape-nas de memorizar, e neste papel insubstituvel oestudo da teoria, dele resultando uma preciosa de-senvoltura na formulao precisa e clara de idias,na capacitao ao julgamento do alcance e das li-mitaes dos aparatos tecnolgicos em uso, e nahabilitao para uma boa avaliao tcnica de pro-postas de solues algortmicas para os problemas.

3.1 Temas-chave da Teoria daComputao

Permeando todos os estudos relacionados com osaspectos tericos da Computao, encontram-seos assuntos usualmente conhecidos comoMatem-tica Discreta [23,24] e Lgica Matemtica [25,26].

Truss [27] afirma que, independentemente deeventuais aplicaes, somente por sua complexi-dade e beleza a matemtica j em si prpriafascinante e significativa, merecendo ateno e es-tudo.

Diz tambm ser um verdadeiro prmio o fatode a matemtica ser tambm til, embora isso de-corra da compreenso profunda da lgica e elegn-cia subjacentes.

Completa sugerindo que no se veja a matem-tica como uma coleo complicada e incompreen-svel de abstraes, mas como um interessante eprazeroso tema de estudo, vivo e poderoso.

Entre os tpicos mais comumente estudados daTeoria da Computao, merecem destaque parti-cular os seguintes:


Vol. I

No. 1

12

matemtica discreta, teoria dos grafos, teo-ria dos conjuntos e teoria das funes recur-sivas;

linguagens formais e autmatos;

mquinas universais, computabilidade, algo-ritmos;

complexidade, intratabilidade;

mquinas finitas sequenciais com entrada esada, transdutores, mquinas de Mealy e deMoore;

lgica matemtica, gramticas formais, mo-delos matemticos, teoremas;

aspectos tericos subjacentes a redes neu-rais, computao evolutiva e sistemas nebu-losos.

Alm de darem uma viso que permite avaliar oalcance e as limitaes dos computadores, uma ob-servao menos superficial permite assegurar que,longe do que seria intuitivo, as complexas estru-turas conceituais estudadas na Teoria da Compu-tao gozam, na prtica, de uma extraordinriaaplicabilidade.

Assim, as ferramentas conceituais oferecidaspela teoria viabilizam a obteno de solues paramuitos complexos problemas da prtica, e apon-tam formas elegantes e econmicas para a realiza-o tecnolgica de tais solues.

Destacam-se, entre muitos outros, os seguintescasos ilustrativos:

a lgebra booleana e a teoria das mqui-nas sequenciais fornecem um substrato con-ceitual essencial para a descrio de muitosfenmenos computacionais, sendo em parti-cular extensivamente utilizadas no projetolgico de computadores e de sistemas di-gitais em geral, de codificadores, de siste-mas de comunicao, de controladores e derobs;

a teoria das relaes e a lgebra relacionalconstituem fundamentos tericos nos quaisse baseiam muitas tcnicas e mtodos hojedisponveis, que nas aplicaes prticas pro-porcionam formas metdicas e muito ade-quadas para a formulao rigorosa e confi-vel de sistemas de software que operam so-bre complexos bancos de dados;

autmatos, transdutores e outras mquinasde estados clssicas, formuladas com baseem estados internos, funes de transio efunes de sada, tm auxiliado significativa-mente na elaborao de pr-processadores,de compiladores, e no processamento simb-lico de cadeias de smbolos. Essas abstraesconstituem o alicerce de inmeros softwares,de interfaces entre o ser humano e os compu-tadores, em particular os de acesso s redesde computadores, de processos de automa-o industrial e de protocolos de comunica-o digital;

expresses regulares, que so formas grama-ticais muito populares de descrio de lin-guagens regulares, tm sido modernamenteadotadas como notao muito conveniente eprtica para a especificao de leis simplesde formao de cadeias simblicas, e, cadavez mais, utilizadas no dia-a-dia de inme-ras atividades profissionais, estando dispo-nvel como recurso nativo de muitas lingua-gens de programao, aplicando-se princi-palmente em anlise lxica, na categorizaode cadeias, no alinhamento de textos e no re-conhecimento e identificao de padres se-quenciais simples;

gramticas gerativas, originalmente estuda-das e propostas para aplicaes em lings-tica, representam formas construtivas para aespecificao de linguagens em geral, encon-trando freqentes aplicaes, no apenas nasua rea inicial de interesse, como tambmna anlise de lingua-gens complexas, e naespecificao formal de notaes para a ex-presso de programas noconvencionais, taiscomo ocorre no projeto de linguagens paraprogramas aplicativos especiais;

a teoria da complexidade computacional [28]e de algoritmos, que se ocupa do estudo deproblemas que permitem a obteno de so-lues algortmicas, ou seja, representveisatravs de programas de computador. Es-tudos nesses domnios tm propiciado o sur-gimento de mtodos e tcnicas destinadosa identificar a viabilidade de construo dealgoritmos cujo tempo de resposta no sejaintrinsecamente abusivo, e que no apresen-tem exageradas exigncias de memria detrabalho. Em outra vertente, procuram ga-rantir que algoritmos de criptografia se be-neficiem exatamente da dificuldade compu-tacional apresentada por alguns problemasespeciais, os quais tm constitudo o funda-mento de muitos dos protocolos criptogrfi-cos modernos;

a adaptatividade [5] outro aspecto que me-rece especial considerao, pelo poder com-putacional que pode proporcionar, e pelacompatibilidade que apresenta com os for-malismos clssicos estudados na Teoria daComputao. A ideia principal em que sebaseia a possibilidade que tem um dis-positivo conceitual adaptativo de automo-dificar dinamicamente seu comportamento.Essa propriedade lhe confere o mesmo podercomputacional da Mquina de Turing. Po-dem ser identificadas diversas manifestaeshistricas deste e de outros conceitos afins.Entre as principais, destacam-se: (i) direta-mente na mquina muitos programas an-tigos, originalmente produzidos em lingua-gem de baixo nvel, e at mesmo em lingua-gem de mquina, cujo cdigo se automodi-


Vol. I

No. 1

13

ficava para melhor aproveitar a memria docomputador, ou ento para realizar opera-es no disponveis nos comandos bsicosda mquina; (ii) nos sistemas de programa-o programas cujo cdigo era organizadocomo um conjunto de overlays, que se re-vezam dinamicamente na ocupao de umamesma rea de memria, viabilizando assima execuo de programas que de outra formano caberiam na memria fsica do compu-tador; (iii) nas linguagens de programao as linguagens extensveis, que permitemao programador definir novos comandos nalinguagem, para depois utiliz-los na codifi-cao de seus programas; (iv) nas metalin-guagens as gramticas de dois nveis, quepermitem criar, em duas etapas, gramticasespecficas das sentenas particulares de lin-guagens dependente de contexto.

as teorias dos conjuntos difusos, da compu-tao evolutiva e das redes neurais consti-tuem outras contribuies recentes aos fun-damentos da inteligncia artificial moderna,que nos ltimos anos tem se disseminado eevoludo de forma extraordinria.

Os temas mais importantes cobertos pela Teo-ria da Computao, discutidos nos tpicos estu-dados a seguir neste artigo, no esgotam a rea,mas fornecem um panorama bastante significativodos assuntos estudados, proporcionando uma boaviso de sua importncia prtica.

3.1.1 Linguagens Formais e Autmatos

Este um assunto que vem sendo estudado desdea dcada de 1950, e tem destacada importnciana Teoria da Computao, fundamentando muitosoutros temas da rea e oferecendo inmeros sub-sdios para aplicaes prticas. Ubquo em cur-rculos acadmicos da rea, por sua to grandeimportncia conceitual e prtica costuma-se reco-mendar que seja apresentado o mais precocementepossvel aos estudantes das reas da computaoe afins [2935]. Historicamente, constata-se queseu estudo foi inicialmente direcionado para ques-tes lingusticas associadas representao e tra-tamento de lingua-gem natural, mas acabou con-quistando a expresso que hoje apresenta ao senotar sua poderosa praticidade em aplicaes vol-tadas para a compilao ou interpretao de lin-guagens de programao em computadores digi-tais.

Essa disciplina concentra sua ateno nas lin-guagens, apreciadas especialmente do ponto devista de especificao e de reconhecimento, e tam-bm no estudo de modelos constitudos por abs-traes gerativas e cognitivas a elas associadas,consideradas tais linguagens segundo sua estru-tura, propriedades, caractersticas, classificaese inter-relacionamento.

Proporciona um variado e poderoso ferramen-

tal conceitual de extraordinria aplicabilidade aoutras disciplinas, habilitando o profissional a de-senvolver argumentaes matemticas, formais erigorosas, e proporcionando uma grande familia-ridade com os fundamentos e princpios da Cinciada Computao.

Muitas aplicaes deste ramo do conhecimentopodem ser identificadas. Dentre as mais clssi-cas, destacam-se: o processamento de linguagensde programao textuais, a representao de pro-cessos, estruturas e protocolos de comunicao, dofluxo da lgica dos programas, e de mquinas cujofuncionamento depende de sucessivas alteraesdo seu estado interno.

Arto Salomaa [36], cita Alfred Aho, que em umapalestra teria feito referncia teoria de lingua-gens formais como sendo a flor da cincia da com-putao, cujas ptalas seriam a complexidade, aslinguagens de programao, os sistemas de pro-gramao e os compiladores.

Atualmente, inmeras aplicaes modernas tmexplorado densamente as ferramentas conceituaisestudadas nesta disciplina. Entre elas destacam-se a computao grfica, em particular as anima-es computadorizadas, os hipertextos e as hiper-mdias, as interfaces Web, e as linguagens visuaise no-lineares em geral.

A importncia do estudo desse assunto se ma-nifesta de vrias maneiras:

proporciona uma viso panormica das ba-ses cientficas da computao;

proporciona fundamentos tericos para area, atravs do estudo de assuntos taiscomo decidibilidade, computabilidade ecomplexidade computacional;

fornece um slido lastro para o desenvolvi-mento de inmeras aplicaes computacio-nais, entre as quais o processamento de lin-guagens, o reconhecimento de padres e amodelagem de sistemas;

estabelece um forte elo entre a teoria e aprtica computacional;

permite que os conceitos e os resultados dateoria referente s linguagens, seus gerado-res, reconhecedores e analisadores possamser aplicados de forma rgida;

um dos temas que se mostra mais eclticoe menos divorciado dos demais assuntos es-tudados na Teoria da Computao.

Segundo uma das grandes autoridades mundiaisno assunto, Arto Salomaa [36], curioso observarque o tema das linguagens formais e autmatos,enquanto para tantos representa o principal tpicoda pesquisa na Cincia da Computao, para ou-tros constitui apenas algo de importncia muitoduvidosa. O autor jocosamente insinua ser issoapenas reflexo da poca e da cultura dos parece-ristas.


Vol. I

No. 1

14

Comentando sobre a receptividade dessa disci-plina pelos seus alunos, Peter Lintz menciona emsua obra [37] que os estudantes por vezes a ro-tulam como superfluamente abstrata e intil naprtica. Sugere que, em resposta a essa tendn-cia, o professor oriente seu ensino atravs de exer-ccios, e que continuadamente conscientize os alu-nos dos interessantes desafios que tais disciplinasvo impondo sua persistncia e inventividade namanipulao de problemas de difcil soluo.

Hopcroft e Ullman afirmam em seu livro cls-sico da rea [38] que esta disciplina compe umaimportantssima sub-rea da Cincia da Compu-tao.

Lembram que Noam Chomsky criou em 1956um modelo matemtico na forma de gramtica,com o qual se props a estudar a sintaxe de lnguasnaturais, mas alguns anos mais tarde seu modelorevelouse expressivo em outra rea, ganhando im-pulso por adequar-se perfeitamente formalizaoda lingua-gem de programao ALGOL 60.

O estudo terico da relao, hoje inseparvel,entre gramticas e os correspondentes autmatosacabou levando criao da importantssima ideiados compiladores dirigidos por sintaxe, e tambmdo conceito de compilador de compiladores, ouseja, dos geradores automticos de compiladores,ambos at hoje muito utilizados [39].

digno de uma cuidadosa e responsvel aten-o o alerta, proclamado por Hopcroft e Ullman[38],lembrando que virtualmente impossvel fa-zer qualquer estudo srio na rea da Computaono qual no seja priorizada a fluncia do estudantenas tcnicas e nos resultados emanados da teoriadas linguagens formais e dos autmatos.

3.1.2 Linguagens de Programao

Outro assunto, que se revela de imensa impor-tncia terica e prtica na vida do profissionalde computao, refere-se s linguagens de pro-gramao. Este artigo procura no se repor-tar s lingua-gens especficas propriamente ditas,atendo-se, por questes de escopo, somente ao as-pecto terico e conceitual do estudo de linguagensde programao em geral.

Os temas tericos mais relevantes, associados aoestudo das linguagens de programao, incluem:

O Clculo Lambda e a Teoria dos Combina-dores, teorias matemticas que fundamen-tam a programao funcional;

A Lgica de Floyd-Hoare, sistema formalusado para provar correo de programasimperativos. preciso lembrar que os mto-dos formais tm adquirido importncia cres-cente, permeando estudos srios em Enge-nharia de Software, e fundamentando mui-tas de suas prticas contemporneas;

A relativamente recente Teoria de Objetos,estabelecida por Abadi e Cardelli, que fun-

damenta toda a rea da programao ori-entada a objetos, atualmente muito dissemi-nada e em expanso;

As Semnticas Formais clssicas, voltadas especificao formal da interpretao daslingua-gens de programao: semntica ope-racional, semntica denotacional e semn-tica axiomtica.

O estudo terico das linguagens de programaovem recebendo contribuies de diversas origens, eem muitas direes, compreendendo assuntos fun-damentais, relativos composio, aos domnios,aos escopos, s ligaes, s transies, s regrasde inferncia associados aos programas que comelas podem ser desenvolvidos.

Razes no faltam para que seja reconhecida anecessidade de um conhecimento profundo da te-oria das linguagens de programao por parte dequalquer profissional que atue na rea de compu-tao:

A radicalizao da aplicao do conceito dereaproveitamento de cdigo tende, progres-siva e desnecessariamente, a levar os progra-madores a se afastarem das tarefas mais cri-ativas e originais da profisso, reduzindo aospoucos a nobre atividade de programao aum mero processo, cada vez mais mecnicoe menos intelectual, de seleo e reorganiza-o de componentes prfabricados.

As linguagens de programao modernas in-corporam inmeros conceitos no-triviais,como por exemplo, sofisticados sistemas detipos, e por isso mesmo seu uso competenteexige no apenas programadores com pr-tica, mas profissionais que apresentem ummnimo de intimidade com os conceitos efundamentos abstratos que lhes so subja-centes, para que possam utilizar essas lin-guagens em todos os seus recursos.

A necessidade crescente do desenvolvimentode sistemas de software de grande portetorna a especificao dos programas umatarefa cada vez mais difcil de realizar porparte de profissionais que no possuam umprofundo conhecimento e grande fluncia nautilizao do indispensvel ferramental con-ceitual exigido em tais projetos.

Para o desenvolvimento de softwares de se-gurana, nos quais os requisitos de qualidadese manifestam em nveis muito superioresao que se pratica usualmente no desenvol-vimento de programas convencionais, torna-se necessrio o uso de mtodos rigorosos deverificao e de validao formal, cuja apli-cao competente exige do profissional pro-fundos conhecimentos tericos, e no apenasuma habilidade puramente pragmtica.

Todo sistema de software que oferece a seususurios uma interface, atravs da qual se-jam feitas as comunicaes entre o programa


Vol. I

No. 1

15

e seu operador, requer algum tipo de proces-sador de linguagem, para cuja concepo eprojeto so necessrios profundos conheci-mentos e habilidades tericas.

Sistemas que se utilizam extensivamente deconceitos e conhecimentos tericos relativoss linguagens de programao esto presen-tes em toda parte, destacando-se os sistemasde comunicao, os sistemas de manipula-o simblica em geral, os processadores detexto, os sistemas operacionais e muitos ou-tros.

3.1.3 Cincia da Programao

Em seu prefcio ao livro de David Gries [40], oconceituado prof. Edsger W. Dijkstra manifestasua preocupao com a resistncia mental quesurge toda vez que se prope o uso de tcnicas dopensamento cientfico em uma nova rea de co-nhecimento, e recomenda um cuidado especial aose procurar convencer nefitos de que, embora primeira vista isso no seja evidente, aqueles in-teis formalismos abstratos no apenas so muitoteis, como tambm indispensveis.

Ainda nesse livro, o autor sugere que esse fen-meno assim ocorre devido a uma srie de razes:

Muitas vezes, pessoas que desconhecem o as-sunto costumam colocar objees injustifica-das a seu uso, em funo da dificuldade quesentem em compreender e conviver com no-taes matemticas, formalismos, tcnicasrigorosas e provas formais.

Alegando serem esses formalismos desneces-srios no dia-a-dia, argumentam que, emvista do demorado e oneroso preparo prvioexigido de um profissional para que estejaapto a us-los fluentemente, torna-se lcitoe prtico aceitar como satisfatria a quali-dade de programas pragmaticamente resul-tantes de desenvolvimentos artesanais, efe-tuados sem qualquer ajuda de mtodos ri-gorosos.

Outro argumento, infundado e recorrente,alega ser difcil e at invivel o empregode tcnicas rigorosas para desenvolver eimplementar programas de grande porte,cuja ocorrncia se mostra cada vez maisfreqente na prtica.

Por incrvel que parea, alguns profissionaisda rea alegam ser muito mais importanteque se disponha de uma especificao bas-tante precisa para um software a ser desen-volvido do que o correspondente programaestar, ele prprio, correto.

No extremo, outros alegam ainda que omundo real dispensa provas formais, e que,para todos os efeitos, na prtica suficienteapenas que o programa desenvolvido cum-pra sua tarefa.

Aludindo a essas posies, professadas por tan-tos profissionais, cita ainda o autor um trecho doDicionrio Oxford, que contrasta os conceitos decincia e de arte: aquela, fundamentada em prin-cpios e na constante utilizao dos mesmos; esta,sustentada pelo conhecimento de tradies e pelasdestrezas que se desenvolvem atravs da prtica.

Gries ainda afirma que a programao s po-der se converter em uma cincia atravs do cul-tivo de uma profunda maturidade matemtica,acompanhado de uma inteno real de empregaresse tipo de recurso na prtica do dia-a-dia.

3.1.4 Computabilidade

De forma anloga ao que se pode observar emoutras especialidades cientficas, uma grande va-riedade de importantes descobertas desta fasci-nante rea do conhecimento foi obtida teorica-mente, muito antes de sua prtica tornar-se tec-nologicamente vivel.

Infelizmente, tal fato induziu, e ainda hoje in-duz muitos, dissociao entre os fatos ligadosao estudo e ao uso dos computadores e os ensina-mentos proporcionados pela Teoria da Computa-bilidade.

Kfoury, Moll e Arbib [41] afirmam, no entanto,em seu livro que, por sua importncia, a Teoriada Computabilidade pode e deve ser consideradacomo sendo, apesar de tudo, o corao da Cinciada Computao.

Nessa linha, tem-se procurado determinar e de-senvolver um alicerce cientfico para o estudo deassuntos relacionados com a Informtica de modogeral, e em particular,de assuntos ligados ao pro-cessamento de dados atravs de algoritmos, aoprojeto de computadores digitais e ao projeto deprogramas desenvolvidos em linguagens de pro-gramao.

Desde meados do sculo passado, em diversosaspectos se tem observado um crescimento signifi-cativo do desenvolvimento da Computao, comopor exemplo: a sofisticao dos processos; o ba-rateamento dos componentes eletrnicos e o vio-lento aumento de sua capacidade e complexidade;a viabilizao de equipamentos eletrnicos muitopoderosos e a custo acessvel; os avanos nas me-todologias de programao; a drstica reduo dotempo necessrio para a obteno de programascomplexos e confiveis; o desenvolvimento de tc-nicas avanadas de especificao rigorosa de pro-gramas, processos e equipamentos.

Nesse contexto, a grande aplicabilidade da Teo-ria da Computabilidade pode ser facilmente iden-tificada, considerando-se que abrange, entre mui-tos outros assuntos:

Aspectos da sintaxe e da semntica delingua-gens de programao

Estudo da enumerao e da universalidadedas funes computveis


Vol. I

No. 1

16

Tcnicas de computabilidade e estado com-putvel de problemas

Metodologia de programao e prova de cor-reo de programas

Semntica denotacional

Programas recursivos

Regras de prova para propriedades dos pro-gramas

Auto-referncia em computabilidade e teo-rema da recurso

Conjuntos, conjuntos recursivos, conjun-tos recursivamente enumerveis, teorema deGdel

Mquina de Turing e formulaes alternati-vas da teoria da computabilidade.

Automatizao da prova de teoremas

Monty Newborn, em seu livro sobre provado-res automticos de teoremas [15], comenta que oscomputadores modernos tm evoludo muito ra-pidamente, ficando, cada vez mais, velozes, com-pactos e baratos, e j permitiram a construo deprogramas capazes de provar teoremas e at devencer campees mundiais de xadrez.

3.1.5 Complexidade computacional

Em artigo recentemente publicado [42], o concei-tuadssimo prof. Peter Denning, reportando-se aobservaes da realidade do dia-a-dia das prin-cipais aplicaes dos computadores, resume, empoucas palavras, a relevncia e o impacto que temo tema Complexidade Computacional sobre as ati-vidades do profissional da rea:

. . . over 3,000 common problems in sci-ence, engineer-ng, and business are sodifficult to solve that even the fastestsupercomputers would take centurieson simple versions.

(Peter J. Denning The profession of ITCommunications of the ACM, v.51, n.8, aug. 2008, p. 21)

De origem relativamente recente, datada da se-gunda metade da dcada de 1970,a Teoria daComplexidade Computacional tem recebido umaextraordinria ateno dos pesquisadores da Ci-ncia da Computao, em vista de sua grande im-portncia para a rea [2, 28].

O estudo da Complexidade Computacionalexige a compreenso de fenmenos no triviais, re-sultantes da interao da computao, da lgica edas aplicaes, para investigar as razes de algunsproblemas apresentarem solues computacionaisto onerosas.

Enquanto a Teoria da Computabilidade seocupa de determinar a possibilidade ou no deuma dada classe de problemas poder ser resolvidaalgoritmicamente, a complexidade computacional

se detm nos aspectos da viabilidade prtica daexecuo de algoritmos considerados adequadospara a tarefa.

Assim, os problemas computveis conseguemmotivar os estudiosos da Computabilidade noapenas por representarem curiosos desafios a se-rem resolvidos pelo programador, mas tambmpor constiturem por si prprios interessantes ob-jetos de estudo:

variados formalismos esto disponveis parasua modelagem e estudo

uma vez abstrados e formalizados, podemser analisados de maneira independente doparticular formalismo com o qual foram re-presentados

ao estudarem as propriedades dos proble-mas, os pesquisadores buscam para elessolues que preferencialmente sejam aomesmo tempo rpidas e compactas

para essas propostas de soluo, so conside-radas particularmente convenientes aquelasque apresentem requisitos polinomiais emsuas exigncias de rea de trabalho, e detempo de resposta

as solues mais adequadas na prtica soaquelas que apresentam, no espao e notem-po,comportamento polinomial de or-dem baixa (de preferncia, linear)

Muitos tpicos costumam ser considerados den-tro da temtica da Complexidade Computacional:

Algoritmos : modelos de computao co-nhecidos podem ser convertidos algoritmi-camente uns nos outros, com uma perdapolinomial de eficincia, exceto nos ca-sos no-determinsticos, de resposta expo-nencial. Assimetrias e no-determinismoscriam atraentes possibilidades para a classi-ficao de problemas quanto sua comple-xidade computacional.

Mquina de Turing: Computabilidade e De-

cidibilidade: de aparncia primeira vistaobscura, e dispondo de operaes bsicasmuito primitivas, a Mquina de Turingmostra-se capaz de representar algoritmossem significativa perda de eficincia, o quea tem consagrado como modelo de com-putao. Computacionalmente muito po-derosa, a Mquina de Turing capaz atmesmo de computar fatos no-triviais so-bre os algoritmos que representam.Todavia,h muitos problemas, ditos incomputveis,aos quais no existe qualquer possibilidadede se associar um algoritmo, ainda que ine-ficiente. Mquinas de Turing estritamenterepresentam, portanto, problemas compu-tveis. Estuda-se, para problemas compu-tveis, o fenmeno da decidibilidade: al-guns dos problemas computveis, ditos inde-cidveis, so representados por Mquinas de


Vol. I

No. 1

17

Turing que iniciam um processamento infi-nito em resposta a certos dados de entrada,enquanto os demais (problemas decidveis)garantidamente terminam o seu processa-mento qualquer que sejam os dados a elasfornecidos. Naturalmente, quando possvel,os ltimos so os preferidos, em termos pr-ticos.

Lgica booleana e Lgica de Primeira Or-dem: Estas formulaes permitem criar sis-temas de provas gerais e compreensveis, pormeio de comandos matemticos detalhadoscuja semntica associa cada sentena res-pectiva aplicao matemtica, permitindoexpressar fatos sobre computaes, o quepropicia o surgimento de problemas lgicosindecidveis.

O estabelecimento de Classes de Comple-xidade e sua inter-relao um assuntocomplexo e com inmeros pontos ainda emaberto, e isso tem motivado diversos traba-lhos na rea, e dado origem a muitos assun-tos de investigao, constituindo assim umtema bastante adequado para pesquisa atualem Cincia da Computao.

Redues e completude: O uso da lgicase revela muito interessante quando, atra-vs das tcnicas de reduo, se torna pos-svel estabelecer pontos em comum acercada dificuldade apresentada pelos problemaspertencentes a toda uma classe de comple-xidade. O estudo da NP-completude e detemas afins suscita importantes mtodos deanlise da Complexidade Computacional.

A dificuldade apresentada por determinadosproblemas pode demonstrar-se til e no in-desejvel como ocorre na maioria dos casosprticos. o que ocorre no estudo da Crip-tografia, no qual a complexidade dos algo-ritmos justamente aquilo que se busca ese necessita ter sob controle. Curiosamente,nessas exatas situaes em que a complexi-dade mais almejada, que se mostra maisdifcil obter a sua manifestao.

Computao paralela uma rea de inte-resse na qual se mostra mais necessrio emais rduo o estudo da complexidade com-putacional, especialmente quando tal es-tudo envolve simultaneamente numerososelementos como agentes paralelos.

4 Formao dos profissionais

da rea

Complementando as diversas aluses j feitas an-teriormente neste artigo, cabem algumas observa-es adicionais sobre a maneira como se formamou como deveriam ser formados os profissionaisque trabalham com Computao. Inicialmente,

transcreve-se a seguir um trecho de uma entre-vista [43] dada pelo conceituado prof. Denning:

The four core practices of compu-ting professions are programming, sys-tems, modeling, and innovating.To bea complete computing professional,you should know the principles and becompetent in the four practices.

(Entrevista do prof. Peter J. Denning Ubiquity)

Tem-se observado uma queda cada vez maispronunciada na qualidade da formao dos futu-ros profissionais da Computao no que tange concepo e implementao de programas, es-pecialmente os de porte menor.

A formao que eles recebem tem, nesses casos,negligenciado os essenciais aspectos microscpicosda problemtica dos projetos pequenos, em favorde uma forte polarizao para a gesto de grandesprojetos de software ou para o desenvolvimento degrandes sistemas.

Como resultado,nota-se,da parte do profissio-nal, uma perda sensvel de habilidade de pro-jeto de programas e algoritmos, uma dificuldadede compreenso de diversos assuntos ligados slingua-gens de programao e sua utilizaocomo instrumento para o desenvolvimento de pro-gramas. Observa-se ainda uma notria deficinciaem sua criatividade para a resoluo autnoma deproblemas, sem recorrerem a repositrios de pro-gramas pr-existentes.

Em relao a isso, j em 1981 o renomado DavidGries alertava [40] que, no mnimo, os programasgrandes podem ser vistos como uma coleo orga-nizada de programas menores, e que ningum sepode considerar especialista em produzir progra-mas grandes de qualidade enquanto no se provarum perito no desenvolvimento de bons programaspequenos.

Pode-se acrescentar que temerrio considerarcapacitado para gerir um dado projeto um profis-sional no dotado de um pleno domnio sobre to-dos os aspectos do mesmo, pois dificilmente costu-mam ser passivamente acatadas as diretrizes ema-nadas por gestores que no estejam aptos a de-monstrarem competncia nos assuntos a que serefere o projeto que pretendem conduzir.

Outro assunto de importncia para a presentereflexo, refere-se influncia da adoo de m-todos baseados em formulaes tericas na quali-dade dos produtos gerados pelos profissionais decomputao.

Alvo tradicional da pesquisa terica da com-putao,a resoluode problemas formulados demaneira precisa e rigorosa atravs de formalismosmatemticos bem estabelecidos mostra-se essen-cial para assegurar a construo de programas dealta qualidade.


Vol. I

No. 1

18

Tais formulaes constituem, na prtica, umgrande desafio, representando um importante au-xlio a atividades de projeto, e, por suas proprie-dades, podem ser exploradas no estabelecimentode mtodos de avaliao objetivos.

As mtricas assim desenvolvidas se empregamem instrumentos de avaliao que utilizam ndicesde mrito do software, o que proporciona formasobjetivas interessantes no apenas para avaliaesindividuais como tambm para comparaes entrediferentes softwares e para uso em sistemas de au-xlio tomada de decises.

As principais metas que se costuma perseguirquando se utilizam tais mtodos so: embasa-mento matemtico slido para os modelos de-senvolvidos; fundamentao cientfica para as de-cises tomadas; alta qualidade tcnico-cientficapara os produtos desenvolvidos; anteposio deum planejamento cientfico aplicao de prticastecnolgicas; expurgo conseqente da prtica dereapro-veitamento mope de peas pr-fabricadasno desenvolvi-mento de produtos de software dealta qualidade.

5 Concluso

Para atender s necessidades de uma poca emque se faz necessrio exigir do profissional umacapacitao cada vez melhor e mais ampla, pre-ciso um constante esforo de reciclagem e atuali-zao, tanto da parte dos profissionais como dasinstituies de ensino, para que seja possvel bemtrabalhar com os atuais sistemas computacionais,de complexidade e calibre sempre crescentes.

consenso ser fator distintivo dos mais ca-pacitados profissionais da Informtica o conheci-mento e domnio das teorias, abstraes e concei-tos que fundamentam suas atividades tcnicas, eessa distino se evidencia progressivamente me-dida que, simultaneamente, crescem as dimensesdos sistemas computacionais contemporneos.

Na rea acadmica, verifica-se um crescenteafastamento de metas entre disciplinas formati-vas e as de carter mais pragmtico, e isso outropreocupante motivo de ateno.

Cabe assim um alerta sobre a necessidade deresgate das importantes relaes entre elas exis-tentes, manifestas nas afinidades entre os modelosabstratos estudados na teoria e as atividades, m-todos e tcnicas prticas de programao que nelesdevem sempre se apoiar.

Flvio S. C. da Silva e Ana C. V. de Melo de-fendem em seu livro [17] a existncia de uma forteafinidade entre cada paradigma de programaoe algum dos modelos de computao existentes,sugerindo que para cada paradigma seja utilizadoo modelo de computao que lhe for mais expres-sivo. Assim, por exemplo, seriam usadas mqui-nas de Turing para o paradigma imperativo, en-

quanto Funes Recursivas e Clculo Lambda se-riam empregados para o paradigma funcional eoutros paradigmas declarativos.

Do ponto de vista pedaggico, para que possamser adequadamente fundamentadas as diferentesatividades ligadas programao, aconselham osautores que se d certa uniformidade nfase comque efetuado o estudo dos diferentes modelos decomputao disponveis.

Com a formao conceitual abrangente, assimproporcionada, os profissionais tero condies degerar solues simples e transparentes para seusproblemas, e como decorrncia natural, de pro-duzir para eles programas eficientes, elegantes ecorretos.

muito atual e oportuno meditar muito se-riamente sobre o cenrio cientfico e tecnolgicoem que trabalha o profissional da computao nosdias de hoje.

De um lado, possvel adquirir conhecimentospara formar conscincia da importncia que tmno dia-a-dia os temas difceis e abstratos de quetratam as disciplinas tericas da rea da Com-putao, e gratificante a certeza da utilidade deuma slida formao, resistente moda, ao tempoe tecnologia, que paire inabalvel acima de ten-dncias polticas e mercadolgicas.

De outro,a observao dos fatos do nosso mundotraz muitas incertezas sobre a maneira como serotratados esses assuntos no futuro.

angustiante a constatao de que a influnciado desconhecimento e da falta de preparo, aliadosao imediatismo, venha de h muito produzindoseus efeitos, especialmente atravs de decises to-madas com base em prioridades distorcidas, queacabam criando importantes barreiras a uma boaformao profissional.

Desse quadro, os maus efeitos que ainda no vi-eram tona seguramente se manifestaro em fu-turo prximo, quando, com certeza, uma reformapara a reverso dessa situao dever mostrar-semuito difcil, demorada e one-rosa, se no invivel.

Referindo-se em particular ao futuro das ativi-dades de programao, em entrevista concedida aEdward Feigenbaum [44], o respeitadssimo prof.Donald Knuth faz um grave alerta que convida reflexo, dada sua veracidade e as severas con-sequncias no mencionadas, dela decorrentes:

Im worried about the present stateof programming. Programmers noware supposed to mostly just use libra-ries. Programmers arent allowed todo their own thing from scratch any-more. Theyre supposed to assemblereusable code that somebody else haswritten. Theres a bunch of things onthe menu and you choose from theseand put them together. Wheres thefun in that? Wheres the beauty in


Vol. I

No. 1

19

that?

(Commun. of the ACM, v.51, n.8,aug. 2008, p. 35)

Fica ento esta pergunta para ser respondida:se as atuais tendncias continuarem como as ob-servamos hoje, com que dever parecer-se a nossaprofisso daqui a uns quinze ou vinte anos? Noapenas no que tange atividade da programao,mas igualmente a todas as outras especialidadesda rea da Computao. . .

Referncias

[1] D. I. A. Cohen, Introduction to ComputerTheory. Wiley, 1997. 2nd ed.

[2] H. R. Lewis and C. H. Papadimitriou, Ele-mentos da Teoria da Computao. Porto Ale-gre: Bookman, 2004.

[3] H. Barendregt, The Lambda Calculus: ItsSyntax and Semantics, volume 103 of Studies

in logic and the foundations of mathematics,vol. 155. 1984.

[4] R. Backhouse, Syntax of Programming Lan-guages. London: Prentice-Hall International,1979.

[5] J. J. Neto, Adaptive rule-driven devices general formulation and case study, inCIAA (B. W. Watson and D. Wood, eds.),vol. 2494 of Lecture Notes in Computer Sci-ence, pp. 234250, Springer, 2001.

[6] F. G. Pagan, Formal Specification of Pro-gramming Languages: A Panoramic Pri-

mer. Englewood Cliffs, New Jersey 07632.Prentice-Hall, Inc., 1981.

[7] K. Slonneger and B. Kurtz, Formal Syn-tax and Semantics of Programming Langua-

ges: A Laboratory Based Approach. Addison-Wesley, 1995.

[8] C. L. Lucchesi and et al, Aspectos Tericosda Computao. Impa CNPq, 1979.

[9] J. C. Martin, Introduction to Languages andthe Theory of Computation. New York:McGraw-Hill, 2003.

[10] M. Sipser, Introduo Teoria da Computa-o. Editora Thomson Learning, 2007.

[11] T. Scheurer, Foundations of computing: sys-tem development with set theory and logic.Addison-Wesley Longman Publishing Co.,Inc. Boston, MA, USA, 1994.

[12] M. Gordon, Programming Language Theoryand Its Implementation. Englewood Cliffs:Prentice-Hall, 1988.

[13] A. D. McGettrick, The Definition of Pro-gramming Languages. Cambridge UniversityPress, 1980.

[14] B. Meyer, Introduction to the Theory ofProgramming Languages. Englewood Cliffs:Prentice Hall, 1990.

[15] M. Newborn, Automated theorem proving:theory and practice. Springer Verlag, 2001.

[16] G. Winskel, The Formal Semantics of Pro-gramming Languages. Cambridge, Massachu-setts: MIT Press, 1993.

[17] F. S. C. Silva and A. C. V. Melo, ModelosClssicos de Computao. Thomson, 2006.

[18] R. W. Sebesta, Concepts of ProgrammingLanguages. Redwood City, Calif.: Wiley,2002.

[19] F. Beckman, Mathematical Foundations ofProgramming. Boston: Addison-Wesley,1980.

[20] J. Reynolds, Theories of programming lan-guages. Cambridge University Press, 1998.

[21] N. Greenlaw and H. Hoover, Fundamentals ofthe Theory of Computation. San Francisco:Morgan Kauffman, 1998.

[22] W. A. Wulf, M. Shaw, and P. N. Hilfinger,Fundamental Structures of Computer Sci-

ence. Reading, Massachusetts: Addison Wes-ley Publishing Company, 1981.

[23] E. R. Schneiderman, Matemtica Discreta uma introduo. Thomson, 2003.

[24] N. L. Biggs, Discrete Mathematics. OxfordScience Publications, Clarendon Press, revi-sed ed., 1989.

[25] A. G. Hamilton, Logic for mathematicians.1990. revised edition.

[26] E. Mendelson, Introduction to mathemati-cal logic, Van Nostrand-Rein-hold Co., NewYork, 1964.

[27] J. K. Truss, Discrete mathematics for com-puter scientists. Addison-Wesley, 1994.

[28] C. Papadimitriou and C. Papadimitriou,Computational complexity. Addison-WesleyReading, MA, 1994.

[29] J. Carroll and D. Long, Theory of Finite Au-tomata with an Introduction to Formal Lan-

guages. Prentice Hall, 1989.

[30] P. G. et al., Teora de autmatas y lenguajesformales. Mxico: Alpha mega, 2001.

[31] M. Harrison, Introduction to formal languagetheory. Addison-Wesley Longman PublishingCo., Inc. Boston, MA, USA, 1978.

[32] J. E. Hopcroft and J. D. Ullman, Introductionto Automata Theory, Languages and Compu-

tation. Reading, MA: Addison Wesley, 1979.

[33] J. E. Hopcroft, R. Motwani, and J. D. Ull-man, Introduction to Automata Theory, Lan-guages, and Computation. Addison Wesley,2001.


Vol. I

No. 1

20

[34] R. Muoz and L. Villodre, Lenguajes, gra-mticas y autmatas: Curso bsico. Mxico:Alpha mega, 2002.

[35] G. Revesz, Introduction to Formal LanguageTheory, 1983.

[36] A. Salomaa, Jewels of formal language the-ory. Computer Science Press, Incorporated,1981.

[37] P. Linz, An Introduction to Formal Langua-ges and Automata. Boston: Jones and Bar-tlett Publishers, 2006.

[38] J. E. Hopcroft and J. D. Ullman, Formallanguages and their relation to automata.Addison-Wesley Longman Publishing Co.,Inc. Boston, MA, USA, 1969.

[39] A. Aho, The Theory of Parsing, Translation,and Compiling. Englewood Cliffs: Prentice-Hall, 1972.

[40] D. Gries, The Science of Programming.Springer-Verlag, 1981.

[41] A. Kfoury, R. Moll, and M. Arbib, AProgramming Approach to Computability.Springer-Verlag, 1982.

[42] P. J. Denning, The profession of IT, Com-munications of the ACM, vol. 51, Aug. 2008.

[43] J. Gehl, Ubiquity Interview: GreatPrinciples of Computing. Ubiquity Edi-tor John Gehl interviews Peter J. Den-ning about the progress of the GreatPrinciples Project, Ubiquity An ACMIT Magazine and Forum, vol. 7, Novem-ber 2006. http://www.acm.org/ubiquity/

interviews/v8i22_denning.html last vi-sited 30th December 2007.

[44] E. Feigenbaum, Interview with DonaldKnuth: A lifes work interrupted, Commu-nications of the ACM, vol. 51, pp. 3135, aug2008.

Mini-currculo do autor: Joo Jos Neto graduado em Engenha-ria de Eletricidade (1971), mestre em Engenharia Eltrica (1975),doutor em Engenharia Eltrica (1980) e livre-docente (1993) pelaEscola Politcnica da Universidade de So Paulo. Atualmente, professor associado da Escola Politcnica da Universidade de SoPaulo e coordena o LTA Laboratrio de Linguagens e Tecnolo-gia Adaptativa do PCS Departamento de Engenharia de Com-putao e Sistemas Digitais da EPUSP. Tem experincia na reade Cincia da Computao, com nfase nos Fundamentos da En-genharia da Computao, atuando principalmente nos seguintestemas: dispositivos adaptativos, tecnologia adaptativa, autma-tos adaptativos,e em suas aplicaes Engenharia de Computa-o,particularmente em sistemas de tomada de deciso adapta-tiva, anlise e processamento de linguagens naturais, construode compiladores, robtica, ensino assistido por computador, mo-delagem de sistemas inteligentes, processos de aprendizagem au-tomtica e inferncias baseadas em tecnologia adaptativa.


Vol. I

No. 1

21

Documents

Teoria&MerTrabalho ATC