🚀 go-pugleaf

On Aug 8, 2:39 pm, "Remek" <wias...@neostrada.pl> wrote:

> mam napisać program liczący ilość kombinacji k znaków
> ze zbioru n znaków. Może to być np. hasło dostępowe do
> czegoś.[...] Jak nazywa sie omawiane zagadnienie?
> Mutacja, permutacja, wariacja ...?

Jak go zwał tak go zwał. Uczyłęm tych rzeczy na
uniwerkach, ale gdy student zadał mi podobne
pytanie ("Mamy użyć permutacji czy kombinacji?),
to opowiedziałem klasie stary dowcip żydowski:

dwóch bardzo inteligentnych przyjaciół ukończyło
biznesową szkołę z samymi najwyższymi stopniami
i wuróżnieniami, po czym założyli własny interes.
I o dziwo nie szło im. Więc za psie pieniądze sprzedali
ten interes trzeciemu kledze, głupiemu, bez wyksztalcenia.
I o dziwo, ich przyjaciel prosperował, biznes kwitł
i przynosił mu opgromne dochody. Ci dwaj wspaniele
mądrzy pytają głupiego przyjaciela:

 -- słuchaj, my jesteśmy inteligentni, wykształceni
i w ogóle cud świata, a Ty głupi. Jak to jest, że ci
tak dobre idzie.

Na co tamten:

 -- słuchajcie, wy jesteści wspaniale inteligentni
i wszystko wiecie, macie w małym palcu, a jestem
malutki, głupi, więc skromny, nie mam wielkich
wymagań - jeden procent zysku mi wystarcza,
z jednego dolara robię dwa, to wszystko, jeden
procent mnie zadawala.

Muszę z przyjemnością powiedzieć, że mój
business class docenił historyjkę, i przynajmniej
chwilowo już mnie nie męczył zbędnymi
pytaniami.

Z tego co piszesz wynika, że chodzi ci po
prostu o wszystkie funkcje z k-elementowego
zbioru, powiedzmy  {0 1 ... k-1}  w n-elementowy
zbior, powiedzmy  A,  gdzie  A jest jakimś tam
"alfabetem" czyli zbiorem znaków. Mońa też
powiedzieć (na jedno wychodzi), że rozpatrujesz
zbiór wszystkich ciągów długości  n,  o wyrazach
ze zbioru n-elementowego  A, albo że chodzi o
k-literowe napisy (słowa, strings), gdzie znowu
za alfabet służy n-elementowy zbiór znaków, A.

> Znalazłem wzór:
>
> K = n do potęgi k

Slusznie!  Dopuszczasz przy tym napisy,
w których występuje mniej niż k różnych
znaków. Powiedzmy dla  k = 10  dopuszczasz
napis:

    r r r r r r r r r r

(gdy litera  r  należy do  A).

> gdzie:
>
> K  - ilość mozliwych kombinacji
> k  - podzbiór znaków hasła
> n  - zbiór znaków jakie mamy do dyspozycji/użycia

Wyrażasz się jak ten trzeci kolega (czyli
niepoprawnie); byleś z jednego dolara robił dwa.

>
> Taki wzór jest np. tutaj:
>
> http://matma4u.akcja.pl/twierdzenia/kombinatoryka/k.htm
>
> Chodzi o ten ostatni na wariacje z powtórzeniami.
> Wg tego wzoru wychodzą
> astronomiczne liczby. Np. ilość możliwych
> kombinacji 4-ro znakowego hasła ze
> zbioru 30 znaków wychodzi 810 000,

Tak.

 > a dla 10 znakowgo to już astronomiczna
> liczba 651 044 743 906 304.
>
> Zakładając, że komputer wykona 1000 operacji
> sprawdzających na sekundę, złamanie takiego
> hasła metodą brute force zajmie mu 20 644 lata.
>
> Czy popełniam błąd w rozumowaniu?

Zdaje się, że rozpatrujesz złamanie na 100%
w takim czasie.  Ale ile czasu potrzeba, żeby
mieć szansę 5%?  Czy 5% Ci nie przeszkadza?
Wciąż daje spać spokojnie?

Ponadto naprawdę w całą sekundę dzisiejszy
komputer sprawdzi tylko 1K = 1000 przypadków,
a nie 10M?

Pozdrawiam,

    Włodek