Numero 6

måndag 13 februari 1995, årgång 25

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


Kalendarium

Aktuellt kalendarium, dvs. inte kalendariet som hör specifikt till denna Numeroutgåva.

Tydlig avsändare och publiceringsanvisning på Numerobidrag!

Det händer då och då att Numerored. får bidrag i Numerofacket där det bland en mängd olika fakta - tidningsartiklar t.ex. - inte alls är självklart vad som avsändaren önskar få publicerat. Är då bidraget också helt anonymt får red. svårt. För er egen skull: skriv namn och markera vad det gäller! (Till detta nummer gällde detta nr. 4 av Riksdag & Departement.)

Red.

Vicerektor

KTHs valförsamling föreslår, som väntat, Staffan Ström till ny vicerektor för forskning och forskarutbildning. Högskolestyrelsen fattar beslut vid sitt ordinarie sammanträde måndagen den 20 februari. Staffan Ström tillträder sin nya befattning den 1 april, om Högskolestyrelsen säger ja. Mandatperioden räcker t o m 1999.

KTH-ekot

NADA-föreläsare till gymnasieskolors högskolevecka?

Informationsenheten söker lärare och forskare som vill föreläsa på Stockholms gymnasieskolor under högskoleveckan 20-24 mars. Ett tillfälle att locka ungdomar till KTH, således. Ingrid undrar om vi har några kandidater. Kontakta i så fall snarast Christina Sternerup, faxnr 790 8177. Mer information i Numeropärmen 95.021.


Öppet hus

...fredagen den 24 febr. kl. 14.00-17. Karlavägen 101.

Välkomna!

Stefan A. och Elisabeth

Bostadsökande

Jag är doktorand på IPLab och jag söker en 1:a eller 2:a i andra hand, möblerat eller omöblerat för ett år fr.o.m. april. Alla förslag är välkomna. Ring 9157 eller skriv till <thierry@nada.kth.se>.

Thierry Reigner

Prefekten bortrest

Jag är bortrest under vecka 9 (27 febr. - 3 mars). Under den tiden är Johan Håstad ställföreträdande prefekt.

Ingrid

Fikaseminarium: NADA-tidning

Vi planerar att göra en informationstidning på NADA som ska rikta sig till gymnasieelever, teknologer och andra intressegrupper. Avsikten är att sprida information om vad vi gör, men även varför. Vi vill intressera fler att läsa datavetenskap och vara med och påverka framtiden inom IT. Jag behöver intresserade personer som vill påverka mål, innehåll och form i tidningen. Vi är berädda att skaffa nödvändig kompetens utanför institutionen om det behövs, men först måste vi veta hur vi vill ha det.

Många av lärarna informerar idag elever och studenter på olika nivåer. Idag har vi en hel del råmaterial på institutionen. Vi borde sätta samman olika informationsmaterial. Hur ska dessa se ut?

Kom till ett fikaseminarium tisdagen den 21 februari kl. 10.15 i lunchrummet på plan 4 och bidra med dina synpunkter.

Ingrid

Fyraperiodsschema

Det är nu beslutat at hela KTH ska ha ett fyraperioders lässchema läsåret 95/96. Varje läsperiod innehåller sju läsveckor och en tentavecka. De två sista dagarna i sista läsveckan är markerade som disponibla dagar; hur det rent praktiskt ska gå ihop sig är för mig oklart.

Period 1: vecka 36-42
Period 2: vecka 44-50
Period 3: vecka 3-9
Period 4: vecka 11-13 samt 17-20

Det blir två omtentaveckor i augusti (34-35), en efter jul (2) och nästan två (15-16) efter påsk.

Kerstin F.

Information om projektet "Teknologers datorkraft"

Från och med hösten 1995 kommer alla nyantagna teknologer på KTH uppmanas köpa en egen persondator att använda i sin utbildning. KTH tillhandahåller sedan lämplig programvara (ordbehandlare, kalkyl- program, kommunikationsprogram samt numeriska och symbolbehandlande matematikprogram) samt den infrastruktur som krävs för att eleverna effektivt skall kunna utnyttja denna resurs. Till detta hör t ex: För att datorn skall bli ett hjälpmedel i teknologernas utbildning fordras vidare att lärarna modifierar sina kurser så att eleverna får vettig användning av datorn i olika sammanhang. KTH's rektor för grundutbildningen kommer därför uppmana institutionerna att på olika sätt planera för denna ökade datoranvändning.

Under nästa läsår gäller projektet främst första årskursens elever och kurser för att sedan sprida sig upp i årskurserna därpå följande läsår. De institutioner som berörs främst under läsåret 95/96 är fysik, matematik, nekanik och NADA, men även andra institutioner blir inblandade genom mindre linjespecifika kurser.

