Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

582456 Approksimointialgoritmit, 8 op (kevät 2010)

Ajankohtaista

Kurssi on päättynyt ja tulokset saatavilla laitoksen intranetissa.

Toinen kurssikoe:

Kurssipalaute on tervetullutta.

Annettava opetus

Luennot Jyrki Kivinen

Laskuharjoitukset Jouni Siren ma 14–16 sali BK106

Kokeet

Ensimmäinen kurssikoe pidettiin 1.3. Koealueena oli kokeeseen mennessä laskuharjoituksissa käsitellyt asiat eli viimeisenä 16.2. pidetyn luennon asiat (luentokalvot 1–180, katso kirjan vastaavat sivut allaolevasta luentoaikataulusta)

Toinen kurssikoe pidettiin to 6.5. klo 9–12. Koealueena oli loput kurssin asioista.

Harjoitustehtävät

  1. harjoitus (25.1.): tehtävät PDF / PS; ratkaisut
  2. harjoitus (1.2.): tehtävät PDF / PS; ratkaisut
  3. harjoitus (8.2.): tehtävät PDF / PS; ratkaisut
  4. harjoitus (15.2.): tehtävät PDF / PS; ratkaisut; lähdeartikkeli tehtävään 2
  5. harjoitus (22.2.): tehtävät PDF / PS; ratkaisut
  6. harjoitus (15.3.): tehtävät PDF / PS; ratkaisut
  7. harjoitus (22.3.): tehtävät PDF / PS; ratkaisut
  8. harjoitus (29.3.): tehtävät PDF / PS; ratkaisut
  9. harjoitus (12.4.): tehtävät PDF / PS; ratkaisut; lähdeartikkeli tehtävään 3
  10. harjoitus (19.4.): tehtävät PDF / PS; ratkaisut
  11. harjoitus (26.4.): tehtävät PDF / PS; ratkaisut; lähdeartikkeli tehtäviin 2 ja 3;

Artikkelitiivistelmä

Kurssiin kuuluu lyhyt kirjallinen ja suullinen esitys jostain sopivasta artikkelista.

Esitysten aikataulu:

Esitysten ja kirjoitelmien sisältö:

Luentomateriaali

Luentokalvot 1–417: PDF, PS (4 kalvoa/sivu),

Kurssi perustuu oppikirjaan

Vijay V. Vazirani: Approximation Algorithms. Springer 2003 (Second Corrected Printing)
(jota tosin ei käsitellä läheskään kokonaan). Luentokalvoista löytyy periaatteessa kaikki tarvittavat asiat, mutta oletus on, että opiskelijoilla on oppikirja käytettävissään.

Luentojen eteneminen

pvm aihe luentokalvot kirjan sivut (suunnilleen)
19.1. johdanto; peruskäsitteitä 1–28 1–4; 344–351
22.1. peruskäsitteitä, joukkopeite 29–44 5–17; 351–352
26.1. joukkopeite 45–60 17–22
29.1. Steiner-puut; TSP 61–81 27–33
2.2. k-keskusongelma 81–94 47–52
5.2. approksimointiskeemat, repun- ja laatikonpakkaus 95–116 68–76
9.2. lineaarinen ohjelmointi (johdanto) 117–135 93–103
12.2. joukkopeite ja duaalinsovitus 136–156 108–116
16.2. joukkopeite pyöristämällä ja primaali-duaaliskeemalla 157–180 118–128
19.2. maksimitoteutuvuus; erilaisten koneiden skedulointi 181–201 130–141
23.2. skedulointi loppuun; monileikkaus ja monihyödykevuo puussa 202–216 141–149
26.2. puun monileikkaus ja monihyödykevuo loppuun; monensuuntainen leikkaus 217–230 149–155
1.3. 1. kurssikoe
väliviikko
16.3. monensuuntainen leikkaus jatkuu 231–247 156–160
19.3. monensuuntainen leikkaus loppuun; monihyödykevuo ja monileikkaus mielivaltaisessa verkossa 248–268 160–173
23.3. monihyödykevuo ja monileikkaus jatkuu 269–284 173–181
26.3. kysyntäpohjainen monihyödykevuo ja harvin leikkaus 283–296 181–185
30.3. kysyntäpohjainen monihyödykevuo ja harvin leikkaus jatkuu 297–308 185–189
9.4. kysyntäpohjainen monihyödykevuo ja harvin leikkaus (melkein) loppuun 309–326 189–193
13.4. tuotantolaitosten sijoittelu 327–341 193–194; 231–235
16.4. tuotantolaitosten sijoittelu loppuun; k-keskusongelma 342–364 235–245
20.4. k-keskusongelma loppuun; PCP-teoreema 365–381 246–249; 309–311
23.4. approksimoitumattomuustuloksia: MAX-3SAT ja solmupeite 382–401 311–316
27.4. klikkiongelman approksimoitumattomuus 402–417 318–322


31. toukokuuta 2010 Jyrki Kivinen