favorite books

(Feb 2004, moved from my web page to this blog)

The other day I was browsing and found the web page of Peter Guttman. Apart from knowing a lot about PKI and practical security, I was inspired by his web page. If I was still leaving in Quebéc, I would feel a moral obligation to write my page in Portuguese, but this is Brazil and they love everything from Europe and the US. It would also be highly unpractical for many reasons: my written Portuguese still leave much to be desired (deixa muito a desejar) and a lot of the spontaneity would be lost. Also, maintaining a trilingual (English-Dutch-Portuguese) web page seems an exageration since those Brazilians interested in the subjects on this page can surely read English.

So my idea is to maintain a web page about the scientific me. For a brief look at the personal me and to understand the reason the irrational decision to move to Brazil please click here.

Favourite Books: as a true intellectual (my wife doesn´t think I should cakk myself one) I can reveal things about myself by telling about my favourite books:

• Dune, by Frank Herbert. Certainly the best SF book I read.
• Brazil, by Errol Lincoln Uys. The history of Brazil in a romanticized but very readable version
• The Brazilians, by Page. A fair description of contemporary Brazil
• The Art of Computer Programming Vol 2, by Knuth. All the stuff about random numbers, primality testing and factoring. Need I say more?
• The Handbook of Cryptography. A beauty, though too tough for most of my CS students. They even cite some of my papers.
• Cryptography and Network Security, by Stallings. Probably the best textbook for CS students, though I don't like the way he does the math. There is virtually no distinction between the 2nd and 3rd edition.
• Cryptographic Protocols, by me, yet to be written. There is no good book about protocols. All the books I've seen so far are either too shallow, or too theoretical. One day I hope to write the book that I believe is missing.
• Quantum Computation and Quantum Information, by Nielsen and Chuang. When I did my thesis it did not exist, now it is the book. They cite some of my work.
• The Selfish Gene, by Richard Dawkins. Convinced me that evolution makes more sense than religion as an explanation for why we are here. His other books are worth reading too.
• Guns, Germs and Steel, by Jared Diamond. Gives a reasonable explanation why Europe invaded the Americas and not the other way around
• The Prisoners Dilemma, by William Poundstone. The best explanation about Game Theory in daily life, told through a biography of John von Neumann.
• Non-zero sum. Somewhat along the same lines, but worth reading
• Pi in the sky, by John D. Barrow. Changed my way of thinking about mathematics
• Probability Theory, The Logic of Science,by E.T.Jaynes. This book changed completely my thinking about the interpretation of probability theory.
• Secret and Lies Digital Security in a Networked World, by Bruce Schneier. Even though I am not a fan of Applied Cryptography (even though he cites my work) I found this book inspiring
• Database Nation, by Simson Garfinkel. Made me stop using my credit card. For one day.

Favourite programming language: Python. (I worked in the corridor as Guido :-)

Favourite films: Apocalypse Now, North by North-West

• (09/Feb/2004 -- To be continued)

Custo transporte para Confins

*Confins define preços de transporte*

João Alberto Aguiar – Repórter

Os preços das quatro linhas de ônibus e táxis, brancos e azuis, que
levarão os passageiros de Belo Horizonte para Confins a partir do
próximo domingo, quando 120 vôos serão transferidos do Aeroporto da
Pampulha para o Aeroporto Internacional Tancredo Neves (Confins), já
estão definidos. De acordo com o diretor de Transporte Metropolitano do
Departamento de Estradas de Rodagem de Minas Gerais (DER/MG), Luiz
Otávio Valadares, a tarifa dos ônibus especiais, com saída do novo
terminal de embarque (Avenida Álvares Cabral, entre as ruas Espírito
Santo e Bahia), custará R$ 12,00.

Os veículos sairão em intervalos mínimos de cinco minutos e máximo de 15
minutos, dependendo dos horários de pico, indo direto para Confins.
Eventualmente, o período entre uma saída e outra poderá superar os 15
minutos, em horários com menor demanda. Outra linha é a do microônibus,
que também custará R$ 12,00. Nesse caso, porém, o usuário poderá optar
por ir do terminal até o Aeroporto da Pampulha, pagando R$ 6,00. Quem
estiver na Pampulha e quiser se deslocar para Confins também pagará R$ 6,00.
As outras duas opções de ônibus urbanos irão parar nos pontos ao longo
do trajeto. São eles os que saem da estação Rodoviária, mais
confortável, ao preço de R$ 5,25, e os que se dirigem para a cidade de
Confins. Antes de chegar ao município, o veículo fará uma parada no
Aeroporto de Confins. A condução sairá da Rua Caetés, esquina com
Olegário Maciel, na região central, ao custo de R$ 3,10. Segundo
Valadares, os ônibus especiais e os microônibus estão munidos com
sistema de segurança, como rastreamento.

