Nada

Numero 42

fredag 5 december 1997, årgång 27

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


Kalendarium

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

Luciafirande

Det blir luciafirande på fredag den 12 december kl 15 i fikarummet på plan 4.

Catherine

Parkeringstillstånd

Parkeringstillstånd finns nu att hämta hos mig.

Bibbi/rum 1419

Doktorandtjänst i numerisk analys och datalogi

Stockholms universitet ledigförklarar en doktorandtjänst i numerisk analys och datalogi. Ansökan senast 22 december 1997. Tillträde 1 januari 1998. Mer information i Numeropärmen 97.149.


Seminar by CIDs Scientific Advisory Board

CID, the Competence Centre for user-oriented IT Design at KTH, is proud to present its Scientific Advisory Board through three half-hour lectures.

Friday, December 5, at 13.15-15 in lecture hall E1, entrance from Lindstedtsvägen 3 and Osquars Backe 2, KTH.

Understanding design representations

Susanne Bødker, Computer Science, Aarhus University

Representing computer applications and their use is an important aspect of design. In various ways, designers need to externalise design proposals, and to present these to others, whether these are fellow designers, users, or managers. This talk deals with understanding design representations and what work they do in design. The talk is based on a series of theoretical concepts coming out of studies of scientific and other work practices, and on practical experiences from design of computer applications. I will present alternatives to the ideas that design representations are mappings of present or future work situations and computer applications and suggest that representations are primarily containers of ideas, and that representation is situated at the same time as representations are crossing boundaries between various design and use activities. As such, representations should be carriers of their own contexts, as regards use as well as design. The talk is based on a series of examples from my practical design experience.

User Interface Trends

Irene McWilliam, Philips Corporate Design, Eindhoven

Bits of the Future: Products and By-products of the Information age

Andrew Lippman, MIT Media Lab

An important challenge in a wired world is how we can extend the technology to all people, in all cultures, for socially valuable purposes. One solution is a "computing grid", much like the power system, that links portable, ultra-lost cost devices affordable by all.

This moves multimedia away from the screen and onto the person, into clothes, houses, toys and objects. In this talk, I summarize work at the MIT Media Laboratory on nomadic interfaces, global media , and new technologies for representation and interaction that rely on small gateways to worldwide computing as an alternative to high cost, individualized workstations.

Yngve Sundblad, CID managing director

CID-seminarium: Some Effects of Human-Computer Interaction on Human-Human Interaction

Christine Neuwirth, Carnegie-Mellon University, USA, håller CID-seminarium under ovanstående rubrik på onsdag (10 dec.) kl. 13.00-15 i seminarierum 4523 (Lindstedtsv. 5, plan 5).

Abstract

This talk describes research at the intersection of human-computer interaction and computer-support for cooperative work, particularly support for the cognitive and social processes of collaborative writing and communication. The research has followed a three-pronged approach: (1) Task analysis involving descriptive studies of people writing together and communicating in order to solve a problem. The aim of the analysis is to build models that will be useful in identifying ways in which computers can support those processes; (2) The development of computer prototypes that embody hypotheses about features of human-computer interfaces to augment writing and communication processes; and (3) Empirical studies that evaluate particular features of those interfaces.

The talk will present results from three studies: (1) the effect of keyboard/voice modality on the production of annotations by reviewers and the reception of those annotations by writers; (2) the effect of different interfaces for annotation on the communication of collaborative writers; and (3) the effect of different interfaces on the time it takes problem-solvers to perform key tasks in joint problem-solving requiring aynchronous communication.


Konferens om studerandeaktiva arbetsformer i utbildningen

Linköpings universitet ordnar en konferens om studerandeaktiva arbetsformer i utbildningen i utbildningen - ett kulturmöte mellan gymnasieskolan och högskolan den 16-17 november 1998. De efterlyser bidrag i form av en sammanfattning av pedagogisk försöksverksamhet, egna idéer och uppslag eller forskningsarbete med inriktning mot studerandeaktiva arbetsformer i vid mening. Jag har lite mer info.

Kerstin F.

Meddelande från prefekten december 1997

Nadas luciafirande blir fredagen den 12 på eftermiddagen.

Michael Hanke, numerisk analys och Mikael Goldman, datalogi tillträder sina lektorat den 1 januari 1998.

Mariana Dorobantu presenterar sin licentiatavhandling fredagen den 5 december kl 13. Därefter flyttar hon och Mihai till USA.

