Computer science is no more about computers
than astronomy is about telescopes.
Ao tentar resolver o problema,
encontrei obstáculos dentro de obstáculos.
Por isso, adotei uma solução recursiva.
— aluno S.Y., 1998
To understand recursion,
we must first understand recursion.
— anônimo
Computers make it easier to do a lot of things,
but most of the things they make it easier to do
don't need to be done.
Efficiency is an ideological concept, not an economic concept.
— Noam Chomsky
Os logaritmos permanecem importantes
para muitas aplicações científicas e técnicas.
— pérola do jornal
O Estado de São Paulo
por volta de agosto de 1998
But you know what I don't understand?
To which David replies, Logarithms?
Then, reacting to Maddie's look: What? You understood those?
Moonlighting TV show
The greatest shortcoming of the human race is
our inability to understand the exponential function.
— Albert A. Bartlett,
Arithmetic, Population and Energy
,
YouTube video
For every polynomial algorithm you have,
I have an exponential algorithm that I would rather run.
— Alan Perlis
Achieving a polynomial-time solution to a nontrivial problem
is not something that depends on fine-grained implementation details;
rather, the difference between exponential and polynomial
is based on overcoming higher-level obstacles.
Once one has a [polynomial] algorithm to solve the problem, however,
it is often possible to achieve further improvements in runnning time
by being careful with the implementation details,
and sometimes by using more complex data structures.
— J. Kleinberg and E. Tardos,
Algorithms Design
Having a solid base of algorithmic knowledge and technique
is one characteristic that separates the truly skilled programmers
from the novices.
With modern computing technology,
you can accomplish some tasks without knowing much about algorithms,
but with a good background in algorithms, you can do much, much more.
— Cormen, Leiserson, Rivest, Stein,
Introduction to Algorithms
Ao verificar que um dado programa está muito lento,
uma pessoa prática normalmente pede uma máquina mais rápida a seu chefe.
[...]
Entretanto,
o ganho potencial que uma máquina mais rápida pode proporcionar
é tipicamente limitado por um fator de 10,
por razões técnicas ou econômicas.
Para obter um ganho maior de desempenho,
é preciso buscar melhores algoritmos.
Como veremos adiante,
um algoritmo rápido rodando em uma máquina lenta
sempre acaba vencendo
para instâncias grandes do problema.
Sempre.
(E as instâncias nem precisam ficar muito grandes
antes que o algoritmo rápido vença.)
— S. S. Skiena, The Algorithm Design Manual
A análise de algoritmos é uma disciplina de engenharia.
Um engenheiro civil, por exemplo,
tem métodos e técnicas para
prever o comportamento de uma ponte antes de construi-la.
Da mesma forma, um projetista de algoritmos
deve ser capaz de
prever o comportamento de um algoritmo antes
de implementá-lo.
— Anônimo
As 10 profissões que serão indispensáveis em 2014
sequer existiam em 2009.
Estamos preparando estudantes para profissoes que ainda não existem,
que usarão tecnologias que ainda não foram inventadas,
para resolver problemas que ainda nem sabemos que existem.
— Um professor
Metade do que se aprende no primeiro ano da faculdade
estará ultrapassado no terceiro ano.
Isto significa que
depois de sair da faculdade
todo profissional precisará continuar a estudar a se atualizar
o tempo todo, para sempre.
— Um professor
Dynamic programming is a fancy name for
[recursion]
with a table.
Instead of solving subproblems recursively,
solve them sequentially and store their solutions in a table.
The trick is to solve them in the right order
so that whenever the solution to a subproblem is needed,
it is already available in the table.
Dynamic programming is particularly useful on problems for which
divide-and-conquer appears to yield an exponential number of subproblems,
but there are really only a small number of subproblems
repeated exponentially often.
In this case, it makes sense to compute each solution the first time
and store it away in a table for later use,
instead of recomputing it recursively every time it is needed.
— Ian Parberry, Problems on Algorithms
A greedy algorithm starts with a solution to a very small subproblem
and augments it successively to a solution for the big problem.
The augmentation is done in a 'greedy' fashion, that is,
paying attention to short-term or local gain,
without regard to whether it will lead to a good long-term or global solution.
As in real life,
greedy algorithms sometimes lead to the best solution,
sometimes lead to pretty good solutions,
and sometimes lead to lousy solutions.
The trick is to determine when to be greedy.
[Most greedy algorithms are deceivingly simple.]
One thing you will notice about greedy algorithms is that they are
usually easy to design, easy to implement, easy to analyze,
and they are very fast,
but they are almost always difficult to prove correct.
— Ian Parberry, Problems on Algorithms