Numero    

Veckobladet om forskning, undervisning och
administration, m.m.

Nummer 15 · 20 april 2000 · Årgång 30       

NADA

Disputation!

Lars Engebretsen disputerar tisdagen den 25 april klockan 10:00 i Kollegiesalen, Administrationsbyggnaden. Avhandlingen försvaras på engelska.

abstract cont.


Cas seminar!

A CAS seminar will take place Thursday 20 April @ 10.15 (room TBD!)

A Formal Framework for Robot Programming Antonio Carlos Dom’nguez Brito Universidad de Las Palmas de Gran Canaria Visitor at CAS since October 1999.

Abstract: Transfer and reuse of software designed specifically to control robotic systems is difficult, and often apparently imposible due to the diversity of hardware and systems software typically involved. Development from scratch is not an uncommon situation in many systems, even at the same laboratory. Other times an important software integration effort must be done to reutilize software. Last years a boosting of hardware features along with a decrease of prices has created a big demand for day-to-day robotics applications, and has evidenced the lack of standard tools to facilitate the design and implementation of robotics systems, and also to define software components for robotic systems. Reutilization and deployment of software for robotics systems should be as easy as buying electronic components to make your own electronic designs. A similar panorama can be found in business computing, where a software components industry is rising. A software framework with a formal definition of component is presented here. Such a framework models a component software, called DES, as a port automaton, so its external interaction can only be done through its ports. Once a DES has been implemented and tested, can be deployed and assembled in any robotic system. An assemblage of DESs, a compound DES, is used to combine DESs and/or another compound DESs. This combination is performed through a small set of process algebra operators. Like DESs, once they has been defined functionally, they also constitute reusable and deployable software components which can be used in new assemblages in the same and/or other systems. ---Henrik

Exjobbsseminarium i datalogi

Onsdagen den 26 april 2000 kl 15.15 i rum 4523

Charlotte Persson, F95
Ett förbättrat API för multimedia- och konferenstjänster
Arbetet är utfört vid British Telecom
Handledare: Henrik Eriksson och examinator: Stefan Arnborg
Opponent:
Joel Brynielsson, D95
Beslutsanalys i mikrovärldar Arbetet är utfört vid Nada
Handledare och examinator: Stefan Arnborg
Opponent: Anders Ingeborn


Hur blir vi bättre på att bedöma studenternas texter?

Kurs för Nadas lärare i att språkligt bedöma och diskutera rapporter.
Tid: 8 och 11 maj
00 kl 13 - 16

Våra studenter förväntas när de är klara på KTH att kunna falla in i ett professionellt skrivande. Hur förbereds de under tiden på Teknis? Vad lär vi dem? Och hur?
För att man ska utvecklas som skribent krävs träning både i att läsa och skriva texter. Man behöver också hand-ledning i form av t ex en lärare som ger relevant och utvecklande kritik på det man presterar. Det är vad den här tvådagarskursen går ut på.
Förhoppningsvis kan kursen, förutom att höja varje lärares kompetens, öppna för nya arbetsformer, där tid för till exempel textdiskussion och mer aktivt skrivande finns med som ett naturligt inslag. Den kan också öppna för en diskussion kring vilken slags kommunikatör en ingenjör är. Vad skrivs och för vem? Hur går det till?
Mitt syfte med kursen är att varje deltagare, mer aktivt ska kunna presentera krav och förväntningar på skriftliga redovisningar, kunna bedöma texterna utifrån genre, syfte och mottagaranpassning och kunna leverera sin bedömning (muntligt eller skriftligt) till studenterna, dels i form av en helhetsbedömning av texten, dels med löpande kommentarer på textens olika delar. Kursen tar två halvdagar i anspråk, och består av föreläsning, diskussion och kortare övningar i att bedöma texter och att formulera bedömningarna muntlig och skriftligt. Vi kommer också att ha tid för norm-diskussioner och diskussioner kring konkretaspråkfrågor.
Välkommen!

Stina Hållsten
stina@nada.kth.se

 

Cont. abstract

