zad 1
Dany graf w postaci macierzy sąsiedztwa
Napisz algorytm lgs(G) zwracający liczbę gwiazd spinających

zad 2

Kod:

begin
a=0 ,b=n, suma=0
while a<n and b>0 do
       begin
              if p>0 then begin a=a+1, suma=suma+1 end
              else begin a=a-1, b=b-1, suma=suma+1 end
              myfikuj(p)  {p przekazywane przez wsk, generalnie chodzi o zmiena znaku liczby lub nie}
      end
end

Jaka jest maksymalna wartość zmiennej suma po zakończeniu pętli?
odp: 3n-2

zad3
Napisz algorytm o złożoności ( rys w załączniku)

if n<=100
  for n to 100 ;

zad4
oszaczuj asymptotyczną liczbą kroków ( w sensie theta) i podkreśl złożoność obl

Kod:

procedure X(n:int)
var i,j,k,L: int
begin
      i=3, L=0
     while i<n^3 do begin
            i=3*i, j=1
           while j<n^2 do begin
                      j=2*j
                      for k=1 to j do L=L+1
            end
     end
end

w 4. wyszlo mi

wyszlo mi O(logn * n^2)  czyli napisalem teta(n^2)

wewnętrzna pętla to suma od j=1 do j=log2(n^2) z 2^j czyli wychodzi n^2 a zewnętrzna wykona się log3(n^3) czyli teta(logn) razy czyli w sumie masz n^2 logn ale to chyba nie jest teta(n^2) chyba

Ad.4 Na bank nie jest tak, ze


i juz tlumacze jak po kolei to rozkwinialem.
Ppetla while
, a dalej
wykona się dokładnie
razy. Czemu tak jest to już chyba policzyć dacie radę. Teraz lecimy w głąb pętli. I tutaj ważna sprawa, bo to co jest w tej pętli poza zmianą i wykona się zawsze tyle samo razy, niezależnie od wartości i w danym przebiegu. Dlatego mamy
gdzie
to zlożoność pętli iterowanych po j i k.

Tu się zaczynają małe schody. Pętla iterowana po j wykona się zgodnie z powyższym wzorem
, jednak tym razem liczba wykonań pętli wewnętrznej JEST zależna od wartości j. Pętla iterowana po k wykona się więc dokładnie j razy. Sumujemy więc ilość iteracji pętli iterowanej po k. Zostanie ona wywołana
razy, za każdym razem wykonując
razy. Czyli mamy
. Na to mamy wzór nawet w czerwonej księdze szatana:
. Zmieniamy go lekko, bo potrzeba nam czegoś takiego:
(zliczamy od 1, a nie od 0), i podstawiamy:
.

No to mamy już wszystko, i składamy:
, co w sensie thety daje nam:
.

co do zadania z gwiazdą:
gwiazda spinająca to taki podgrf grafu który jest gwiazdą i zawiera wszystkie wierzchołki grafu
Inaczej jest to drzewa spinające będące gwiazdą (dla ścisłości gwiazda to graf mający jeden wierzchołek stopnia n-1, połączony z n-1 wierzchołkami stopnia 1)
czyli de facto starczy sprawdzić ile jest wierzchołków, które łączą ze wszystkimi pozostałymi, czyli ile jest wierzchołków stopnia n-1  (n w całym moim wywodzie oznacza liczbę wierzchołków w grafie) 

---