gildot

Topo
Sobre
FAQ
Tópicos
Autores
Preferências
Artigos
Sondagens
Propor artigo


8/3
gildicas
9/30
jobs
10/9
perguntas
10/25
press

 
Dijkstra morreu...
Contribuído por npf em 12-08-02 8:23
do departamento
News WhiteShadow escreve "

Morreu no dia 6 de Agosto, vítima de cancro, Umas das maiores e mais importantes figuras da informática, Edsger Dijkstra, vencedor em 1972 do ACM Turing Award, o "Prémio Nobel" da informática.

Sem ele a ciência de computadores como a conhecemos hoje não seria possível. Foi responsável pela introdução de conceitos como a programação estruturada, semáforos, vectores e pilhas, pela criação de algoritmos como o da descoberta do menor caminho entre dois pontos (a que foi dado o seu nome) ou de problemas clássicos como o do jantar dos filósofos. Dijkstra foi um visionário que pensou na programação como uma ciência, como algo passível de ser estudado, estruturado e organizado.

Era também um excelente escritor e por isso a quantidade de papers que nos deixou é enorme e de inqustionável qualidade. Veja-se a título de exemplo o seu famoso paper Go To Statement Considered Harmful."

Tive a oportunidade e a honra de presencionar uma palestra dada por ele em 1995, em Eindhoven, durante as Olimpíadas Internacionais de Informática, onde pude confirmar a sua excelência científica. Usava sempre transparências vazias durante as suas apresentações e nunca (ou quase nunca) se enganava ao escrever código. Quando lhe perguntavam como conseguia fazer, dizia que aundo se enganava apagava tudo e começava de novo, do zero, para tentar atingir a perfeição.

Estamos por isso todos de luto, e foi com enorme tristeza que recebi a notícia. Fica aqui a minha (e de todos nós) sincera homenagem para o homem e o cientista.

Para finalizar, fica aqui um frase sua, que ilustra bem o seu espírito: "the question of whether computers can think is like the question of whether submarines can swim"

(Um artigo mais completo pode ser visto aqui.)

ADSL vs Cabo em Linux | Prémio "jornalismo à pedrada"  >

 

gildot Login
Login:

Password:

