---
title: AiSD Lista 2
tags: aisd
author: Mateusz Reis
---
# AiSD Lista 2

## Zadanie 2

Idea: Sortujemy odcinki względem punktu końcowego i wybieramy po kolei te które kończą się najszybciej tak aby wybrać ich jak najwięcej. Przy rozważaniu odcinka najpierw sprawdzamy czy nie zaczyna się przed końcem poprzedniego którego wybraliśmy, jeśli tak to nie wybieramy tego odcinka.
Pozwala nam to uniknąć sytuacji w której weźmiemy jeden odcinek który zablokuje możliwość wybrania dwóch innych.

Algorytm:

Posortuj odcinki względem ich końca. 
Wybierz odcinek który kończy się najwcześniej.
Wynik<-0
Koniec(jest to koniec naszego najpóźniejszego odcinka)<- odc.koniec
Dla każdego odcinka o z listy:
    Jeśli o.start>koniec:
        Wynik<-Wynik+1
        Koniec<-o.koniec

## Zadanie 3

Nasz algorytm musi wybierać największy możliwy ułamek mniejszy bądź równy $\frac{a}{b}$ o liczniku 1. Następnie odejmuje od aktualnie rozważanego wybrany ułamek i rozwiązuje problem dla nowego ułamka.

$$
\frac{a}{b}=\frac{1}{\lceil{b/a}\rceil}+foo\Big(\frac{a}{b}-\frac{1}{\lceil{b/a}\rceil}\Big)
$$

Nasz algorytm w oczywisty sposób zawsze się zatrzyma ponieważ za każdym razem odejmujemy niezerową wartość od skończonej liczby. Natomiast nie zawsze da wynik optymalny.
Przykład:

$$
\frac{9}{20}=\frac{1}{3}+foo\Big(\frac{9}{20}-\frac{1}{3}\Big)\\
\Big\downarrow\\
\frac{7}{60}=\frac{1}{9}+foo\Big(\frac{7}{60}-\frac{1}{9}\Big)\\
\Big\downarrow\\
\frac{1}{180}=\frac{1}{180}+foo(0)
$$
co daje
$$
\frac{9}{20}=\frac{1}{3}+\frac{1}{9}+\frac{1}{180}
$$
natomiast optymalne rozwiązanie to
$$
\frac{9}{20}=\frac{1}{4}+\frac{1}{5}
$$

## Zadanie 4

Na początku zauważmy że pokolowanie wszystkich liści drzewa zwiększy nam maksymalną liczbę wierzchołków na ścieżce o 2, ponieważ z liścia możemy iść tylko do góry i ewentualnie trafić do innego pokolorowanego liścia. Jest to masksymalna liczba wierzchołków które możemy pokolorować przy $k=2$. Można by też pokolorować wszystkie wierzchołki z jednego poziomu i wtedy również zwiększamy liczbę pokolorowanych wierzchołków o 2 ale każdy liść ma maksymalnie 1 rodzica więc otrzymalibyśmy w najlepszym przypadku tyle samo pokolorowanych wierzchołków. Tak więc nasz algorytm $\lfloor\frac{k}{2}\rfloor$ razy pokoloruje wszystkie liście a następnie je odrzuci i pokoloruje nowe liście i powtórzy operację, dodatkowo jeśli $k \,\,mod\,\, 2 = 1$ może pokolorować jeden dodatkowy wierzchołek. Można łatwo dowieść to przez indukcję ponieważ zawsze ścieżka która będzie zawierała maksymalną ilość wierzchołków będzie z liścia do liścia.

Algorytm:

G'<-G

dopóki k>1:
    pokoloruj wszystkie liście z G' w G
    k<-k div 2
    odrzuć wszystkie liście z G'
jeśli k==1:
    pokoloruj dowolony wierzchołek z G' w G

zwróć G 

## Zadanie 5


**Lemat 1**

W każdym momencie działania algorytmu, oraz po jego zakończeniu w $E'$ nie będzie cyklu.

**Dowód:**

Załóżmy nie wprost, że podczas działania algorytmu w którymś etapie pojawiła się spójna składowa, w której jest cykl. Oznaczmy ją jako $S$ Rozważmy następujące sytuacje:

