Numero 17

fredag 15 maj 1998, årgång 28

Veckoblad om forskning, undervisning och administration m.m.
NADA - Institutionen för numerisk analys och datalogi, KTH


Aktuellt kalendarium (inte kalendariet som hör specifikt till denna Numeroutgåva).

Numero utkommer inte nästa vecka

Nästa nummer av Numero utkommer den 29 maj.


PDC-seminarium: Is the atmospheric energy spectrum due to two-dimensional turbulence?

Erik Lindborg, Institutionen för mekanik, KTH, håller PDC-seminarium under ovanstående rubrik tisdagen den 26 maj kl. 15.15 i seminarierum 1537 (Lindstedtsv. 3, plan 5).


This talk will consist of two parts: First, a theoretical part in which some basic kinematic and dynamic relations are derived for the second and third order structure functions of two-dimensional turbulence, secondly, a presentation of structure function calculations based on wind data from 5745 commercial airplane flights, reported in the MOZAIC data set. The calculated structure functions will be compared with the results from the theoretical analysis. Due to the large amount of data, the new results are very clean. On the basis of these results, the question asked in the title, will be given a preliminary answer.

Erik Aurell

Tack så mycket!

Ett stort tack för uppvaktningen i samband med min introduktion i tisdags. Orkideerna är väldigt vackra och även trollspöet har kommit till användning redan. Så fort jag viftade med det så damp det ned en färdig lic-avhandling (från Py) på posten!

Kerstin S.E.


Institutionen för datalogi och numerisk analys (DNA), Lunds Universitet - Lunds Tekniska Högskola och Avdelningen för datalogi, Institutionen för systemteknik, Luleå Tekniska Universitet samarrangerar programmeringstävlingen "SVENSKT MÄSTERSKAP inom ACM International Collegiate Programming Contest".

Tävlingen är en lagtävling (maximalt 3 personer och en dator per lag) där man under fem timmar, med hjälp av Pascal, C eller C++, försöker lösa så många problem som möjligt (av 6-8).

Tävlingen går parallellt i Lund och Luleå lördagen den 26 september kl. 10-15 och är öppen för studenter från hela Sverige. Anmälan är öppen mellan 18 augusti och 18 september. Numeropärmen 98.068

I korthet

Stipendier: Stipendier för utlandspraktik eller examensarbete vid någon av de fem stora europeiska forskningsanläggningarna CERN, ESO, ESRF, EMBL eller JET. Ansökan skall vara NFR tillhanda senast den 2 juni. Anmälningsblankett finns hos Karin Molin. Numeropärmen 98.064

Information: I vetenskapens lustgård. Månadsblad maj kulturhuvudstadsåret 1998. Numeropärmen 98.065

Seminarium: Efficient Data Structures with Bit Fiddling. Stefan Nilsson, Tekniska högskolan, Helsingfors. 18 maj kl. 15.30 i konferensrummet "gamla telegrafen", Electrum 5:e våningen, ingång vid B-hissen, Kista. SICS och KTH/IT. Numeropärmen 98.066

Konferens: Workshop on Formal Design of Safety Critical Embedded Systems. 15-17 mars 1999 i München.'99.html

Seminarium: Seminarium om aktuell forskning vid IIASA (International Institute for Applied Systems Analysis, Laxenburg, Österrike). "Environmentally Compatible Energy Strategies" och "Modeling Land-Use and Land-Cover Changes". 27 maj kl. 9.15-12.15 i sal D3, Lindstedtsvägen 5. Infrastruktur och Samhällsplanering och FRN. Numeropärmen 98.067

Nummeseminarium: Finite element methods for Maxwell's equations

Peter Hansbo, NADA, håller seminarium i numerisk analys under ovanstående rubrik onsdagen den 27 maj kl. 13.15 i seminarierum 1537 (Lindstedtsv. 3, plan 5).

Björn Sjögreen

Disputation: Neural Control of Locomotion in Biological and Robotic Systems

Tom Wadden, SANS, disputerar under ovanstående rubrik fredagen den 29 maj kl. 10.15 i sal D2 (Lindstedtsv. 5).


The work presented in this thesis deals with the construction of biologically inspired control systems for locomotion. The information learned from these studies should be of interest to both engineers and biologists. Engineers looking for inspiration from biological systems may find novel ways to control mechanical devices, while biologists can see the results of embedding their theorized control laws in simulated neuro-mechanical systems.

