Computer-Science

Andrey Kolmogorov, Fred Hennie, Richard Stearns, and Walter Savitch are all famous separately; but they have something in common. Read on, and see. Today I wish to discuss some algorithmic tricks and show that they were initially used by complexity theorists, years before they were used by algorithm designers. To steal a phrase: it`s computational complexity all the way down. Well not exactly. The situation is slightly more complex”a bad pun. The complexity theorists often invented a concept and used it in a narrow way, while later it was rediscovered and made a general notion. ...

En cuanto a la relación de Chomsky con la informática proviene de sus enormes aportaciones a la Teoría de Autómatas y al estudio de los lenguajes formales, donde sus ideas se aplican a la perfección. Dichas aportaciones han resultado elementos indispensables para la construcción de compiladores y traductores que puedan servir de intérpretes válidos entre las órdenes que dan los seres humanos y su correcta recepción y aplicación por máquinas automáticas. Puede decirse que el papel desempeñado por Chomsky ha resultado crucial en este importante campo, pues fue imprescindible para dar el siguiente paso tras los primeros computadores, el ENIAC o el propio ACE de Turing, programados directamente en código binario, de forma que a mediados de 1954 ya influyó en la especificación del borrador The IBM Mathematical Formula Translating System, origen del lenguaje Fortran, y también John Backus adoptó sus reglas para describir la sintaxis de Algol, origen de la notación Backus-Naur. ...

Much of this data was entered by hand (obtained by contacting past conference organizers, retrieving cached conference websites, and searching CVs) so please email me if you notice any errors or omissions: bestpaper-AT-jeffhuang.com. I tried to collect best paper awards from the top-tier conferences in each area, but some conferences do not have such an award (e.g. SIGGRAPH, CAV). ”Distinguished paper award” and ”outstanding paper award” are included but not ”best student paper” (e.g. NIPS) or ”best 10-year old paper” (e.g. POPL) ...

A lot of programmers that make some of the coolest and most useful software today, such as many of the stuff we see on the Internet or use daily, don’t have a theoretical computer science background. They’re still pretty awesome and creative programmers and we thank them for what they build. However, theoretical computer science has its uses and applications and can turn out to be quite practical. In this article, targeted at programmers who know their art but who don’t have any theoretical computer science background, I will present one of the most pragmatic tools of computer science: Big O notation and algorithm complexity analysis. As someone who has worked both in a computer science academic setting and in building production-level software in the industry, this is the tool I have found to be one of the truly useful ones in practice, so I hope after reading this article you can apply it in your own code to make it better. After reading this post, you should be able to understand all the common terms computer scientists use such as ”big O”, ”asymptotic behavior” and ”worst-case analysis”. ...

This is a short documentary about the LEGO Turing Machine built by Jeroen van den Bos and Davy Landman at Centrum Wiskunde & Informatica (CWI), Amsterdam (Netherlands). They built it for CWI’s exposition ”Turings Erfenis” in honor of the centenary of Alan Turing’s birth on 23 June 1912. Alan Turing was a brilliant mathematician who helped define the theoretical model of the computer as we know it today. He was a visionary, one of the few people of his time who recognized the role the computer would play for humanity. The Turing Machine (1936) is an adequate model of a computer. It can do anything the computers of today or tomorrow can do. ...

I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible. My main motivation for doing this is to plan possible blog coverage of more theory venues – finding correspondents attending these events who would be willing to write either brief or in-depth blog entries about events they are attending. Beyond that, I hope a list like this would give everyone a better sense of the lay of the theory land. ...