För Nadas del innebär detta projekt att vi får tänka till hur tekno- logerna kan utnyttja sina datorer i Programmeringsteknikkursen (4p) för MVTBKIL samt Inda-kursen (8p) för FDE.

För att förbereda denna förändring har KTH's datorråd beslutat genom- föra ett pilotprojekt för I-linjens 1:a årskurs under vårterminen. Dessa I-elever läser bl a Programmeringsteknikkursen i vår. De elever som inte redan har egen dator får låna en bärbar Power-book av KTH. Eleverna kommer vidare att förses med bl a kommunikationsprogram (First Class), Pascalkompilator, Matlab, Maple samt en ordbehandlare. KTH ställer även upp med service och hjälp till elever och inblandade lärare genom Michael Westlund och Björn Gahm, som kommer från D-linjen och är heltidsanställda av TS-avdelningen på KTH.

Precis hur I-eleverna skall använda sina datorer i ProgT-kursen är ännu inte bestämt. Mycket talar för att de flesta av de laborationer och definitivt den individuella programmeringsuppgiften skall göras och redovisas på Nadas Unix-datorer. Någon eller några av de första Pascal-laborationerna och Matlab-uppgiften skulle dock kunna göras och redovisas på den egna datorn. Vidare kan den användas för olika slags kommunikation: uppkoppling till Nadas datorer via moden hemifrån, internt post- och infosystem via I-linjens egen server, etc. Naturligt- vis kan man också förbereda Pascal-uppgifter hemma, ta med sig filerna på egen diskett till KTH, tanka över dem till Nadas datorer, osv.

Allt det här blir naturligtvis en stor apparat, som ställer stora krav på nät och annan infrastruktur. Förutom att jag är kursledare i ProgT- kursen på I-linjen i vår är jag också ordförande i Datorrådets refe- rensgrupp för grundutbildningen på KTH. Jag välkomnar därför alla tips och synpunkter på planeringsprojektet (det som gäller alla nyantagna nästa år) och pilotprojektet som pågår under vt-95.

Lennart Edsberg

NADA:s anslag dras ner

Och det är jag som drar ner dom! Mest varje dag plockar jag bort papper som tejpats på glasrutor och väggar, även NADA-meddelanden. Dessa papper sätter jag i stället upp på anslagstavlorna, som huset har gott om, eller i nödfall på metallytor i dörrarna.

Egentligen vore det bättre om papperen anslogs på rätt plats meddetsamma. Det är i alla fall vad arkitekten framfört. Väggarna är målade med en speciell färg som kanske inte går att få tag i mer och som följer med tejpen bort. Tejpmärken på glas är besvärligt att få bort, fästkuddar är värre och allra värst var dom postetiketter som någon använde i höstas!

Beträffande anslagstavlor så anslås nu alla betygslistor för tekniskurser på dom stora tavlorna till höger på plan tre. Tavlorna till vänster kan vi använda för all annan information. Större delen är nu allmän reklamyta, den erövrar vi allteftersom vi behöver mera utrymme. Universitetskurserna och deras betyg anslås utanför expeditionen.

Som flyttansvarig kan jag med tillfredsställelse konstatera att dom flesta nu packat upp sina kartonger. Dom som ännu har kartonger kvar kan kanske meddela vilken morot eller piska som skulle kunna göra dom mer uppackningsbenägna!

Henrik E

IPLab-seminarium: Developing Cognitive Tools Based on Cooperative Hypermedia Systems for the Support of Group Problem Solving

Norbert A. Streitz, Darmstadt, Tyskland, håller IPLab-seminarium under ovanstående rubrik på onsdag (15 febr.) kl. 13.15 i sal E32 (Lindstedtsv. 3, plan 3).

Abstract

This talk is about the design and implementation of cognitive tools supporting collaborative work activities. Although the application scenarios can vary to quite an extent (product design meetings, business decision making, editorial meetings for publishing, software development planning) there is a common focus on group problem solving. In addition, we address a wide range of social and physical situations (local and distributed group meetings, desktop-based as well as meeting room based collaboration). The design is grounded in a conceptual framework for building systems where the role of hypertext and hypermedia is central. Although a wide range of collaborative work can benefit from the approach taken, one can characterize our approach as support for document-based activities, i.e., collaborative work where documents are either produced or are used as means during group work (Streitz, 1994). In our view, most of these documents are or will be realized as hypermedia documents. This is a result of our approach where we are trying to bring together the research areas of CSCW and hypermedia, while building on a theoretical foundation in cognitive and social psychology, and reflecting the requirements not only in an appropriate functionality but also in innovative group-oriented user-interfaces.

