Today I read on
Lipton's Blog
that Phillipe Flajolet passed away (1948-2011).
Flajolet worked in Analytic Combinatorics.
His book with Sedgewick on the field
(see this review)
practically defined the term Analytic Combinatorics.
Most of the math we use in Theoretical computer science is discrete math.
However, analytical mathematics is also useful and I wonder if its potential
has been fully tapped yet.
Here)
is an example: a paper by Flajolet that uses
Complex Analysis to show that certain context free languages are
inherently ambiguous.
I am teaching 30 students a course on Formal Language theory now and
I suspect that less than 3 know any complex analysis.
I suspect that in earlier times more would have. I do not miss those
times; however, it means that results like the one cited above cannot be taught.
Sorry for your loss, I will look up his work. Thinking about what you said about real analysis, it strikes me that US education offers things like probability, geometry, real analysis, discrete math, as "chunks," which means it's easy for students (intentionally or unintentionally) to just skip or miss them, leading to gaps in knowledge.
ReplyDeleteWe had a Ukrainian exchange student with us for a year, and one of the things I noticed about her education was that she had learned a little bit of everything every single year, which reminded me of my early education in French schools. It was very incremental and reinforcing. There was only one tiny thing she didn't know, but I was able to explain it to her in 15 minutes and she just got it. I mention this because students from places like Russia, Ukraine, Poland do so well in ACM competitions, and I wonder if this is part of the reason.
For the decades 1960-2000, Google ngrams shows a marked increase in usage of the word "naturality" ... most of which is associated to the mathematical literature.
ReplyDeleteThe widespread embrace naturality as a formalized idea is the hallmark of an new mathematical era in which combinatorics, algebra, and geometry are effectively merged.
Regrettably, this transformation has largely bypassed the engineering disciplines. One reason is that undergraduate curricula at four-year engineering colleges are full—there is simply no time for students learn (early and necessarily slowly) the basic ideas of mathematical naturality.
Another reason is that the notation of standard STEM textbooks was evolved during the 1920s-50s, and has remained (largely) static ever since. In particular (and speaking very broadly) undergraduate-level engineering textbooks that attempt to inculcate notions of mathematical naturality simply have not found broad popularity at engineering colleges.
The result is that pretty much all science-and-engineering students learn (for example) undergraduate classical/quantum mechanics on linear state-spaces, in a quaint (to mathematicians) 1920s-style notation in which operator relations like [A,B]=iC are expressed as algebraic identities. No hint is given of the equivalent geometric expression 〈dA,dB〉_ω=C, where {A,B,C} now are functions that satisfy a Lie algebra, d is the exterior derivative, and ω is a symplectic structure.
The geometric elements {A,B,C,d,ω} of the latter expression (and thus the algebraic/combinatoric Lie structure too) all have a natural pullback onto computational state-spaces (both classical and quantum) that dominate modern systems engineering ... and so it is regrettable that these natural mathematical concepts cannot be communicated to students trained in traditional STEM curricula. The simple point is that engineers who lack a mathematical understanding how their own simulation codes work, are not engineers at all!
Many great mathematicians have written textbooks that try to bridge this gap, but to date, none of these textbooks have found broad acceptance. I repose great hope, however, in Michael Spivak's newly announced Physics for Mathematicians: Mechanics I.
I haven't received my copy yet, but Spivak's introduction is very promising ... and funny too:
---------
THE HARDEST PART OF MECHANICS: THE FUNDAMENTALS
These lectures are based on a book that I am writing, or at least trying to write. For many years I have been saying that I would like to write a book (or series of books) called Physics for Mathematicians. Whenever I would tell people that, they would say, Oh good, you're going to explain quantum mechanics, or string theory, or something like that.
And I would say, Well that would be nice, but I can't begin to do that now; first I have to learn elementary physics, so the first thing I will be writing will be Mechanics for Mathematicians.
So then people would say, Ah, so you're going to be writing about symplectic structures, or something of that sort. And I would have to say, No, I'm not trying to write a book about mathematics for mathematicians, I'm trying to write a book about physics for mathematicians; of course, symplectic structures will eventually make an appearance, but the problem is that I could easily understand symplectic structures, it's elementary mechanics that I don't understand.
---------
We can all hope that Spivak's outreach efforts are fruitful, and that our STEM students will be exposed earlier and more creatively, to the powerful toolset of mathematical naturality—with its integrated combinatoric, algebraic, geometric, and (nowadays) informatic aspects—that mathematicians like Spivak have labored for the past half-century to create for us.
Flajolet's textbook on Analytic Combinatorics is a gem, and his papers are a delight. Though I did not know him personally, I'm sure he'll be missed sorely.
ReplyDeleteThe "little bit of everything" model can be very frustrating when you actually want to work on something, and get to know a lot about that, and other hand there are some other things that you don't want to spend your time on. It's adequate mostly for people that don't really care that much about what they are learning about, or like everything.
ReplyDeleteAlso, I would say the reason people from Eastern Europe do better in ACM competitions than the US is because they don't have so many interesting research/startup/internship opportunities. That often leaves academically disposed people with ACM competitions as the most interesting thing to do.
I once encountered Flajolet and Martin's paper about estimating the number of distinct elements in a data stream.
ReplyDeleteFYI, your post sort of implies that Flajolet's theory requires a deep understanding of complex math. That's not true.
ReplyDeleteFlajolet fathered Analytic Combinatorics, and calling the theory insightful is beyond euphemism. Understanding the proofs requires a serious mathematical bagage few students have. Applying the results, however, does not. Indeed you can take advantage of many of his results without knowing anything (or much) about complex analysis.