O diretor também informou os preços dos táxis. O branco, partindo de
qualquer ponto da cidade, custará R$ 55,00. Atualmente, os valores giram
em torno de R$ 100,00, já que a tarifa de retorno para a capital está
embutida. A partir de domingo, ela deixa de existir. Apesar da afirmação
do diretor do DER/MG, o presidente do sindicato dos taxistas (Sincavir),
Dirceu Efigênio Reis, disse que a categoria já definiu, no sindicato,
que o preço a ser cobrado do passageiro é de R$ 60,00. "Falta apenas
definir amanhã (hoje) em reunião com o DER e a Infraero, na BHTrans", disse.
A tarifa do táxi azul, ou especial, que era de R$ 77,00, cairá para R$
60,00. Ao chegar ao Aeroporto de Confins, o taxista de Belo Horizonte
deverá passar por um local determinado, onde receberá um tíquete. Com
esse tíquete terá direito a entrar na fila e retornar para BH com outro
passageiro.

O limite de permanência na fila é de 200 táxis. Se já houver 200
veículos, o taxista deverá retornar sem passageiro, ou tentar uma vaga
depois. Ontem, depois de participar de um encontro no Aeroporto de
Confins, Valadares teria uma reunião com os prefeitos de Lagoa Santa e
Confins, onde o acordo seria formalizado. A reunião que definiu os
preços aconteceu na terça-feira à noite com representantes do DER/MG,
BHTrans e de taxistas de Belo Horizonte.

Os taxistas de Lagoa Santa e Confins vão direto para a fila. Eles
poderão retornar de BH para Confins com passageiros, através de um
sistema semelhante ao definido para os motoristas de táxi de BH. O
DER/MG informou ontem que o total de vagas na fila para os taxistas será
inferior ao que será disponibilizado para os taxistas da capital
mineira. Segundo o órgão, existem 130 táxis de Lagoa Santa e 40 de
Confins atuando no Aeroporto Internacional, além de outros 200 azuis, de
cooperativas.

Generating permutation

I just read in Skiena's book that it is possible to generate a random permutation with uniform distribution like this:

for i=1 to n do a[i]=n
for i=1 to n-1 do swap( a[i], a[Random(i, n)])

where Random(i, n) generates a uniform random integer in {i, ..., n}

Wow, that's surprisingly simple.
Obviously, the amount of randomness needed is correct:
n * (n-1) * ... * 2. But why the result is uniform isn't clear.

(the next day)
Maybe it is not so surprising at all:
I seem to temember from Lenstra's algebra classes that any permutation can be described as a sequence of n-1 swaps between 1 and an arbitrary element, 2 and an arbitrary element, etc. as long as you leave 1, 2 etc alone from then n. You probably prove this by recursion. The result then follows.


I love Skiena's book with a wealth of interesting algorithms;
I think I'm gonna buy it. See his site:
http://www.cs.sunysb.edu/~algorith/info/form.shtml
http://www.cs.sunysb.edu/~algorith/

BTW, the nerdiest site on the internet:
http://www.research.att.com/~njas/sequences/

Enc: [Sbc-l] programação matemática

Prezad*s,
Eu considero a situação muito mais grave. Além do fato que a maioria dos alunos em computação tem pouca noção de matemática, existe em Brasil um buracão entre a computação e a matemática em que quase ninguém está fazendo pesquisa.

Para clarificar: só matemático que virou pesquisador na informática teórica. Meu campo principal é a criptografia (protocolos zero-knowledge e quânticos), mas me interesso por muito mais assuntos, como
- teoria de informação (entropia de Shannon etc)
- teoria de complexidade (NP completeness, random complexity, reversible computing)
- complexidade de Kolmogorov
- teoria de informação quântica: (complexidade comunicação, complexidade de computação, códigos quânticos)

Trata-se de campos de pesquisa enormes em que centenas de pesquisadores no mundo inteiro atuam,
e que têm seus congressos anuais como STOC, FOCS, STACS, etc.
Até hoje (depois de quase 7 anos em Brasil) não encontrei nenhum pesquisador brasileiro fazendo pesquisa em um destas áreas.
(Se alguém conhece uma publicação brasileira em um deste congressos, gostaria de saber).

Existem mais áreas teóricas como
- teoria de computabilidade
- análise algoritmos
- teoria de códigos (para correção de erros)
- inteligência artificial teórica
- geometria computacional
- pesquisa operacional
- semântica de linguagem de operação
- análise formal de protocolos
- etc
Eu diria que estas áreas tinham menos dificuldades de ser reconhecidas,
ou porque sua utilidade era obvia,
ou por se tratar de áreas muito relacionadas à lógica.
Mas o que chama a atenção é que tudo que é relacionado
à teoria de complexidade aparentemente não chegou em Brasil.

