UL/FRI/UNI-RI/OM/Kolokviji/2004-12-01

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Kolokvij z dne 01.12.2004
UL/FRI/UNI-RI/OM

Čas pisanja: 90 minut minut.
Literatura: en A4 list z obrazci.

Naloga 1

V ravnini želimo razporediti n točk tako, da bosta poljubni dve med njimi oddaljeni vsaj za 1 ter da bosta najbolj oddaljeni točki čim bolj skupaj (torej, da bo maksimum razdalje med točkami minimalen).

a. Zapiši kot optimizacijsko nalogo.
b. Reši za n = 6, n = 7 in n = 8.
c. Kako bi nalogo reševal v splošnem?

Rešitev a

\Phi = \{ ((x_1, y_1), (x_2, y_2) ... (x_n, y_n)) \in (\mathbb{R} \times \mathbb{R})^n \ | \ \forall i, j \in \{1,2,...,n\}: i \neq j \Rightarrow d((x_i, y_i), (x_j, y_j)) \geq 1 \}

P(A \in \Phi) = max_{p, q \in A} d(p, q)

naloga: (Φ, P, Min)

Rešitev b

Točne rešitve sicer ne mislim risati, se pa da razbrati idejo iz točke c.

Rešitev c

Iterativno dodajamo točke: začnemo s tremi točkami (trikotnik, vse so med sabo oddaljene za 1). Nadaljujemo tako da označimo področje, na katerem točke ne moremo postaviti (v primeru trikotnika je to obomočje sestavljen iz treh krogov z radijem 1). Optimalen položaj nove točke naj bi bil na robu prepovedanega območja in to tam kjer lahko pridemo najbližje središču območja (v to zadnje nisem 100% prepričan, kakor nisem prepričan tudi v zadostnost tega opisa :) )

Naloga 2

Dane so matrike Al, A2, ... , An, Ai; ∈ Rai x i+1. Radi bi izračunali produkt A1 • A2 ... • An s čim manj množenji (vemo, da če množimo matriki oblik k x l in 1 x m, potrebujemo k l m množenj, rezultat pa je matrika oblike k x m).

Zapiši kot optimizacijsko nalogo. Kako bi nalogo reševal z lokalno optimizacijo (sosednost, začetna rešitev, računanje kriterijske funkcije, ...)?

Rešitev

\Phi = \{ (p_1, p_2, ... p_n) \in S_n \ | \ \forall i \in [1, n-1]: \mbox{rezultat mnozenja} A_{p_1} A_{p_2} ... A_{p_i} \mbox{se da mnoziti z} A_{p_{i+1}} \}

K(P \in \Phi) = \sum_{i = 1}^{n-1} \mbox{stevilo mnozenj za mnozenje matrike} A_{p_1} A_{p_2} ... A_{p_i} \ \mbox{z} \ A_{p_{i+1}}

naloga: (Φ, K, Min)

Lokalna optimizacija:

  • Dve permutaciji iz Φ sta si sosedni ko se razlikujeta samo v dveh elementih (dva elementa imata zamenjana položaja)

Naloga 3

Pokaži, da je množica

A = (x, y, z) \in \mathbb{R}\ \ log(x^2 + 2y^2 +5 z^2 + 3xz + y - sin(y)) \le 3, \ (x-y)^2 + (y-z)^2 + (z-x)^2 \le x + y + z

konveksna!

Rešitev

  1. Razdeliš na dve funkciji za kateri ugotavjaš konveksnost
  2. pri prvi pridejo glavne poddeterminante Hessejeve matrike H1 = 2, H2 = 20 + 2sin y, H3 = 110 + 11sin y (so vecje ali enake 0 za vse x,y,z)
  3. pri drugi pridejo glavne poddeterminante Hessejeve matrike H1 = 4, H2 = 12, H3 = 0 (so vecje ali enake 0 za vse x,y,z)
  4. ker velja, da je presek konveksih množic tudi konveksna množica, lahko rečemo da je začetna množica konveksna

Naloga 4

Naj bo D konveksna množica v \mathbb{R}n in a > 0. Definiramo S = x \in \mathbb{R}n | d(x,D) < a}, kjer je d(x, D) razdalja točke x do množice D. Pokaži, da je S konveksna.

Namig: za s1, s2 \in S pokaži, da je tudi \lambda\ s_1 + (1-\lambda)s_2 \in S.

Rešitev

s1,s2 \in S \Rightarrow d(s_1, D) < a \ in \ d(s_2, D) < a

Če zdaj ti dve točki vstavimo v tisto enačbo, ki je pogoj za konveksnost dobimo: d( \lambda\ s_1 + (1 - \lambda\ ) s_2, D) \le \lambda\ d(s_1, D) + (1 - \lambda\ )d(s_2, D)

Recimo da velja d(s_1, D) = a \ in \ d(s_2, D) = a (to sicer ni nikoli res). Potem zapišemo desno stran zgornje neenačbe kot: \lambda\ a + (1 - \lambda\ )a \Rightarrow d( \lambda\ s_1 + (1 - \lambda\ ) s_2, D) < a

iz tega lahko sklepamo, da je S konveksna

Vzpostavljeno iz »http://www.e-studij.si/UL/FRI/UNI-RI/OM/Kolokviji/2004-12-01«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja