Pseudokod

Odpowiedz Nowy wątek
2019-09-08 15:11
0

Cześć, mam zadanie na algebrze, żeby w pseudokodzie zapisać dane permutacje:

  • x^2y^-1

  • x^-1y^3

  • x^ −1 y^−2

Dla podpuktu drugiego to wygląda tak:

for i=1 to n
z[ x [ i ] ] <- i

for i=1 to n 
s[ i ] <- y[ y[ y[ i ] ] ] 

for i = 1 to n 
w [ i ] <- z[ s [ i ] ]

Mógłby ktoś mi wytłumaczyć w prosty sposób - krok po kroku - jak to działa?

EDIT: Chodzi o permutacje z tego filu (około 9 minuty) (

).
Treść zadania: Proszę napisać algorytm, który dla danych permutacji x, y należących do Sn (przedstawionych w zwykły sposób w odpowiednich tablicach) oblicza permutację x^-1y^-2.

edytowany 1x, ostatnio: Nindzia, 2019-09-08 15:46
W jakim sensie permutacje, co te zapisy oznaczają, jak np. : x^2y^-1, co to za operatory w tym pseudokodzie, jak: <-, z[ x [ i ] ]? - lion137 2019-09-08 15:36
Objaśnij co to znaczy x^-1y^-2? - lion137 2019-09-08 15:58

Pozostało 580 znaków

2019-09-08 16:06
0

@lion137: x do potęgi -1 oznacza permutację odwrotną a y do potęgi -2 oznacza permutację odwrotną i jeszcze podniesioną do potęgi 2

I chodzi o pseudokod algorytmu ich złożenia ((x^(-1)) o (y^(-2)))? - lion137 2019-09-08 16:21

Pozostało 580 znaków

2019-09-08 16:22
0

@lion137: mnożenia

Przedstawionych w zwykły sposób na odpowiednich tablicach, znaczy, że to są takie macierze 2 x n? - lion137 2019-09-08 16:29

Pozostało 580 znaków

2019-09-08 16:39
0
Nindzia napisał(a):

@lion137: mnożenia

@lion137: jakbym wiedział to bym nie pytał o to na forum ;)

Jeżeli nie Rozumiesz tematu zadania, to skąd my mamy wiedzieć? Zapytaj autora, niech Ci dokładnie wytłumaczy. - lion137 2019-09-08 16:44
@lion137: może dyskutuj w odpowiedziach, będzie łatwiej czytać. - Silv 2019-09-08 17:08
W sumie tak, ale to on wylazł z komentarzy do postów, mogliśmy to załątwić ciągiem komenytarzy pod pierwszym postem:) - lion137 2019-09-08 17:11
Nie marudź, tylko Ty zacznij robić lepiej. ;) - Silv 2019-09-08 17:12
PS. "Zacznij lepiej" w sensie: skoro już jest, jak jest. - Silv 2019-09-08 17:13

Pozostało 580 znaków

2019-09-08 18:21
2

Nie ma pewności, jak te permutacje przedstawić, ale temat dość ciekawy. Po pierwsze primo, nie ma sensu "ciągnąć" za sobą tego rzędu indeksów, logicznie jest przedstawić permutację jako tablicę o długości n:
[3, 2, 1] - to oznacza 1 -> 3, 2 -> 2, 3 -> 1.
Po drugie primo, najlepiej jest stworzyć dwie funkcje: mnożącą permutacje i odwracającą permutację; wtedy te różne wyrażenia, będzie można z tych dwóch skomponować:

fun mult_perm(x, y):
    out_perm = []
    for i = 1 to length(y):
        out_perm.append(x[y[i]])
    return out_perm

fun rev_perm(x):
    out_perm = [0] * length(x)
    for i = 1 to length(x):
        out_perm[x[i]] = i
    return out_perm

fun sol1(x, y):
    return mult_perm(mult_perm(x, x), rev_perm(y))

Rozwiązanie pierwszego zadania wygląda akurat tak (funkcja sol1). out_perm.append(...) w pierwszym, to dodanie elementu do końca tablicy. Proof of concept w Pythonie (Wciśnij run). Permutacja najpierw pomnożona przez siebie, potem odwrócenie permutacji identycznościowej, to ta sama permutacja, co tłumaczy wynik trzeciego print. Tutaj permutacje nie idą od 1 do n, tylko od 0 do n - 1.
https://repl.it/repls/NecessaryGlamorousPi


edytowany 1x, ostatnio: lion137, 2019-09-08 18:22

Pozostało 580 znaków

2019-09-08 18:27
0
lion137 napisał(a):

Nie ma pewności, jak te permutacje przedstawić, ale temat dość ciekawy. Po pierwsze primo, nie ma sensu "ciągnąć" za sobą tego rzędu indeksów, logicznie jest przedstawić permutację jako tablicę o długości n:
[3, 2, 1] - to oznacza 1 -> 3, 2 -> 2, 3 -> 1.
Po drugie primo, najlepiej jest stworzyć dwie funkcje: mnożącą permutacje i odwracającą permutację; wtedy te różne wyrażenia, będzie można z tych dwóch skomponować:

fun mult_perm(x, y):
  out_perm = []
  for i = 1 to length(y):
      out_perm.append(x[y[i]])
  return out_perm

fun rev_perm(x):
  out_perm = [0] * length(x)
  for i = 1 to length(x):
      out_perm[x[i]] = i
  return out_perm

fun sol1(x, y):
  return mult_perm(mult_perm(x, x), rev_perm(y))

Rozwiązanie pierwszego zadania wygląda akurat tak (funkcja sol1). out_perm.append(...) w pierwszym, to dodanie elementu do końca tablicy. Proof of concept w Pythonie (Wciśnij run). Permutacja najpierw pomnożona przez siebie, potem odwrócenie permutacji identycznościowej, to ta sama permutacja, co tłumaczy wynik trzeciego print. Tutaj permutacje nie idą od 1 do n, tylko od 0 do n - 1.
https://repl.it/repls/NecessaryGlamorousPi

No właśnie problem jest w tym, że nie sposób to przedstawić w formie działającego programu komputerowego - bo z tym też raczej nie miałbym problemu, tylko jestem na 3 roku studiów informatyki (zaczynam ostatni, 7 semestr w październiku) i niedługo mam poprawkę waruna z algebry i muszę go zdać, a takie zadanie to jedno z wielu, które najprawdopodobniej się pojawi, napisać w pseudokodzie na kartce algorytm, który liczy takie permutacje. Na szczęście już mniej więcej obadałem temat i chyba rozumiem. Jakby ktoś miał coś wartościowego do dodania to proszę się nie krępować. @lion137 - mimo wszystko dzięki za pomoc.

Listing, który podałem jest najbardziej pseudo pseudokodem:), jaki sobie mogę wyobrazić. - lion137 2019-09-08 18:29

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0