In this thesis we study optimization versions of NP-complete constraint satisfaction problems. An example of such a problem is the Maximum Satisfiability problem. An instance of this problem consists of clauses formed by Boolean variables and the goal is to find an assignment to the variables that satisfies as many clauses as possible. Since it is NP-complete to decide if all clauses are simultaneously satisfiable, the Maximum Satisfiability problem cannot be solved exactly in polynomial time unless P=NP. However, it may be possible to solve the problem approximately, in the sense that the number of satisfied clauses is at most some factor c from the optimum. Such an algorithm is called a c-approximation algorithm}. The foundation of the results presented in this thesis is the approximability of several constraint satisfaction problems. We provide both upper and lower bounds on the approximability. A proof of an upper bound is usually a polynomial time c-approximation algorithm for some c, while a proof of a lower bound usually shows that it is NP-hard to approximate the problem within some c. We also use hardness results for constraint satisfaction problems to prove hardness results for other optimization problems.
As for upper bounds, we use a combination of semidefinite programming and randomized rounding to construct a randomized 1.380-approximation algorithm for the Set Splitting and Not-All-Equal Satisfiability problems and a randomized (p-Theta(p^{-12}))-approximation algorithm for systems of linear equations mod p with at most two unknowns in each equation. Using randomized sampling, we construct a randomized polynomial time approx-imation scheme for dense instances of arbitrary k-ary constraint satisfaction problems. With a combination of PCP techniques and representation theory for Abelian groups, we prove that it is NP-hard to approximate a k-ary constraint satisfaction problem over sets of cardinality D within D^(k-2*sqrt(k+1)+1)-epsilon, for any constant epsilon > 0. As a comparison, the best currently known algorithm approximates the problem within D^(k-1).
Using a reduction from systems of linear equations mod 2 with exactly three occurrences of each variable, we prove that it is NP-hard to approximate the Asymmetric Traveling Salesman Problem with distances one and two within 2805/2804-epsilon for every constant epsilon > 0. For the special case where the distance function is constrained to be symmetric, we prove a lower bound of 5381/5380-epsilon for every constant epsilon > 0.
Finally, we improve earlier reductions and combine the improved reduction with a recent PCP characterization of NP to prove that the size of a maximum clique in a graph with n vertices cannot be approximated in polynomial time within n^(1-O(1/sqrt(log log n))) unless NP is a subset of ZPTIME(2^(O(log n(log log n)^(3/2)))).

Nyheter från Systemgruppen!

Vad kan passa bättre än ett påskägg eller två så här i påsktider?
Det finns en uppsjö med så kallade "easter eggs" - i betydelsen
en liten kul detalj som skaparna gömt i sitt verk" - bland
annat i datorer och datorprogram. Här är en länk till The Easter Egg Archive,
http://www.eeggs.com/


Glad Påsk önskar systemgruppen!


Johan Berglund
Systemgruppen, Nada

Numero är institutionstidningen vid Nada – institutionen för numerisk analys och datalogi, KTH. Numero utkommer normalt på fredags­förmiddagar under teminstid. Manus måste lämnas in före kl.16 på tisdagar.

Manus, tips, förslag och andra bidrag till Numero kan lämnas på något av följande sätt:

Bidrag för artiklar och notiser bör i största möjliga mån vara färdigformulerade och korrekturlästa.

Varje Numeronummer utkommer i två former:

Numeroredaktionen består av Rickard Buch. Ansvarig utgivare är Ingrid Melinder. Numeros innehåll uttrycker inte institutionens officiella ståndpunkt annat än då detta anges.

Ibland refereras till Numeropärmen. Det är en pärm som finns i bokhyllan i Nadas fikarum på plan 4, i vilken kompletterande information sätts in, försett med nummer på formen 99:NN-N.

Kalendarium

tor. 20 apr. kl. 10.15 CAS seminar (room TBD!) A Formal Framework for Robot Programming Antonio Carlos Dom’nguez Brito Universidad de Las Palmas de Gran Canaria .
tis. 25 april kl. 10.00 Lars Engebretsen disputerar. Plats: Kollegiesalen, Administrationsbyggnaden
ons. 26 april kl 15.15 Exjobbsseminarium i datalogi. Plats: rum 4523
Charlotte Persson och Joel Brynielsson.
Veckans Citat: "Obstacles: Are those frightful things you see when you take your eyes off the goal."

Hannah More

Glad Påsk!

   

Numeroredaktionen