Great talk. Like most computer scientists, I was familiar with BDDs before, but I had never even heard of ZDDs - and yes, I didn't even know what it was prior to attending the talk. It turns out that ZDDs are a compact way to represent families of sets - for some problems more compact than any other technique, and there is a nice algebra with operations over them that can be implemented efficiently. The talk was easy to follow, full of examples, explanations, and even some good humor - but the best part is just how much Knuth himself is fascinated by the subject, which might very well be contagious in a good sense: he's made me a fan of ZDDs. When it becomes available online, I recommend watching this, and I'm planning on attending the lecture next year (and the following years). For now, most of the material covered in the talk is available as a preprint in Fascicle 1b of the Art of Computer Programming: Binary Decision Diagrams under the section "Zero-suppressed BDDs: A combinatorial alternative". Knuth said he will update this section soon and it will also appear in print.
No comments:
Post a Comment