The main contributions are:

Licentiatseminarium: Approximating generalizations of Max Cut

Lars Engebretsen, TCS, håller licentiatseminarium under ovanstående rubrik tisdagen den 26 maj kl. 10.00 i sal E2 (Osquars backe 2, plan 3).


We study the approximability of different generalizations of the Max Cut problem. First, we show that Max Set Splitting and Max Not All Equal Sat are both approximable within 1.380 in probabilistic polynomial time. The algorithm uses standard semidefinite relaxations, combined with a probabilistic post-processing step. Then, we focus on systems of linear equations modulo p with exactly k unknowns in each equations. The naive randomized algorithm, which guesses a solution uniformly at random from the solution space, has performance ratio p for this problem. For k >= 3, it has been shown by Håstad that it is, for all epsilon > 0, NP-hard to approximate the optimum within p - epsilon. In contrast to this remarkable result, we show that, for the case when k = 2, it is possible to use a semidefinite relaxation combined with randomized rounding to obtain a probabilistic polynomial time algorithm with performance ratio p - kappa(p), where kappa(p) > 0 for all p. Finally, we show that it is possible to construct a randomized polynomial time approximation scheme for instances where the number of equations is Theta(n^k), where n is the number of variables in the instance.

Licentiatseminarium: S-notation - a computer based method for studying and representing text composition

Py Kollberg, IPLab, håller licentiatseminarium under ovanstående rubrik onsdagen den 3 juni kl. 14.00 i sal E32 (Osquars backe 2, plan 3).


This thesis presents a method for studying revisions in computer based writing. The kernel of the method is a representation of a writing session based on the finished text. In the text, all revisions that the writer made are visible at the position they were performed during writing in a representation that also covers their order and internal structure. With this method, the word processor registers all the writer's actions during the writing session in a keystroke record. With the log-file as an input, the S-notation for the writing session can be generated by a program for revision analysis. In this program (Trace-it) the user can work interactively with the notation, replay the writing session, and make a range of automatic analyses. In this way, it is possible to follow how a writer worked with the text during its composition. Previous methods have not allowed these possibilities for representing and studying writing. In S-notation, the writing session is represented only on the basis of the structure of the writer's overt revisions. It leaves interpretations at higher levels, where the writer's intentions with the revisions are concerned, to a human interpreter. The S-notation supports the user during the interpretation stage in finding the parts of a writing session that could be worthwhile to investigate further. The thesis discusses problems in the description of computer based writing, and problems in finding relevant and useful levels of the descriptions. The S-notation has mainly been used within writing research and education, but it can be applied to other kinds of text editing as well, such as programming. It can also be used as a history tool by writers. The S-notation representation is independent of the word processor that the writer used to write the text. Thus the method can be used to study the effects that different properties of the writing medium might have on writing.

CAS-seminarium: Generic Shape Indexing and Matching for 2-D Object Recognition

Sven Dickinson, Department of Computer Science and Center for Cognitive Science, Rutgers University, håller CAS-seminarium under ovanstående rubrik måndagen den 25 maj kl. 15.30 i sal BB2 (Fiskartorpsvägen 15A).


We have been developing a theory for the generic representation of 2-D shape, in which structural descriptions are derived from the shocks (singularities) of a curve evolution process acting on a silhouette. We now apply the theory to the problems of shape matching and indexing. The shocks are organized into a directed, acyclic shock graph which, in turn, can be reduced to a unique rooted shock tree whose levels are ordered by significance. We first introduce a novel tree indexing algorithm based on an eigenvalue characterization of a shock tree's topological structure. This topological signature, in the form of a vector, is computed at each node of a query tree and used to "vote" for objects having similar local topological structure. From the resulting set of model shock tree candidates, this same topological signature is exploited in a shock tree matching (verification) algorithm that factors in the geometry of the shock tree's nodes. The algorithm computes the distance between two shock trees as well as a set of node correspondences. Using a diverse database of shapes, we demonstrate our system's performance under articulation, occlusion, and changes in viewpoint.

This talk represents joint work with Ali Shokoufandeh (Rutgers University), Kaleem Siddiqi (Yale University), and Steven W. Zucker (Yale University).

Henrik I. Christensen

^ Upp till Numeros hemsida.

Sidansvarig: <>
Senast ändrad 14 maj 1998
Tekniskt stöd: <>