Em muitos institutos que eu conheço no mundo, os departamentos de matemática e de computação formam um contínuo:
- O MIT já reconheceu a importância deste campo nos anos 80, e há no mínimo três professores de CS e no mínimo dois professores da matemática fazendo pesquisa nestas áreas
http://theory.lcs.mit.edu/people.html:
(pensei especificamente em Rivest, Goldwasser, Micali, Sipser e Spielman.
Pelo que saiba, Sipser e Spielman são de matemática, o primeiro
orientador do segundo. O trabalho dos outros membros do grupo eu não conheço)
- Na Universidade de Montreal (onde fiz meu doutorado) há 6 professores
para informática teórica:
http://www.iro.umontreal.ca/labs/theorique/
- O equivalente holandês do IMPA mudou de nome para
"Centrum voor Wiskunde [=matemática] en Informática" em 1980 (!!!)
onde há vários grupos fazendo pesquisa nestas áreas:
http://www.cwi.nl
- No Dinamarca tem o BRICS: www.brics.dk
E há muito mais grupos espalhado no mundo.

Em contrasto, no Brasil tem nada. A situação da UFMG me parece típico para o Brasil inteiro:
Existe um hiato entre o departamento de Computação e o de Matemática.
Exagerando um pouco: o informático quer saber nada de teoria mas
quer programar em Java (nada contra Java, é uma linguagem bonita).
E o matemático gosta de assuntos puros, como hiperquadrados não Riemannianos
["non-Riemannian hypersquares"; veja The mathematical experience, Davis & Hersch, pg 34]
e tem desdém para tudo que parece aplicado, como assuntos de computação
(passei anos entre matemáticos; sei como eles pensam).
Ambos acham, raciocinando dentro de seu sistema de pensamento fechado,
que informática teórica seja irrelevante. O resultado é previsível:
informática teórica não existe em Brasil, e isto se reflete no ensino.

A única universidade com um Departamento de Informática Teórica
é a UFRGS, pelo que achei via google:
http://www.inf.ufrgs.br/~hgmc/teorica/paginas/tecomp.html

Nem é um assunto simples: o que é mais útil para um bacharelado em
informática? Saber SQL e Java, ou saber qual é a definição de um bit
segundo a definição de Shannon, conhecer o problema da parada da Máquina de Turing?

Na Universidade de Montreal eu era monitor da disciplina
Informática teórica. Era uma disciplina temida porque era difícil,
e quem tomou bomba duas vezes tinha que sair do programa.
A situação em Brasil está melhorando um pouco por causa da criptografia,
um assunto cada vez mais importante por ser relacionado à segurança de computador.
Hoje há grupos fortes na Unicamp e USP (o LabSEC da UFSC é mais aplicado).

Me parece que a melhor estratégia seja de tentar convencer os matemáticos
que informática teórica é um campo interessante *e* relevante, o que não é
verdade para assuntos puros como hiperquadrados não Riemannianos
ou topologia (é um trauma minha -- tinha nota baixa para esta matéria).
Ao mesmo tempo, acredito que este país precise de um instituto para informática
teórica, parecido com o IMPA.

Quanto ao ensino na computação:
não sei se é verdade, mas tenho a impressão que muito programas ensinam
muito cálculo, tempo que na minha opinião poderia ser melhor aproveitado
ensinando matemática discreta. Há até uma explicação para isto:
muitas vezes quem define o programa são os matemáticos, que por força de tradição
dão ênfase na matemática contínua, enquanto para informática a matemática
discreta é muito mais relevante. Até me interessaria aprofundar este assunto um pouco.

Jerô

=================
Jeroen van de Graaf
jvdg@lcc.ufmg.br
LCC/Cenapad---UFMG
Prédio ICEX, sala 2040
(31) 3499 4909
----- Repassado por Jeroen Antonius Maria van de Graaf/LCC/ATI/REITORIA/UFMG em 06/03/05 22:04 -----
"Manuel ljfas"
Enviado Por: sbc-l-bounces@inf.ufrgs.br
03/03/05 09:45

Para
sbc-l@inf.ufrgs.br
cc
Assunto
Re: [Sbc-l] programação matemática