* $S$ powstała przez połączenie dwóch superwierzchołków $v_{1}$ i $v_{2}$. Oznacza to, że do zbioru $E'$ zostały dołączone krawędzie $e_{i}$ i $e_{j}$. Ponieważ $e_i$ została dołączona jako najlżejsza krawędź incydentna do $v_{1}$ więc $C(e_{i})<C(e_{j})$. Ale skoro $e_j$ została dołączona jako najlżejsza krawędź incydentna do $v_{2}$ to musi zachodzić $C(e_{j})<C(e_{i})$ (Pamiętajmy, że w grafie nie ma krawędzi o takiej samej wadze) – sprzeczność.
* $S$ powstała przez połączenie się trzech lub więcej superwierzchołków. Podzielmy powstały cykl $C$ na następujące części: niech $v_{1},v_{2},v_{3},\dots ,v_{l}$ będą kolejnymi superwierzchołkami należącymi do $C$, a $e_{1},e_{2},\dots ,e_{l}$ będą kolejnymi krawędziami należącymi do $C$, które zostały dodane w zakończonym właśnie etapie algorytmu. W $C$ krawędzie $e_{i}$ oraz superwierzchołki $v_{i}$ występują na przemian. Z zasady działania algorytmu możemy stwierdzić, że aby powstał taki cykl, musi zachodzić $C(e_{1})<C(e_{2})<\dots <C(e_{l-1})<C(e_{l})<C(e_{1})$ – sprzeczność.

**Lemat 2**
W każdym etapie działania algorytmu otrzymujemy dla każdego superwierzchołka minimalne drzewo rozpinające

**Dowód:**

* Gdy zostanie zakończony etap 1:

Załóżmy, że istnieje taki superwierzchołek $V_{i}$ który nie jest minimalnym drzewem rozpinającym poddrzewa złożonego z wierzchołków należących do $V_{i}$. Weźmy więc takie minimalne drzewo rozpinające $T$. Istnieje krawędź $e_{i}$ taka, że $e_{i}\in E(V_{i})\land e_{i}\not \in E(T)$. Dodajmy $e_{i}$. W $T$ powstał cykl. Ponieważ $e_{i}$ jest incydenta do pewnego wierzchołka z tego cyklu, istnieje więc inna krawędź $e'_{i}$ incydentna do tego samego wierzchołka. Jednak z tego, że $e_{i}\in E(V_{i})$ wynika, że $C(e_{i})<C(e'_{i})$. Jeśli usuniemy krawędź $e'_{i}$ z $T$ otrzymamy mniejsze drzewo rozpinające, co jest sprzeczne z założeniem o minimalności $T$.

* Gdy zostanie zakończony etap 2:

Z poprawności etapu 1 wiemy, że istnieje takie wywołanie etapu 2, w którym każdy z superwierzchołków jest minimalnym drzewem rozpinającym. Jest to choćby pierwsze wywołanie. Załóżmy zatem, że dla pewnego wywołania tego etapu otrzymano superwierzchołki będące minimalnymi drzewami rozpinającymi, jednak scaliło przynajmniej dwa z nich w taki sposób, że dało się otrzymać mniejsze drzewo rozpinające.

Niech etap $k$-ty będzie pierwszym takim etapem, w którym coś się popsuło. Niech $E'_{1}$ będzie zbiorem krawędzi przed wywołaniem etapu $k$, a $E'_{2}$ będzie zbiorem krawędzi po jego wywołaniu. Niech $T$ będzie minimalnym drzewem rozpinającym takim, że $V(T)=V(V_{i})$, ale że $E(T)\not =E(V_{i})$. Istnieje więc krawędź $e_{i}\in E(V_{i})\land e_{i}\not \in E(T)$.

