Nazwy Algorytmów

[tedew]

witam
mam pewną prośbę , aby ktoś spróbował mi napisać co podane algo robią i jaki to jest typ algo ( deterministyczny cz niedetreministyczny )

1 algo
(? . Dany jest graf G o n wierzchołkach , Co jest wynikiem jego działania, czyli kiedy ten algorytm drukuje 0, a kiedy drukuje 1 ?? )


begin
{a jest tablicą a[1..n]}
a:=permutaja-losowa(n); {n jest liczbą wierzchołków w grafie G}
{powyższa instrukcja umieszcza w tablicy a losową permutację liczb 1, 2, ..., n}
b:=true; i:=1;
while (i < n) and b do begin
if {a[i],a[i+1]} nie jest krawędzią w grafie G then b:=false;
i:=i+1
end;
b:=b and ({a[n],a[1]} jest krawędzią w grafie G);
if b then write(1) else write(0)
end.



2 algo
(. Dany jest graf G = (V, E) o n wierzchołkach , Co jest wynikiem jego działania, czyli kiedy ten algorytm drukuje 0, a kiedy drukuje 1 ?? )

begin
read(k); {k jest parametrem działania tego programu}
wylosuj k-elementowy podzbiór W ze zbioru wierzchołków V;
b:=true;
for każdego i należy do W do
for każdego j należy do W do
if {i, j} Ď E then b:=false;
if b then write(1) else write(0)
end.


3 algo
(. Dana jest liczba naturalna n, Co jest wynikiem jego działania, czyli kiedy ten algorytm drukuje TAK ? )

begin
read(n);
k := random(n); l := random(n);
{Procedura random(n) generuje losową liczbę naturalną z przedziału 2 i n}
if k*l = n then print(***8216;TAK***8217;)
end.

pozdro

[pawelblu]

1) jezeli kazdy element (wierzcholek) tej permutacji a, oprocz ostatniego jest polaczony krawedzia z elementem po nim nastepujacym oraz jezeli ostatni element jest polaczony krawedzia z pierwszym to bedzie 1 , wpp 0

2) jezeli przyjmujemy ze wierzcholek jest polaczony krawedzia sam ze soba, to 1 bedzie gdy wylosowalismy podzbior wierzcholkow tworzacych graf pelny ( 0 wpp )
jezeli przyjmujemy ze wiercholek nie jest polaczony krawedzia sam ze soba, to 1 bedzie wtedy i tylko wtedy gdy k=0 ( 0 wpp ).

3) random(n) losuje liczbe naturalna z przedzialu 0..n-1 - nie rozumiem o co chodzilo autorowi (szczegolnie patrzac na ten komentarz).

[tedew]

witam
@pawelblu
jesteś genialny wielkie dzięki - o to chodziło

pozdro

p.s.

a może wiesz co reprezentują te algo , chodzi o nazwe , np: kolorowanie grafów , znajdowanie najkrutszej drogi itp.

[pawelblu]

Nie wiem jakby mozna to ladnie nazwac

Zreszta trudno to jakos systematyzowac jezeli algorytmy opieraja sie na losowaniu

[tedew]

witam
poszukuje jeszcze algo i złożoność do takich zagadnien :
1 Badanie, czy dany ele-ment a należy do zbioru A (zbiór A ma n elemen-tów).
2 Kolorowanie grafu, za-wierającego n wierzchoł-ków
3 Znajdowanie najkrótszej drogi w grafie o n wierz-chołkach, którego połą-czenia są obciążone nie-ujemnymi wagami.
4 Kolorowanie grafu, za-wierającego n wierzchoł-ków, możliwie najmniej-szą liczbą kolorów.
5 Sprawdzenie, czy dana liczba n jest liczbą pierw-szą.

pozdro

p.s.
w książkach szukałem , nie znalazłem nietety tego

[pawelblu]

Napisany przez tedew

witam
poszukuje jeszcze algo i złożoność do takich zagadnien :
1 Badanie, czy dany ele-ment a należy do zbioru A (zbiór A ma n elemen-tów).
2 Kolorowanie grafu, za-wierającego n wierzchoł-ków
3 Znajdowanie najkrótszej drogi w grafie o n wierz-chołkach, którego połą-czenia są obciążone nie-ujemnymi wagami.
4 Kolorowanie grafu, za-wierającego n wierzchoł-ków, możliwie najmniej-szą liczbą kolorów.
5 Sprawdzenie, czy dana liczba n jest liczbą pierw-szą.

pozdro

p.s.
w książkach szukałem , nie znalazłem nietety tego

Ooo za duzo juz wymagasz

[tedew]

re
bo pozostało mi jescze tylko to i PGP i bede miał komplet PGP to se sam poradze ale algo to moja słaba strona

pozdro