Jak nauczyć się rozwiązywać zadania algorytmiczne typu codility , hackerrank itp

0

Witam , jaka wiedza jest potrzebna do rozwiązywania takich zadań rekrutacyjnych i nie tylko z algorytmów ? Czy potrzeba do tego wiedza z matematyki np rachunek prawdopodobieństwa/kombinatoryka ? Czy są jakieś kursy / książki które pokazują jakieś metody rozwiązywań zadań algorytmicznych bo jako początkujący jak czytam takie zadanie to nie wiem nawet od czego zacząć .

2

Oczywiście to zależy od typu zadania.
Czasem faktycznie kombinatoryka się przydaje, ale w bardzo podstawowym zakresie, podobnie jak matematyka ogółem.

Bardziej przydatna jest wiedza o podstawowych algorytmach matematycznych (NWW, NWD, sito Eratostenesa etc.), sortowaniach itp. Poleciłbym także poznanie struktur danych (listy, kopce, drzewa, wektory, grafy).

Materiały z PWr po polsku:
http://www.zio.iiar.pwr.wroc.pl/sdizo.html

Zwłaszcza:

http://www.zio.iiar.pwr.wroc.pl/sdizo/Wyklady/sdizo_2018_wyklad_3.pdf
http://www.zio.iiar.pwr.wroc.pl/sdizo/Wyklady/sdizo_wyklad_5_2019.pdf

Obcojęzyczne:
https://algorithms.openmymind.net/
https://fiftyexamples.readthedocs.io/en/latest/algorithms.html

I oczywiście - wspomniany Cormen ;)
http://web.ist.utl.pt/~fabio.ferreira/material/asa/clrs.pdf

0

Czy w tych materiałach mówią jak wpadać na rozwiązania czy tylko opisują istniejące algorytmy ? Czy może chodzi o to że do robienia tych zadań wykorzystuje się ogólnie znane algorytmy z ksiażek ? Sorry za laickość moich pytań.

0

Głównie pokazuje się istniejące algorytmy - inaczej dostajesz narzędzia do rozwiązywania swoich problemów.
Z drugiej strony linki "obcojęzyczne" mają proste przykłady, polecam poczytać.

1
trzmiel napisał(a):

Czy w tych materiałach mówią jak wpadać na rozwiązania czy tylko opisują istniejące algorytmy ?

"Wpadanie na rozwiązania" przychodzi z doświadczeniem, podobnie jak w rozwiązywaniu normalnych zadań z matematyki. W książkach podanych wyżej (w szczególności "Zaprzyjaźnij się z algorytmami" Tomasiewicza) masz obrazowe przykłady, które co pomogą.

Czy może chodzi o to że do robienia tych zadań wykorzystuje się ogólnie znane algorytmy z ksiażek ? Sorry za laickość moich pytań.

Tak, tak samo jak do rozwiązywania zadań tekstowych z matematyki wykorzystuje się ogólne metody, trzeba tylko przełożyć rozwleczony tekst o Bajtazarach w Bajtocjii na ściśle zdefiniowany problem i zaaplikować odpowiednia matematykę/algorytm.

2
  1. Znajomość istniejących algorytmów sprawia ze nie wymyślasz koła na nowo. Problemy algorytmiczne są raczej "unikane", ale mimo wszystko często wymagają użycia takich rzeczy jak mapa, set czy też posortowania czegoś itd. Te rzeczy nie są "celem" tylko środkiem do osiągnięcia celu i trzeba je znać i rozumieć
  2. Znajomość istnejących algorytmów pokazuje ci pewne "metody", jak dziel i zwyciężaj czy programowanie dynamiczne i zachłanne. Jak zobaczysz na czym to polega na przykładzie jakiegoś istniejącego algorytmu, łatwiej będzie potem "wpaść" na to w nowym problemie.
0