Referências
  • aqui
  • WhiteShadow
  • Go To Statement Considered Harmful
  • Mais acerca News
  • Também por npf
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    Engraçado... (Pontos:1)
    por fmimoso em 12-08-02 9:24 GMT (#1)
    (Utilizador Info) http://www.mobi.com.pt
    Confesso a minha ignorância como letrado em informática (tudo o que digo a seguir pode parecer e ser uma grande bacorada). Mas sou um pouco curioso. Fui tentar conhecer um pouco mais do senhor em questão e encontrei este pequeno texto (How do we tell truths that might hurt?) de onde saliento a seguinte afirmação:

    "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."

    Achei piada porque penso que hoje ainda se programa em grande quantidade em BASIC, aliás, parece-me que os "curiosos" (assim como eu) começam todos pelo BASIC... Ah, o artigo foi escrito em 1975!

    Re:Engraçado... (Pontos:3, Interessante)
    por cgd em 12-08-02 10:09 GMT (#2)
    (Utilizador Info)

    Todas as pessoas têm afirmações polémicas, e quanto mais conhecidas são, mais eco têm. Claro que essa afirmação está errada -- se alguém que se iniciou a programar em basic é impossível de se regenerar, então nem sequer vale a pena falar de reinserção social para aqueles rapazinhos que nascem em bairros degradados, ou tratamentos de desintoxicação para drogados, etc... ou seja, a capacidade de adaptação e correcção do ser humano subitamente deixa de existir.

    Outro texto polémico dele, foi a historieta dos GOTOs. Se é certo que de facto abriu portas para a programação estruturada (ou melhor: semi-estruturada, que é o que se encontra nas construções das linguagens de hoje em dia -- o facto de se poder fazer "return" em qualquer ponto de uma função, portanto, não apenas no fim, viola as regras de programação estruturada), foi de facto bom, mas a marginalização do goto foi errada. O goto é um bom instrumento, se correctamente usado. Pode tornar o código mais curto, mais rápido e mais legivel. A maior parte das pessoas que eu conheço, especialmente as que têm formação em informática (e não em electrónica ou em mecânica-- onde realmente se tem de fazer alguma coisa :-) ) simplesmente considera o goto mau, e faz disso religião.

    Ainda sobre isto, logo depois desse paper aparecer, o politicamente incorrecto Donal Knuth escreveu um texto chamado "Structured programming with GOTOs" (ou algo do estilo), e nomeadamente escreveu um algoritmo onde fazia criterioso uso do goto, e afirmou que esse algoritmo (implementado com GOTO's) era mais claro e seria cerca de 7 vezes mais eficiente, do que se fosse implementado puramente em programação estruturada. O Dijkstra terá dito "nesse caso justifica-se o uso do goto" :-)

    Enfim, ninguém é perfeito, tal como eu disse no mail que enviei aos meu colegas:


    Edsger Dijkstra, conhecido autor e investigador na área
    da computação e matemática, morreu anteontem, 6 de agosto.

    Alguns dos seus trabalhos incluiem a invenção dos semáforos
    P-V, algoritmos de shortest-path, introdução dos conceitos
    "vector" e "stack" na computação, etc... tambem escreveu
    o famoso artigo "goto statement considered harmful" (...ninguem
    é perfeito :-)

    noticia: http://www.cs.utexas.edu/users/UTCS/notices/dijkstra/ewdobit.html
    alguns dos seus textos: http://www.cs.utexas.edu/users/EWD/

    cya


    -- carlos

    Re:Engraçado... (Pontos:2, Informativo)
    por RaTao em 12-08-02 13:42 GMT (#5)
    (Utilizador Info)
    Sobre a questão dos GOTO's existe uma referencia interessante no sítio The linux-kernel mailing list FAQ.

    Alias, esta questão é parecida com a questão dos exit() a meio do algoritmo, que eu estimo muito =)

    Regards,
    Nuno Silva aka RaTao
    Re:Engraçado... (Pontos:3, Interessante)
    por BlueNote em 12-08-02 20:59 GMT (#6)
    (Utilizador Info)
    Por acaso, estou completamente de acordo com o espírito da citação que apresentas. Claro que não literalmente, todas as pessoas podem, se fizerem um esforço, reformular a forma de pensar e aprender novas linguagens, mas nesse artigo, no contexto da época, era importante salientar que se devia abandonar a introdução à programação pelo BASIC.

    O BASIC polui completamente a forma de pensar dos "programadores". É uma linguagem que desestrutura a capacidade de pensar a resolução de problemas e cria maus hábitos intelectuais -- "desarruma" os processos de resolução de problemas e isso é o inimigo número um de quem pensa um problema de engenharia.

    A forma de resolver problemas em BASIC é, aplicando uma expressão popular, resolver "à trolhex".

    É uma infelicidade que o VisualBASIC esteja a perpetuar as coisas à "trolhex", encorajando de forma serôdia a entropia e a resistência à mudança.

    Re:Engraçado... (Pontos:2, Esclarecedor)
    por lms em 14-08-02 12:31 GMT (#13)
    (Utilizador Info) http://homepage.esoterica.pt/~lms/
    Por acaso, a minha opinião é um pouco sui generis. Da minha experiência pessoal (e atenção que não vou sequer pretender ter a arrogância de assumir que conheço "massa crítica" suficiente de pessoas para poder justificar estatisticamente a minha opinião!), o que "polui" o trabalho de muitos programadores que conheço é a ausência de conhecimentos de estruturas de dados e de algoritmos - coisas que um programador auto-didacta só muito raramente (ou tardiamente) aprende.

    Aprender BASIC por si só não é uma "desvantagem". VisualBASIC e outros "dialectos" contemporâneos são linguagens estruturadas com uma rica variedade de estruturas. Mas o programador auto-didacta continua a usar strings e arrays para fazer praticamente tudo; e um "algoritmo" de pesquisa será sempre uma busca sequencial. Se for demasiado lenta, aumenta-se a velocidade de processamento do CPU.

    Não vou "criticar" esta forma de pensar e de programar do programador auto-didacta. Provavelmente ele está de acordo com o "espírito dos tempos". Quando aprendi a programar, os computadores eram tão lentos que - calculem! - usar linguagens interpretadas era anátema. O TurboBASIC da Borland era um sucesso vs. a versão do Bill Gates, não porque o Bill fosse um mau programador de compiladores :) mas porque o TurboBASIC podia compilar programas e aumentar assim exponencialmente a velocidade de processamento do software :) Mas essas coisas todas estão ultrapassadas. Quem é que se dá ao trabalho de pegar num livro do Knuth, do Dijkstra ou de outros luminários para consultar qual o algoritmo ou a estrutura de dados mais apropriada para resolver um problema? Não é mais fácil alocar um array de strings "algures" na memória de 1 GB e fazer uma pesquisa sequencial? Leva 3 segundos a programar em vez de estar a ver como é que se carregam os dados numa árvore binária e usar o algoritmo adequado...

    Quem é que consegue escrever um QuickSort em meia hora sem consultar um manual? Melhor ainda: quem é que se lembra da última vez em que consultou o manual do seu compilador favorito para ver se tinha uma library já com o QuickSort? E ainda mais: no último ano, quem é que teve a pachorra de desenvolver a sua própria library de QuickSort (porque a do GCC tinha demasiado overhead/era pouco ineficiente/tinha bugs/não era apropriada para o problema em questão?) Ya. Bons velhos programadores do final da década de oitenta...

    Por isso, sinceramente, mais vale que o pessoal aprenda depressa BASIC, pois mais de 90% do mercado português de software vai precisar de programadores de VisualBASIC para fazer manutenção a bugs de pacotes criados "à trolhex" (para usar a expressão do BlueNote) lá para meados da década de 90. E esqueçam os malvados pointers para structs de funções :) ou sistemas de cache usando B+-trees... isso pertence ao passado remoto. GOTOs rule forever!

    Luis Miguel Sequeira lms@esoterica.pt http://homepage.esoterica.pt/~lms/ "Brain not found; please replace user"

    Re:Engraçado... (Pontos:2)
    por cgd em 19-08-02 15:47 GMT (#14)
    (Utilizador Info)
    Quem é que consegue escrever um QuickSort em meia hora sem consultar um manual? Melhor ainda: quem é que se lembra da última vez em que consultou o manual do seu compilador favorito para ver se tinha uma library já com o QuickSort? E ainda mais: no último ano, quem é que teve a pachorra de desenvolver a sua própria library de QuickSort (porque a do GCC tinha demasiado overhead/era pouco ineficiente/tinha bugs/não era apropriada para o problema em questão?)

    1. quicksort em 17 minutos, contados, sem consultar nada, incluindo debugging, em python:


    def sort(a,i,j):
      t = (i+j)/2
      jj = j
      while i    if a[i] > a[t]:
          swap(a, i, j)
          j -= 1
        else :
          i += 1
      if j>0: sort(a, 0, j)
      if jj>i: sort(a, i, jj)
      return a

    def swap(a, i, j):
      temp = a[i]
      a[i] = a[j]
      a[j] = temp

    a = [1]; print sort(a, 0, len(a)-1)
    a = [1,2]; print sort(a, 0, len(a)-1)
    a = [1,2,3]; print sort(a, 0, len(a)-1)
    a = [1,2,3,4]; print sort(a, 0, len(a)-1)
    a = [1,2,3,4,5]; print sort(a, 0, len(a)-1)
    a = [6,5,4,3,2,1]; print sort(a, 0, len(a)-1)

    2. Não me lembro da ultima vez que fui ao manual: no C existe o qsort() na stdlib (sei de cor), no java, existe o sort na class Arrays, no python, todas as sequencias mutaveis têm o metodo sort... hmm.. ah! implementei uma serie de sort's (insertion, bubble, quick, heap, merge) em awk, mas ja la vao cerca de 4 anos...

    3. ja tive pachorra, há muitos anos, para tentar melhorar a qsort() da glibc. a que vem na libc era mais rápida. se quiseres implesmentar uma versao especializada (que saiba o tipo que vai ordenar de antemao e nao precise de usar ponteiros para funcs de comparacao), entao provavelmetne nem te interessa usar o quicksort,mas sim radix sorts ou count sorts (se aplicavel).

    nota: já agora, como curiosidade, o uso do goto permitia optimizar o algoritmo de cima ligeiramente, sem perder clareza de código. Como?
    nota2: a recursivade deste algoritmo pode-se evitar completamente, usando apenas uma pequena quantidade de memoria (constante). Como?

    O truque em programar bem, está em saber pensar bem. Um gajo que nao saiba estruturas de dados mas que saiba pensar, estrutura a funcionalidade de, digamos, procura em strings num modulo, quando descobrir (porque é esperto) uma maneira mais eficiente de fazer procuras, implementa o mesmo interface do seu modulo original com melhores algoritmos.

    O problema é sempre o mesmo: para ter coisas boas, são precisas pessoas boas, e nao existem muitas dessas disponíveis. Nao existem milagres, quem pensa que se programa melhor por deixar de usar goto's, ou por passar a usar OO, ou por ter aprendido com a linguagem XPTO em vez da XYZ, mais vale passar a escrever poesia (o meu problema, é que não sei escrever poemas).

    cya


    -- carlos

    ... (Pontos:2, Informativo)
    por Baía em 12-08-02 11:09 GMT (#3)
    (Utilizador Info)
    Só uma correcção: Algoritmo de Dijkstra "encontra" o caminho mais curto entre a fonte (única) de um grafo e todos os outros vértices (e não dois pontos), resolvendo assim o denominado single-source shortest-paths problem ou SSSP problem... unicamente para grafos em que todos os arcos possuem pesos não-negativos. Morreu um dos mais notáveis "cientistas informáticos" de todos os tempos!!
    Re:... (Pontos:1)
    por Baía em 13-08-02 8:47 GMT (#10)
    (Utilizador Info)
    1- Caso não tenhas reparado está entre "s 2- Nunca ouviste falar em "Ciências Informáticas" 3- Get a Life
    Re:... (Pontos:3, Informativo)
    por mlopes em 13-08-02 9:11 GMT (#11)
    (Utilizador Info)
    Informática
       substantivo feminino

    conjunto de ciência e técnica que tem por objecto o tratamento de dados relativos à informação por processos racionais e automáticos, que implicam a utilização de um computador e aparelhos complementares deste;

    (Do russo informatika, «id.», pelo fr. informatique, «id.»

    If you don't have time to do it right, where are you going to find the time to do it over?

    Re:... (Pontos:1)
    por Baía em 13-08-02 12:32 GMT (#12)
    (Utilizador Info)
    Click here e bica-me rijo...
    Outros pioneiros que faleceram (Pontos:2, Informativo)
    por samcruise em 12-08-02 23:19 GMT (#8)
    (Utilizador Info)
    Falai em mortes...

    Li hoje na Wired, sobre a morte de um dos inventores da programação orientada a objectos: Kristen Nygaard.

    Não me lembro de ouvir falar nele, mas Nygaard e o seu colega Ole-Johan Dahl receberam, em 2001, o AM Turing Award do ACM (que ainda não tem menção da morte, na sua página), pelo trabalho desenvolvido nos anos 50 e 60, quando inventaram a linguagem Simula, que acabaria por dar origem à Eiffel, SmallTalk, C++ e Java, entre outras.

    A página do ACM refere ainda outro falecimento, de John Cocke, também vencedor de um Alan M. Turing Award em 1987 (ver link anterior) pela sua contribuição para o design e teoria dos compiladores e, também, pela sua grande contribuição no design da arquitectura de processadores RISC.

    Temos de aceitar que nos próximos tempos irão desaparecer, com mais frequência, vários dos pioneiros da aventura informática.

    Cientista da Computação (Pontos:2)
    por racme em 13-08-02 0:30 GMT (#9)
    (Utilizador Info)
    Sem duvida um grande Homem Edsger Dijkstra de seu nome, Fisico e Matematico.
    Ou como muitos o consideraram Um dos pioneiros da "Ciência dos Computadores".

    "In 1955 I took the decision not to become a theoretical physicist, but a programmer instead"
    Quando em 1957 casou e se tentou registar junto das autoridades Holandeses como tendo Profissao "Programador Informatico", recusaram pois tal profissao nao nao existia.

    Notavel pelo seu trabalho na sincronização de processos onde o Problema dos Filosofos da "Dinning Table e dos "Chopsticks" tem grande relevancia, pra resolucao do acesso a recursos em processos concurrenciais.
    Retenho-o tambem na memoria pelo seu trabalho no Algoritmo "Shortes t-path". So mesmo um algoritmo tao simples e eficaz poderia ser tao util a um aluno de 2ano no seu exame de IA.

    Invariavelmente lembrado pela sua posição quanto ao uso do Goto e perseguição pela IBM quando esta tentava implementar o PL/I.
    Mas sera sempre recordado como um grande Pioneiro da Ciência dos Computadores

    . "Always design your programs as a member of a whole family of programs, including those that are likely to succeed it"

    . "Separate Concerns"

    . "A Programming Language is a tool that has profound influence on our thinking habits"

    . "The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague" (from 1972 Turing Award Lecture)

    . "Progress is possible only if we train ourselves to think about programs without thinking of them as pieces of executable code"

    . "Program testing can best show the presence of errors but never their absence"

    . "I mean, if 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself, "Dijkstra would not have liked this", well that would be enough immortality for me"


    ...no reino de Quelthalas...
    im awake, im awake!

     

     

    [ Topo | Sugerir artigo | Artigos anteriores | Sondagens passadas | FAQ | Editores | Preferências | Contacto ]