At GMD-IPSI, we have developed cooperative hypermedia systems which follow the approach outlined above. SEPIA (Streitz et al, 1992) is a hypermedia authoring environment for single as well as synchronous and asynchronous cooperative use which provides dedicated functionality by offering different types of operations and nodes and links in corresponding 'activity spaces'. The definition of the functionality is based on a cognitive theory of writing as problem solving. Subsequently, we developed DOLPHIN (Streitz et al, 1994), an electronic meeting room environment for group use in one as well as in several distributed meeting locations providing shared workspaces. It combines the advantages of freeform writing, scribbling, and drawing on an electronic whiteboard with those of more formal node-link structure representations and opportunities for using them in coexistence but also of transforming them into each other (Haake, Neuwirth, Streitz, 1994). This functionality is complemented by an innovative pen-based user interface which makes use of gesture recognition in order to provide the most frequently used operations.

Different versions and combinations of these systems serve as concrete examples for discussing on how to meet the requirements of future digital information environments using the proposed approach. At the same time, they provide promising examples of a class of applications which are needed to justify the immense investments planned for today's and future information super highways (Hoschka, Butscher & Streitz, 1992) which are currently under debate due to the parallel development and merge of computer, network and telecommunication technology.


SANS-seminarium: The spatter code for encoding concepts at many levels

Pentti Kanerva, SICS, håller SANS-seminarium under ovanstående rubrik på onsdag (15 febr.) kl. 13.15 i seminarierum 1537 (Lindstedtsv. 3, plan 5).

Abstract

The Spatter Code encodes "high-level" concepts in terms of their "low-level" components so that concepts at different levels can be combined freely. The binary spatter code is the simplest and it will be used as an illustration. The spatter code is intended for the modeling of encoding by the brain and it is "neural" in several ways: (1) it is high-dimensional (e.g., 10,000 bits or "neurons"), (2) it is random, (3) it does not use fields, and (4) it is most simply realized with linear threshold functions. A properly designed spatter code is RECURSIVE and ANALYZABLE. "Recursive" means that the codewords for components and combinations have the same statistical distribution (e.g., the same probability of 1s), and "analyzable" means that it is possible to decide whether codeword Wi is a component of codeword Wj. However, the code is not reversible in the sense that one could determine the components of Wj by looking at Wj alone. The Spatter Code was inspired by the Scatter Code of Smith and Stanford, which combines components with XOR, while the spatter code combines them by thresholding their sum.

Roland Orre, Anders Lansner

Docenföreläsning: Funktionaldeterminanter av Laplace-operatorn i 2D simpliciska komplex

Erik Aurell, håller docenföreläsning under ovanstående rubrik på onsdag (15 febr.) kl. 15.15-16 i sal 21 i hus 5 (SU-matematik, Kräftriket). Det är den sista av tre docentföreläsningar med början kl. 13.15. Se Numeropärmen 95.022.


Diskret matte: Embeddability of simplicial complexes

Karanbir Sarkaria, Chandigarh, Indien, håller seminarium i diskret matematik (kombinatorik och teoretisk datalogi) under ovanstående rubrik på torsdag (16 febr.) kl. 16.15-17.15 i rum 13.08, matteinst., KTH (Fiskartorpsvägen 15A, 1/2 tr, t.h.).


Fulbright commission-anslag

...ger anslag till forskning och/eller undervisning vid amerikanska universitet och till en visiting lecturer in Scandinavian Studies vid Berkeley-universitetet.

Sista ansökningsdag lördagen den 15 april. Numeropärmen 95.023.


Diskret matte: Faster Sorting in Theory and Practice

Arne Andersson, Lunds Universitet, håller seminarium i diskret matematik (kombinatorik & teoretisk datalogi) under ovanstående rubrik måndagen den 20 febr. kl. 15.15-16.15 i sal E32 (Lindstedtsv. 3).

Abstract

The problem of sorting is regarded as one of the most fundamental in computer science, taught in introductory courses all over the world. We present some new findings.

* Our first algorithm, Forward Radix Sort, is very simple and fast in practice.

* Adding a preprocessing step, the algorithm will adapt gracefully to the input distribution. The analysis can be made in terms of the number of bits that need to inspected in order to distinguish the elements or in terms of the entropy of the input.

* Extending the algorithm further, we obtain an O(n loglogn) worst- case time algorithm for sorting arbitrary integers, a significant improvement over previous upper bounds. In fact, the algorithm allows the input elements (integers, strings, etc) to occupy more than a constant number of machine words each. If the total number of machine words occupied by the elements is W, the worst-case sorting cost is O(W + n loglogn).

* Using hash coding, sorting can in some cases even be made in linear time.

Anders Björner & Johan Håstad