**Fakt**: Krawędź $e_{i}$ została dodana podczas $k$-tego wywołania. (Nie może należeć do $E'_{1}$, gdyż inaczej superwierzchołek do którego by należała nie byłby minimalnym drzewem rozpinającym, co jest sprzeczne z dowodem dla pierwszego etapu i założeniem, że wywołanie$k$-te jest najmniejszym wywołaniem, które zwróciło nieoptymalne drzewa).

Dodajmy krawędź $e_{i}$ do $E(T)$. W $T$ powstał cykl. Ponieważ $e_{i}$ jest najmniejszą krawędzią incydentną do pewnego superwierzchołka z tego cyklu, istnieje więc inna krawędź incydenta do tego samego superwierzchołka. Jednak jej waga jest większa niż waga krawędzi $e_{i}$, zatem zastąpienie jej krawędzią $e_{i}$ da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności $T$.

## Zadanie 6

Zacznijmy od tego że jeśli dana krawędź $e$ nie jest krawędzią maksymalną na żadnym cyklu z $G$ to należy do jakiegoś MST.

Dowód:
Załóżmy że $e$ nie jest maksymalna na żadnych cyklu z $G$ i nie należy do żadnego MST:
- $e$ nie należy do żadnego cyklu $\implies$ $e$ musi należeć do MST.
- $e$ należy do jakiegoś cyklu w $G$ mamy wtedy MST $T$ do którego nie należy $e$. Jeżeli dołożymy $e$ do $T$ to stworzymy cykl, wtedy w $T$ znajdziemy taką krawędź $f$ t.ż. $C(e)<C(f)$ (taka krawędź istnieje bo $e$ nie jest najcięższą krawędzia w cyklu) która leży na cyklu $c$, do którego należy również $e$, wtedy jeśli usuniemy $f$ z $T$ dostaniemy $T'$ które zawiera $e$ i jest lżejsze niż $T$.

Algorytm: usuwamy $e={v,u}$ z $G$, jeśli nie przechodząc przez krawędzie o wadze większej niż $C(e)$ dostaniemy się z $v$ do $u$ oznacza to że $e$ nie należy do żadnego MST, wpp $e$ należy do jakiegoś MST.

Pseudokod:

mod_DFS(G,start,koniec,maxw):
    jeśli start == koniec 
        zwróć false 
    
    dla każdego sąsiada x wierzcholka start:
        jeśli C({start,s})<maxw
            found<-mod_DFS(G,x,koniec,maxw)
        jeśli found==false
            zwróć false
    
    zwróć true
    
fun(G,e)
    v<-jeden wierzcholek krawedzi e 
    u<-drugi wierzcholek krawedzi e
    usun e z G
    zwroc mod_DFS(G,v,u,C(e))

Dowód poprawności:
- jeśli $e$ nie należy do żadnego cyklu nigdy nie dojdziemy do $u$ każdy mod_DFS zwróci false $\implies$ $e$ należy do MST, ponieważ nie istnieje ścieżka z $v$ do $u$ co znaczy że nie jest to drzewo rozpinające

- jeśli $e$ należy do cyklu i nie jest największą krawędzią to nigdy nie skorzystamy z krawędzi o większej wadze niż $e$ co rownież nie doprowadzi nas do $u$, ponieważ nigdy nie przejdziemy przez cykl aż do $u$

- wpp. dojdziemy do $u$ i mod_DFS zwróci false co oznacza że $e$ nie należy do MST

## Zadanie 7

Jest to znany problem, co ciekawe to dla jednej maszyny więcej jest to problem NP-zupełny.
- Oznaczmy zadania jako $z_i$ oraz ich czasy wykonania jako $a_i$ oraz $b_i$.
- Zacznijmy od tego że czas wykonania na maszynie $A$ to $\sum_{i=1}^n a_i$ ponieważ będziemy po kolei wykonywać zadania jedno po drugim bez przerw. Wtedy nie ważna jest kolejność ponieważ i tak musimy wykonać wszystkie zadania.
- Na maszynie $B$ będziemy wykonywać zadania w kolejności otrzymania ich od maszyny $A$. Jednak przy maszynie $B$ będziemy mieć dodatkowo czas przestoju spowodowany oczekiwaniem na wykonanie zadanie $a_i$ na maszynie $A$. Czas ten oznaczmy jako $x_i$ gdzie $i$ to czas oczekiwania przed wykonaniem zadania $b_i$. Wtedy czas wykonania zadań na maszynie $B$ możemy policzyć jako $\sum_{i=1}^n b_i + \sum_{i=1}^nx_i$. Oczywiście będziemy dążyli do zminimalizowania $x_i$.
- Ponieważ na początku kolejka do maszyny $B$ będzie pusta to $x_1=a_1$, tyle czasu musi upłynąć zanim zaczniemy wykonywać pierwsze zadanie na maszynie $B$. $x_2$ obliczymy jako $a_1+a_2-b_1-x_0$ ponieważ drugie zadanie najpierw wykonamy na maszynie $A$ w tym samym czasie wykonujemy już zadanie $b_1$ po opóźnieniu $x_1$. Natomiast $a_1+a_2$ może być czasem krótszym niż $b_1+x_1$ tak więc $x_2=max(a_1+a_2-b_1-x_1,0)$. Łatwo pokazać przez indukcję że $x_n=\sum_{k=0}^n a_k -\sum_{k=0}^{n-1} b_k - \sum_{k=1}^{n-1} x_k$