Christer Berg disputerar fredagen den 19 december kl 14.

Jan-Erik Mångs har slutat på systemgruppen och börjar på annan anställning den 1 december.

De utlysta tjänsterna som personalansvarig (72 sökande), ledare till systemgruppen (2), kvalificerad sekreterare (10), informationsansvarig (7) samt ett antal doktorandtjänster är under tillsättning. Vi räknar med att vara klara under december månad.

Kontrakten för Cid och Psci har förnyats och gäller fram till år 2000.

Resultat av universitetskanslerns bedömning av KTH presenteras den 4/12 1997.

Nadas engelskspråkiga tidning finns nu för spridning till olika intressenter.

Reserapport från fem lärares besök på tre institutionen i England och Wales kommer att föreligga under december månad och presenteras på institutionskollegiet den 1/12.

För Nadas självvärdering finns en enkät avsedd för studenter och som behandlar grad av studentservice. Blankett återfinns vid studentexpeditionen. Lärarna ska sammanställa kursanalyser under december. Alla doktorander ombedes fylla i en enkät under december och vissa doktorander och handledare kommer att intervjuas under våren. Avsikten är att få reda på doktorandernas studieförhållanden, motivation mm.

Akademiska Hus, AH insatser beträffande lukt i huvudbyggnaden LV 5. Under våren togs prover och prövades tvättning av korridorer och trapphus. Detta resulterade inte i någon förbättring. Under sommaren utfördes ommålning, som givit en klar förbättring enligt AH. Nu avvaktar man och har begärt en handlingsplan inför sommaren 1998 om lukten återkommer. Om så erfordras kommer färgen att tas ner och ersättas med ny. Gunner Kjönsberg, Akzo Nobel är mycket säker på att luften inte innebär några hälsorisker.

Arbetet med att karlägga de elektromagnetiska fälten och att förbättra avskärmningen från ställverket på plan 2 har accelererat. Vi räknar med att få besked denna månad.


Disputation: On Oracles and Circuits - Topics in Computational Complexity

Christer Berg disputerar på avhandlingen "On Oracles and Circuits - Topics in Computational Complexity" fredagen den 19 december kl 14.00 i Kollegiesalen, Administrationsbyggnaden, Kungl Tekniska Högskolan, Valhallavägen 79, Stockholm. Opponent är Pavel Pudlák, Academy of Sciences of the Czech Republic.

Abstract

This thesis presents results in computational complexity related to the theory of oracles and circuits.

Circuits compute Boolean functions, and the size of the smallest circuit that computes a function is a way to measure this function's complexity. An oracle is a tool used to investigate the relationship between complexity classes, and the structure of individual classes. There is also a tight connection between lower bounds for bounded depth circuits and the existence of oracles for hierarchy complexity classes.

We present a version of the Karchmer and Wigderson game, and use this game to give an upper bound on the probability that a monotone formula depends on k variables after a random restriction has been applied to it.

We propose a symmetric version of Razborov's method of approximation which is used to prove lower bounds for monotone circuit complexity. The new approximation argument does not rely on the Sunflower lemma that previously has been essential for the method of approximation. By using this version of the approximation method, we provide exponential lower bounds for a number of monotone problems, among them the Clique problem. The bounds obtained are the same as the previously best known for the respective problems. We also show how to extend our method in order to give lower bounds for monotone real circuits.

We show that there are functions computable by linear size circuits of depth k that require exponential size perceptrons of depth k-1, for constant k. Using the relation between constant depth circuits and oracles for the polynomial hierarchy, we prove the existence of an oracle that separates the levels in the PP(PH) hierarchy. We also prove another lower bound for the size of perceptrons with bounded weights, which makes it possible to show an almost tight oracle separation.

Finally, we study, from several points of view, the problems involved in constructing an oracle A under which BPP collapses to probabilistic linear time. Such an oracle was proposed by Fortnow and Sipser; however, their construction was incomplete. We prove a structure theorem for probabilistic oracle machines, which could help complete the construction of the oracle A. On the other hand, we show that there are previously unknown problems with the Fortnow-Sipser construction.


Seminarium: PDC Artist Teresa Wennberg