Caros
Eu já presenciei profissionais da computação desenvolvendo algoritmos ridículos, ineficientes e ilegíveis justamente por não saber programação matemática. Isso é consequência da má formação.
A programação matemática (programação linear, prog. Inteira, Prog. Dinâmica, Pesquisa Opercional, etc) faz uma ponte entre a teoria puramente matemática e a prática de projeto de algoritmos. Eu entendo que programação matemática está muito mais próxima da computação do que da matemática. Afinal, a essência dessa disciplina são os algoritmos e a modelagem de problemas.
Esse problema tem um efeito cascata. A ausência dessas disciplina geram profissionais que um dia podem se tornar professor. Na condição de professor, se ele não for trabalhar com disciplinas básicas (projeto de algoritmos, análise de algoritmos, teoria da computação, etc.) ele talvez não descubra a real necessidade das disciplinas que ele não teve. Mas ele descobre que tecnologias são interessantes porque está na mídia. Além disso, ele não se dá conta que tecnologia é igual moda, um dia é uma coisa, outro dia é outra. E assim, as diciplinas que dão base para a CIÊNCIA (da computação) vão sendo deixadas de lado.
Esse problema nós observamos também nos eventos da SBC. Se hoje eu desenvolver um algoritmo revolucionário para algum problema eu não consigo publicar no evento da SBC. Basta observar os worshops e seções do congresso da SBC deste ano. Não seria possível encaixar o artigo. Isso não é curioso?
No entanto, é possível publicar nos eventos tais como: Pesquisa Operacional, Matemática Computacional, etc. Nesses eventos nós encontramos muitas pesquisas sobre algoritmos. Isso também não é de interesse da computação? Algoritmos não é de interesse da computação?
Esse assunto realmente deveria ser discutido pela SBC.
Manuel









----- Original Message -----
From: campani@inf.ufrgs.br
To: sbc-l@inf.ufrgs.br
Subject: [Sbc-l] programação matemática
Date: Wed, 2 Mar 2005 11:03:23 -0300
>
> Caros e Caro Manuel:
>
> Oportuna a tua mensagem. Vejo nos últimos anos uma preocupação
> maior, no Brasil,
> com o tempo que o aluno permanece no curso superior que com sua efetiva
> formação. Isto ocorre normalmente pelo sacrifício de certas disciplinas em seu
> currículo, particularmente as mais teóricas. No entanto, são estas exatamente
> aquelas que lhe darão uma formação consistente. É o caso de programação
> matemática, importante disciplina que pode fornecer aos futuros bachareis um
> ferramental matemático precioso. Acho que a SBC deveria fazer uma discussão
> neste sentido. Uma outra disciplina, que me parece é apresentada aos alunos
> apenas na UFRGS e na PUC-Rio, é teoria das categorias, que é uma
> ferramenta bem
> interessante para ciência da computação, e cuja adoção nos cursos poderia
> incrementar a qualidade do profissional formado.
>
> Um abraço,
>
> Campani
>
> -----
>
> Colegas
>
> Costantemente nos deparamos com algoritmos concebidos a partir de
> formulações de programação matemática. Na literatura encontramos
> alguns desses algoritmos clássicos e muito importantes, tais como:
> algoritmo Húngaro para o problema de atribuição, algoritmo de
> Out-of-Kilter para Fluxo de Custo Mínimo, algoritmo de Edmond para
> Emparelhamento de Grafo não Bipartido. Alguns desses algoritmos
> baseiam-se em variáveis primais e/ou duais oriundas de formulações
> de programação matemática.
>
> Estes exemplos de algoritmos demostram a importância da programação
> matemática na concepção de algoritmos robustos e eficientes. Apesar
> disso, são POUCOS CURSOS de Ciência da Computação, tais como da
> UNICAMP e USP, que contêm disciplinas de programação matemática em
> sua grade curricular. Pelo menos é isso que eu tenho observado. Por
> que isso ocorre se algoritmos é a base da computação?
>
> Manuel
>
> ----------------------------------------------------------------
> This message was sent using IMP, the Internet Messaging Program.
> _______________________________________________
> Sbc-l mailing list
> Sbc-l@inf.ufrgs.br
> https://listas.inf.ufrgs.br/mailman/listinfo/sbc-l
--
___________________________________________________________
Sign-up for Ads Free at Mail.com
http://promo.mail.com/adsfreejump.htm

_______________________________________________
Sbc-l mailing list
Sbc-l@inf.ufrgs.br
https://listas.inf.ufrgs.br/mailman/listinfo/sbc-l

FHC X Lula

What I find striking is this:
3,4,5 years ago people would says many things about FH, like
"FH is killing public education"
("FH está acabando com o ensino público").

But today there are no similar phrases about Lula.
People will say
"O PT está acabando com o ensino público" ou
"O governo está acabando com o ensino público"
but never "Lula está acabando com o ensino público".

With FH everybody knew who was in power,
but with Lula nobody seems to know .......