A comparative runtime analysis of heuristic algorithms for satisfiability problems

The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (k?3) is O(n(k−1)), and presents a k-SAT instance that has Θ(n(k−1)) expected runtime bound.     

Multi-frequency disturbance rejection via blending control technique for hard disk drives

This paper is concerned with the rejection of multiple narrowband disturbances in hard disk drives (HDDs). Inspired by a control blending idea, the multi-frequency disturbance rejection is formulated as a blending control problem. Each disturbance rejection is accomplished by using the H₂ optimal control method. Based on all H₂ optimal controllers, the blending technique is applied to yield a single controller which is capable of achieving rejection of all disturbances. Rejections of two and three disturbances for a 1.8-inch HDD VCM actuator are taken as application examples in the paper. Simulation and experimental results show that the ultimate controller results in a simultaneous attenuation of disturbances with frequencies higher or lower than the closed-loop system bandwidth. Moreover, the method turns out to be able to lift phase and thus prevent phase margin loss when it is used to deal with disturbances near bandwidth.     

On the decoding of binary cyclic codes with the Newton identities

We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases.Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas.Then we consider the so-called online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).     

Betriebsinformatik und Wirtschaftsinformatik als notwendige anwendungsbezogene Ergänzung einer allgemeinen Informatik – Vorschläge zur Verbesserung der akademischen Ausbildung auf dem Gebiet der automatisierten Datenverarbeitung in der Bundesrepublik Deutschland

Zusammenfassung  Nachdruck eines Aufsatzes aus elektronische datenverarbeitung 11(11)1969:544–548. This article is also available in English via and : Grochla E (2008) Corporate Information Systems Engineering and Business and Information Systems Engineering as a Necessary Application-Oriented Extension of General Computer Science – Proposals for Enhancing Academic Education in the Field of Automated Data Processing in the Federal Republic of Germany. Bus Inf Syst Eng. doi .

---

     

Tool support for learning Büchi automata and linear temporal logic

We introduce a graphical interactive tool, named GOAL, that can assist the user in understanding Büchi automata, linear temporal logic, and their relation. Büchi automata and linear temporal logic are closely related and have long served as fundamental building blocks of linear-time model checking. Understanding their relation is instrumental in discovering algorithmic solutions to model checking problems or simply in using those solutions, e.g., specifying a temporal property directly by an automaton rather than a temporal formula so that the property can be verified by an algorithm that operates on automata. One main function of the GOAL tool is translation of a temporal formula into an equivalent Büchi automaton that can be further manipulated visually. The user may edit the resulting automaton, attempting to optimize it, or simply run the automaton on some inputs to get a basic understanding of how it operates. GOAL includes a large number of translation algorithms, most of which support past temporal operators. With the option of viewing the intermediate steps of a translation, the user can quickly grasp how a translation algorithm works. The tool also provides various standard operations and tests on Büchi automata, in particular the equivalence test which is essential for checking if a hand-drawn automaton is correct in the sense that it is equivalent to some intended temporal formula or reference automaton. Several use cases are elaborated to show how these GOAL functions may be combined to facilitate the learning and teaching of Büchi automata and linear temporal logic. This work was partially supported by the National Science Council, Taiwan (R.O.C.) under grants NSC94-2213-E-002-089, NSC95-2221-E-002-127, NSC95-3114-P-001-001-Y02 (iCAST 2006), NSC96-3114-P-001-002-Y (iCAST 2007), and NSC97-2221-E-002-074-MY3.     

Integrationsdefizite des IT-Controllings

Zusammenfassung  Der Beitrag basiert auf der Annahme, dass das IT-Controlling in zweifacher Hinsicht unter einem Integrationsdefizit leidet. Dies gilt zum einen für die unbefriedigende Synchronisation der Forschung mit Entwicklungen in der Praxis, zum anderen für die unzureichende Verzahnung mit den Methoden der Wirtschaftsinformatik. Ausgehend von dieser Annahme untersucht der Beitrag die historische Entwicklung des IT-Controllings, um daraus Thesen zum Integrationsstand abzuleiten. Die Untersuchung kommt zu dem Ergebnis, dass Hinweise auf – nach wie vor – ungenutzte Integrationspotenziale vorliegen und identifiziert Potenziale einer weiter gehenden Integration. Aus der Analyse identifizierter Integrationspotenziale werden Anforderungen an eine methodenbezogene Integration abgeleitet und die Realisierung von Integrationspotenzialen an zwei Beispielen illustriert. This article is also available in English via and : Strecker S, Kargl H (2009) Integration Deficits of IT Controlling – Historical Background, Analysis of Integration Potentials and Method Integration. Bus Inf Syst Eng. doi: 10.1007/s12599-009-0053-4.     

Wirtschaftsinformatik zwischen Wissenschaft und Unternehmertum

One of the major success indicators for applied research sciences is the rate of transfer from research into practice. Only if concrete and economically successful products are derived from research results, such sciences can induce an impact. However, this process of innovation mandatorily needs entrepreneurship. Within the domain of business information systems, the two German enterprises SAP AG and IDS Scheer AG demonstrate that linking research and innovation is the key to lasting success in the information technology markets. German industry has significant disadvantages on the cost of human resources. Therefore it can be only successful with products that incorporate a high degree of innovation and that are consequently highly priced. But the invention of such products needs scientific research as a source of inspiration. Germany has a highly developed infrastructure of research facilities and organizations. However, they need to be better coordinated and aligned with business needs. Vice versa, enterprises need to actively approach the scientific community in order to clearly formulate their demand. Such a strategy needs changes on all sides. To achieve a change in the domain of science, it is necessary to change the profile of leading researchers, such as full professors. They should incorporate attributes of an entrepreneur and be profiled more as a research manager that tries to anticipate future needs and to develop its unit in terms of research subjects as well as personnel and financial resources. Consequently, the process of application, selection and review of leading researchers should be more oriented on processes that are common in enterprises. E. g. external head-hunters can be involved in the searching and assessing process in order to get the best qualified person for the research vacancy. Also enterprises need to change their attitude towards scientific research. In order to foster this process, executives could be invited to advisory and supervisory boards of research organisations. Furthermore, those executives must be proactively informed about the research activities and results in order to attract their interest and to show potentials for a transfer into products. There is still a long way in the hunt for innovation leadership and all these suggestions can only be a starting point.     

Optimierte Softwarelizenzierung – Kombinierte Lizenztypen im Lizenzportfolio

Although software licenses usually range among the most expensive items within the IT budget, they still lack the necessary attention by many companies. Therefore, most companies inadequately have implemented their software asset management neglecting further potential for cost reduction, which can be obtained by optimizing the use of different license types. This paper shows how possible savings can be realized by combining different types of licenses in a license portfolio. The model presented is based on the most common license types considering different user groups as well as their behavior. Additionally to cost risks, the risk of service quality is also taken into consideration. The following examples illustrate the model's high relevance and show how it can be can be applied in practice.     

基于GPRS—Internet的换热站无线远程监控系统

根据集中供热系统数据采集的特点,介绍了基于GPRS-Internet网络的换热站无线远程监控系统的组成以及换热站的自动控制.远程换热站采集现场的温度、流量、压力等数据,并通过GPRS-Internet网络传送到监控中心.监控中心实现了对整个供热系统进行远程自动化控制,解决了整个供热系统热工参数难以采集和热量分配不均等问题.运行结果表明,该系统稳定性好、调节精度高、操作方便,可以满足远程监控和长周期稳定运行等要求.