Background: Some sub-areas of computer science are concerned with developing new methods to solve practically motivated problems of certain shapes (determined by the sub-area). While obviously using real practical problem instances would be best, few papers in these areas actually use them, because (1) it is hard to obtain these problem instances (from industry) without first giving them a method to solve them (chicken-egg problem) and (2) many of these problem instances have too many intricacies that need to be handled at the same time, so that to make progress in the area, most papers pick one particular challenge, show the challenge by means of a convincing but synthetic example and propose a novel method that gives some insight into how to solve the challenge.
Doing research in this area requires to identify the shortcomings of current techniques and to derive convincing examples that actually demonstrate the shortcomings of previous approaches. Coming up with such examples requires to marry (1) the understanding of previous techniques, (2) the basic idea of what the practical problems are about, and (3) conciseness of the example, so that it can be used as running examples for thinking session at the whiteboard and as running examples in papers.
Question: Coming up with such examples requires creativity and can be seen as a puzzling problem, as the requirements are somewhat contradictory. Now there are some PhD students who will excel at such tasks and solve them without any guidance, and others will not know how to start, despite having a working knowledge of all the involved concepts. So what are suitable strategies to teach such puzzling skills to PhD students? I find it highly difficult to give help in such situations, as vague hints such as "think about what happens in this situation in that application" are often insufficient for a PhD student who is not good at puzzling, but hints such as "start by doing this and that" yield no learning effect since "this and that" will typically contain all ideas for one particular solution. The strategies should help students who are already familiar with all formal definitions and basic concepts, but never looked at them in combination yet.
Example: To clarify the question, let me give a (made up) example that is at least understandable to computer scientists. Assume that there is some reason to believe that when translating a deterministic automaton over finite words (DFA) to a digital circuit, we can make the circuit smaller whenever there are two states s1 and s2 in the automaton such that the language accepted when starting the automaton from s1 is the complement of the language accepted from s2. We also have a reason to believe that this is relevant for some application that involves all possible kinds of computations with binary-encoded strings. The tasks is to find a DFA that has two such states s1 and s2, whose implemented language can be easily explained in a sentence or two, for which the DFA is non-trivial (i.e., no state accepts no words or all words), and that makes at least a little bit of sense from the application point of view (here: arbitrary operations over binary strings)
Example solution to the example: One solution is to take a binary alphabet and to encode the language containing all strings that have an even number of 1s. The minimal automaton will have two states that naturally have this property. Many other solutions are possible, though.
Notes: I'm posting this here as the problem may not be exclusive to computer science. The example description above can very likely be improved. But let's assume that the task is already crystal clear to the PhD student, including the motivation.
No comments:
Post a Comment