Obstawiam, że po prostu trzeba najwięcej robić tego typu zadań, ćwiczyć się w ich robieniu i tyle (są przykładowe zadania na Codility, które można sobie robić - każdego tygodnia jest inne https://app.codility.com/programmers/challenges/ ), w razie potrzeby coś tam doczytując na SO, Wikipedii czy w innych źródłach (ale jednak to na czas jest, więc trzeba i tak wyćwiczyć pewne rozwiązania, żeby umieć potem podobne zaklepać w ciągu kilku minut).

Czy są jakieś kursy / książki które pokazują jakieś metody rozwiązywań zadań algorytmicznych

Jest taka książka "Cracking the code interview", ale nie czytałem.

Poza tym są też książki o algorytmach (ja coś Knutha przeglądałem kiedyś w bibliotece).

2

Jak się nauczyć robić leki na nowe choroby?
Trzeba się dowiedzieć jak robiono leki na stare choroby i kombinować/eksperymentować z nabytą wiedzą.
A przede wszystkim, przestudiować jak działa choroba, na którą lekarstwo opracowujemy.

0

Myślę, że powinieneś zobaczyć jakie tam są zadania, czy wszystko trzeba robić z pamięci i czy właśnie takie zadania są ci potrzebne? Bardzo trudne zadania polegają na znajomości zaawansowanej matematyki i algorytmów heurystycznych. A czy takie proste zadanie zrobisz w godzinę?
Dwie liczby, A i B, są tworzone z cyfr od 0 do 9, używając każdej cyfry tylko raz, to znaczy że obie liczby nie mają tych samych cyfr. Sześcian jednej z liczb jest równy kwadratowi drugiej, tj. A do kwadratu = B do sześcianu. Jakie są te liczby?

0

ostatnio zaczałam robic pierwsze 100 zadan w project euler. Jedno z nich mnie rozwala: dla n=10, jest 5 mozliwych podzbiorów liczb pierwszych mniejszych od 10, których suma daje 10. Trzeba znalezc n, dla ktorego liczba takich podzbiorów wynosi 1000. Oczywiscie zaczalam od metody brute force

def allCombinations(lst,n):
	t=[]
	for i in range(2, n//2+1):
		nElementhPermutations= list(itertools.combinations_with_replacement(lst, i))
		for tup in nElementhPermutations:
			if sum(tup)==n: t.append(tup) 
	return t

Ale algorytm zdycha z MemoryError dla n=39, dla których jest ok 12 licz pierwszych mniejszych od n i 272 znalezione podzbiory ktorych suma wynosi n

1

list(itertools.combinations_with_replacement(lst, i)) po co? o_o Nie możesz lecieć po generatorze tylko musisz z tego robić listę w pamięci? Bez sensu. Wywal to list() i też będzie działać i nie wywali się z braku pamięci. Niemniej to raczej słabe rozwiązanie. Inna sprawa ze źle nazywasz zmienne bo wcale nie masz tam żadnej permutacji ;]
Nie widze u ciebie w ogóle żadnych liczb pierwszych, to raz. Dwa, masz tu tzw problem subset sum -> https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

1

Z tego co zauważyłem patrząc na wiele rozwiązań na projecteuler, prawie 100% zadań NIE MA być rozwiązane przez brute force tylko ze znajomością wzorów matematycznych, które zmniejszają zbiór danych do przeszukania milion razy. Dlatego trudno to nazwać portalem informatycznym, jest zdecydowanie matematyczny.

Ostatnio wziąłem się za uczenie nowych rzeczy. Mamy tabelkę 6x6 wypełnioną liczbami i mamy te liczby ustawić inaczej żeby znaleźć maksimum pewnej funkcji, której wartość jest określona położeniem tych liczb w tabelce. Gdybyśmy chcieli przestawiać liczby przez permutacje, to mamy 36! silnia przestawień (analogiczne zadanie do problemu komiwojażera). Ani za milion lat by się to nie udało. Ale w ciągu kilku minut można znaleźć niezłe rozwiązanie algorytmem genetycznym, bardzo łatwym do nauczenia. Tylko kilka godzin programowania i około 500 linii kodu źródłowego.

1

Z tego co zauważyłem patrząc na wiele rozwiązań na projecteuler, prawie 100% zadań NIE MA być rozwiązane przez brute force tylko ze znajomością wzorów matematycznych, które zmniejszają zbiór danych do przeszukania milion razy. Dlatego trudno to nazwać portalem informatycznym, jest zdecydowanie matematyczny.

A ty myślisz ze jak wygląda praca przy przetwarzaniu informacji? Ty myślisz ze programiści bezmyślnie klepią bruty? :D :D
Informatyka to nauka o przetwarzaniu informacji i jest bardzo silnie oparta na matematyce.

0
Shalom napisał(a):

A ty myślisz ze jak wygląda praca przy przetwarzaniu informacji? Ty myślisz ze programiści bezmyślnie klepią bruty? :D :D
Informatyka to nauka o przetwarzaniu informacji i jest bardzo silnie oparta na matematyce.

Po co mi piszesz obraźliwie bezsensowną odpowiedź która nie jest mi potrzebna i o którą nie pytałem???

Moja odpowiedź była skierowana do dziewczyny która myślała że te zadania rozwiąże przez brute force, więc jej mówię, że tą metodą zadań z tego portalu nie rozwiąże i to będzie strata czasu. Ktoś na swojej stronie opublikował metody rozwiązywania wszystkich tych zadań i podał też odpowiedzi. Prawie we wszystkich przypadkach okazuje się że jest wzór matematyczny, często z matematyki wyższej, który liczy od razu wszystkie wartości tak, że można to ręcznie na kartce papieru policzyć.

Poza tym zagadnienie ma charakter jedynie naukowy. 99% zleceń na programowanie nie dotyczy takich zadań. Zlecane do wykonania za wynagrodzeniem są serwisy internetowe wyświetlające proste rzeczy z baz danych.

2

Po co mi piszesz obraźliwie bezsensowną odpowiedź która nie jest mi potrzebna i o którą nie pytałem???

Nie piszę ci, tylko ogólnie do świata. Bo wielu ludziom nadal wydaje sie że da się robić informatykę bez matematyki. I klepią te swoje formatki w htmlu i generic CRUDy i myślą że to jest informatyka.

Poza tym zagadnienie ma charakter jedynie naukowy. 99% zleceń na programowanie nie dotyczy takich zadań. Zlecane do wykonania za wynagrodzeniem są serwisy internetowe wyświetlające proste rzeczy z baz danych.

Faktycznie, za miskę ryżu na umowie o dzieło trudniej o jakiejś bardziej skomplikowane zagadnienia :D A potem jest płacz gdzie moje 15k które mi obiecywali na bootcampie?!.

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