Modellization of self-propelling particles with a coupled map lattice model

Jan Hemmingsson, IFM, Linköping, håller seminarium under ovanstående rubrik måndagen den 20 febr. kl. 15.15 i seminarierum 1537 (Lindstedtsv. 3, plan 5).

Abstract

We present a simple coupled map lattice model for simulating self-propelling particles. The interaction consists of three parts; viscous "smearing" where the momenta are averaged over some neighborhood, the collision where the momenta are conserved, and finally the acceleration. Like in externally forced fluids we find three regions: diffusion, convection and intermittency.


Populärvetenskapligt: Kan datorn tänka? Industrial Applications of Artificial Intelligence

Rand Walzmann, håller seminarium i NADA:s populärvetenskapliga serie Datorn i människans tjänst under ovanstående rubrik på onsdag (15 febr.) kl. 17.15-18 i sal E7 (Lindstedtsv. 17).

Abstract

In the highly competitive environment of todays world, organizations have realized the need for rapid and effective decision-making in order to survive and grow. Many business organizations have come to recognize the potential of artificial intelligence (AI) technology to help meet this need and have adopted the technology for routine use. One recent survey documents over 2500 AI applications and estimates that they have covered only 20% of the working systems. The rapidly growing number of successful applications of AI technology during the past 10 years has resulted in the replacement of the early mysticism surrounding the technology by the perception that it provides a very useful tool for assisting human decision-making. AI technology is being absorbed into the mainstream of software technology. Organizations are increasingly turning to AI technology to solve problems the way they presently turn to other software tools. The trend is away from stand-alone AI based systems towards systems that are embedded in other conventional software programs. An embedded AI system builds on available functionality of existing appllication software by performing some task in a more intelligent fashion. These developments have been made possible by the steadily increasing availability of low-cost and powerful tools for developing AI systems and integrating them into more traditional environments.

In this talk I will discuss current trends in applications of AI technology in business and industry and will illustrate them with several examples.


Exjobbspresentation: On the Computation of Fixpoints in Static Program Analysis with an Application to Analysis of AKL

Erik Schön håller exjobbspresentation för IT-institutionen under ovanstående rubrik på fredag (17 febr.) kl. 10.00-11 i styrelserummet, SICS (Electrum, Kista).

Abstract

Static program analysis is a way of automatically deriving approximate semantic information about a program before actually running it. This information can then be used by a compiler for optimizing the generated code with respect to eg. size, speed of execution and memory usage.

A fixpoint solver lies at the heart of most frameworks for static program analysis. Given a system of equations containing monotone functions on a complete lattice, the fixpoint solver iteratively computes the values of the functions and terminates with a solution in a finite number of iteration steps when the equations are stable, i.e. do not change.

A dependency graph is normally used as a guide to which function to compute in each iteration step. This is a directed graph, possibly with cycles, where the vertices represent functions in the system of equations and an edge from vertex i to vertex j indicates that function j depends on the value of function i for its evaluation.

As the number of equations tend to be very large, it is extremely important to avoid unnecessary computations and hence to find an optimal order in which to compute the functions . It is also important to have an efficient method for detecting stability. An algorithm satisfying these two requirements is Bourdoncle's algorithm (1993) for finding a weak topological ordering of a directed graph which may contain cycles. Bourdoncle's algorithm is a generalization of Tarjan's algorithm for finding the strongly connected components of a directed graph.

We present results from experiments with a fixpoint solver in the Analysis Framework for AKL (Agents Kernel Language, a concurrent constraint language developed at SICS) using the above ideas showing that a considerable speed-up can be achieved compared to that of a fixpoint solver using Tarjan's algorithm.

We also present a class of functions particularly suited to the iterative scheme of computations that arise in monotone fixpoint computations on complete lattices.

Descriptors: static program analysis, fixpoint computations, dependency graphs, topological sorting, Tarjan's algorithm.

Björn Lisper


Numero utkommer normalt på fredagar under terminstid, manusstopp kl 13 dagen före.

Bidrag till Numero kan lämnas i datorläsbar form - via datorpost till <numero@nada.kth.se> eller i Mac-mappen Numero-bidrag i filhanteraren Nada-arkiv - eller på papper till KTH; NADA, Numero; 100 44 STOCKHOLM (dvs. Numerofacket bland NADA-postfacken). Varje Numero-utgåva utkommer i tre former:

Ibland refereras till Numeropärmen. Det är en pärm som finns i NADA:s fikarums bokhylla (plan 4).

Numero-redaktionen består f.n. av Peter Svanberg. Ansvarig utgivare är Ingrid Melinder. Numeros innehåll uttrycker inte institutionens officiella ståndpunkt annat än då detta anges.