582456 Approksimointialgoritmit, 8 op (kevät 2010)

Ajankohtaista

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

Toinen kurssikoe:

• tehtävät PDF / PS
• ratkaisut (PDF)

Kurssipalaute on tervetullutta.

Annettava opetus

Luennot Jyrki Kivinen

• periodi III (19.1.–25.2.): ti 8–10 sali B222; pe 12–14 sali D123
• periodi IV (16.3.–29.4.): ti 8–10 sali B222; pe 12–14 sali C220

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)

• tehtävät PDF / PS
• ratkaisut PDF / PS

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

• tehtävät PDF / PS
• ratkaisut (PDF)

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:

• Esitykset pidetään viimeisellä luentokerralla pe 30.4. klo 12–14.
• Alustava versio tekstistä tulee toimittaa luennoijalle sähköpostitse PDF-muodossa viimeistään to 29.4. klo 16. Alustavat versiot laitetaan tilapäisesti laitoksen intranetiin, jotta muut opiskelijat voivat halutessaan (hieman) tutustua niihin etukäteen.
• Lopullinen (arvosteltava) versio tekstistä tulee toimittaa luennoijalle viimeistään ma 10.5. klo 16.

Esitysten ja kirjoitelmien sisältö:

• Esitystä kohti on aikaa 10–15 minuuttia. Kirjoituksen ohjepituus on 5–10 sivua laitoksen kandidaatintutkielman formaatissa.
• Ei ole tarkoitus, eikä tila- ja aikarajojen takia edes mahdollista, selittää algoritmien tai todistusten yksityiskohtia (elleivät ne ole todella yksinkertaisia mutta silti kiinnostavia).
• Lähdemateriaalin mukaan mahdollisia käsiteltäviä asioita ovat esim. ongelman määrittely ja motivointi; mitä positiivisia ja negatiivisia tuloksia on esitetty aiemmin/juuri nyt/edelleen avoimena; mihin muihin ongelmiin tämä liittyy ja miten; sekä kenties kevyt katsaus tai ''highlight'' siitä, minkä tyyppisiä tekniikoita työssä on käytetty.
• Esityksen ja kirjoitelman on tarkoitus olla työmäärältään selvästi kevyempi kuin seminaarissa.

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