Nada

Nadas institutionssymbol

^ Upp till kursens hemsida

In English

Studiehandbokstext 1998/99 för

2D1443 Parallella beräkningar

Poäng

4
Föreläsning
30
Kursnivå
D
Övning
-
Betygsskala, KTH
U, 3, 4, 5
Lab
-
Obligatorisk för
-


Valbar för
D, F
Perioder
4
Språk
Svenska; på engelska om flera elever så begär
Webbinfo
www.nada.kth.se/kurser/kth/2D1443
Kursansvarig

Jens Lagergren, 08 - 790 7327, jens@nada.kth.se

Kortbeskrivning

En avancerad kurs i teoretisk datalogi som behandlar den parallella beräkningsmodellen PRAM.

Mål

Kursen mål är att

för att eleverna ska Kursinnehåll

Kursen kommer att beskriva PRAM-modellen. I denna arbetar ett antal processorer synkront i en slinga: läs-tänk-skriv. Med den tid en PRAM algoritm kräver menas antalet läs-tänk-skrivfaser. En algoritm är en NC algoritm om den använder högst tiden O(logk n) och högst O(nc) processorer på varje indata av storlek n (där k och c är konstanter).

Kursen börjar med att introducera modellen och ett antal tekniker. Bland dessa tekniker kan nämnas pointer jumping, accelerated cascading och symmetry breaking. Därefter studeras parallella algoritmer för problem av ungefär samma typ som på en vanlig algoritmkurs. Här kan nämnas algoritmer för: listor, evaluering av uttryck, sökning och sortering, undre gränser för sökning och sortering (i jämförelsemodell), grafer, strängar och aritmetik.

I mån av tid behandlas även probabilistiska parallella algoritmer och undre gränser för parallella PRAM algoritmer (generella).

Förkunskaper

Motsvarande en av kurserna 2D1353 Algoritmer, datastrukturer och komplexitet och 2D1354 Algoritmer och komplexitet.

Påbyggnad

Diskuteras med kursledaren.

Examination

Inlämningsuppgifter (ÖVN1; 4 p).

Kurslitteratur

Enligt förteckning på institutionen. Läsåret 96/97 användes J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992.

Övrigt

Kursen ges vartannat år. Ges 98/99.

Länk till studiehandbokstexten 1997/98

^ Upp till kursens hemsida


Sidansvarig: <www-kurs@nada.kth.se>
Senast ändrad 20 april 1998
Tekniskt stöd: <webmaster@nada.kth.se>