The artist Teresa Wennberg has been invited by PDC to realize an environment for a "CAVE" and will work here during next year. She has been working with electronic media since the late seventies and has been invited by numerous institutions to do so, such as the Pompidou Center in Paris, Le Fresnoy in Lille, the GAMSAU laboratory in Marseille, Aoyama Computer Graphic School in Japan, the Vasulka Studio in the US.. Her work has been exhibited throughout the world.

On Tuesday December 9th at 10.30 in room 1537 at PDC, she will be doing a short presentation of herself and some works and installations and talk a little about her project here at PDC.

Welcome !

Gert Svensson

Nummeseminarium: Rationella faktoruppdelningar av cirkeldelningspolynom

Docent Hans Riesel håller seminarium i numerisk analys under ovanstående rubrik måndagen den 19 jan. kl. 15.15-16 i seminarierum 4523 (Lindstedtsv. 5, plan 5).

Sammanfattning

Det finns vissa specialfall av cirkeldelningpolynomen, som har oväntade faktoruppdelningar, såsom $x^4+4=(x^2+2x+2)(x^2-2x+2)$ och $x^6+27=(x^2+3)(x^2-3x+3)((x^2+3x+3)$. Föredraget handlar om dessa fall. En algoritm för att finna dessa formler kommer att beskrivas samt resultat för alla gradtal upp till 180.

[Fel i första ekvationen rättat 1998-01-09./Red.]


Exjobbsseminarium i datalogi

Ett exjobbsseminarium äger rum på torsdag (11 dec.) kl. 15.15 i seminarierum 4523 (Lindstedtsv. 5, plan 5, vid Sans).

Dan Waltin, F92, 20 poäng. Visualisering av förslitningar hos filtar och viror i en pappersmaskin med hjälp av animering. Arbetet är utfört vid Skogsindustrins tekniska forskningsinstitut. Handledare och examinator: Lars Kjelldahl.

Hans Österlund, T91, 12 poäng. Kanaltilldelning i radarsimulator. Arbetet är utfört vid Celsius Tech Electronics. Handledare: Henrik Eriksson. Examinator: Lars Kjelldahl.

Johan Dewe, D92, 20 poäng. En prototyp för att klassificera dokument från WWW med avseende på genre och ämne. Arbetet är utfört vid Telia Research. Handledare: Kerstin Frenckner. Examinator: Kerstin S-Eklundh.

Kerstin F.

Kurs: Vad är det du säger? Eller: Hur får vi eleverna att göra bra muntliga och skriftliga presentationer?

Bengt Hemlin, presentationsguru, Tom Åseskog från språk och didaktik m.fl., håller kurs för alla Nada-lärare och övriga intresserade Nada-anställda under ovanstående rubrik måndag-tisdag 15-16 dec. kl. 9.15-16 i sal V3 (Teknikringen 72, 2 trappor).

Kursen ska uppmuntra och lära oss att

Det finns fortfarande platser kvar på kursen! Anmälan till Kerstin F. senast 5 december.

Mer info på http://www.nada.kth.se/~kfrenck/Lararinfo/Presentationskurs.html

Kerstin F.

Diskret matte-seminarium: Starkt sammanhangande riktade grafer och pomängder av pomängder

Anders Björner håller seminarium i diskret matematik under ovanstående rubrik på torsdag (11 dec.) kl. 15.15-16.15 i seminarierum 3733, matematik, KTH (Lindstedtsvägen 25 - klocktornet, plan 7).

Sammanfattning

En riktad graf kallas starkt sammanhängande om det är möjligt att komma från varje nod till varje annan nod längs en riktad stig. Vi betraktar mängden av alla riktade grafer på n noder som inte är starkt sammanhängande. Tar man bort kanter så bevaras denna egenskap, så denna mängd bildar ett simplicialt komplex. Vårt huvudresultat är att detta komplex är homotopiekvivalent med en kil (wedge) av (n-1)! sfärer av dimension 2n-4. Det har alltså torsionsfri homologi koncentrerad i en dimension. I beviset och analysen av dessa grafer spelar en viss partialordning av mängden av alla partialordningar av n element en betydande roll. Motsvarande frågeställningar för oriktade grafer har visat sig vara av betydelse i Vassilievs teori för knutinvarianter.

(Gemensamt arbete med V. Welker)

A. Björner och J. Håstad

^ Upp till Numeros hemsida.


Sidansvarig: <numero@nada.kth.se>
Senast ändrad 4 december 1997
Tekniskt stöd: <webmaster@nada.kth.se>