Tags / Computer Science
Generalizing Dynamic Programming
- Using dynamic programming techniques to optimise general compute efficiencyDynamic programming is an approach to efficiently implementing certain classes of algorithms. As a feeble excuse for not noticing this earlier, the term is a little confusing: it isn’t about programming or about doing it dynamically! It was invented in the 1950s by Richard E. Bellman whilst working for RAND Corporation. Apparently he deliberately named it obtusely to avoid his work being considered research! I discovered this term recently when looking into existing research about algorithm optimisation and specifically why the systemic memoisation in NetKernel can optimise solutions to certain problems particularly well.
Travelling Salesman Problem
- Study of TSP running on NetKernel with cache replacing dynamic programmingThis paper offers an analysis of the application of NetKernel and Resource oriented computing to the well known Travelling Salesman Problem (TSP). This discussion ignores the many approximate approaches to solving this problem which are necessary for real-world problems of any significant complexity. The aim, however, is to show how ROC can automatically optimise a solution which it knows nothing about other than empirical data collected during execution. The algorithm structures the problem into sub-problems many of which overlap with each other - this occurrence is called overlapping subproblems.
History Of Gödel Numbering Part 3This is the third and final article in this series. Part 1 and part 2 describe how the concept of Godel numbers were first used to solidify the foundations of computing, then subsequently neglected by mainstream computing as it evolved until research at Hewlett Packard showed how the concept could lead to the caching of pure computation. In this final part I want to show the implications of this discovery for the future of IT.
History Of Gödel Numbering Part 2In the first post in this series I introduced Godel numbers and the important role they had in the foundations of computing. In this post I want to show how we took the concept to pioneer an approach to cache computation. A technique of identifying and eliminating redundant processing. Please entertain my third person prose. Picking up the trail In 1999 a small group of researchers in Hewlett Packard Labs were working in the domain of e-payment and digital commerce.
History Of Gödel Numbering Part 1At the break of the 20th century the prominent German mathematician, David Hilbert, posed 23 unsolved mathematical problems. He believed these problems were critical to progress in the field. Many, but not all of these problems have since been solved and some have given great philosophical insight. In particular his second problem asks for a proof that arithmetic is consistent, that is the arithmetic that we learn at school and forms the basis of much of the social and economic structure of our society.
Practical State Machines in NetKernel
Following up on my previous post, ROC Hockey, where I introduced our new implementation of Hierarchical State Machines on NetKernel I’ve decided to cover the topic of how they are actually used in practice in an ROC system.