Dnia Sun, 14 Oct 2012 02:29:16 +0200, bartekltg napisal:

> W dniu 2012-10-14 02:01, Edek Pienkowski pisze:
>
>>> Zawsze myslalem o tym, jako o nauce projektowania algorytmów.
>>> Ale nie mikroptymalizacji, tylko takim bardziej ogolnym.
>>
>> Po pierwsze, kompilatory robią masę "mikrooptymalizacji".
>> Implementuje się je raz.
>
> Ale pisanie kompilatora to zdecydowanie nie jest to, czym
> się student pierwszego roku powinien zajmować:)

Na MIT zajmowali się tym na pierwszym roku. Ale oni to
truskawki cukrem, prawda?

>> No i to są algorytmy, niektóre dość proste, więc to jest
>> wstęp do algorytmiki, jeden z możliwych. Uczy wszystkich
>> podstawowych elementów dorzucając model procesora, którego
>> trzeba użyć. RAMu i cache może nie mieć, ze dwa rejestry
>> i proste fikcyjne ALU, pełny minimalizm.
>
> To tu się po prostu nie zgadzamy. Zwykłym potrzeba
> znaczniej bardziej tego sortowania niż babrania się
> w asm. Zwłaszcza na początku.

Nikt nie mówi o babraniu się w asm, tylko w języku
funkcyjnym z modelem asm, takim że pięciolatek by
zrozumiał. To czego 5-latek by nie zrozumiał to język,
sekwencyjność, przekształcenie nie naruszające kodu
w żadnym z dośc nieograniczonej liczby przypadków,
struktur danych opartych o parę (Scheme...) i parę innych
tego typu rzeczy. Sam fikcyjny asm to akurat pikuś.

> Znam paru dobrych informatyków siedzących 'w przemyśle',
> znam paru, ktorzy poszli w teorię. Na takim przedmiocie
> JAJO, gdzie to właśnie mieli bawic się asm i bebechami
> systemu poradzili sobie. Ale assembler jest im w codziennej
> pracy niepotrzebny. Wiedza wyniesiona z analizy sortowania
> - tak.

Nie wiem jaką wiedzę się z tego wynosi, ale na MIT uważali
bardzo długo, że właściwą na wstęp. Jedyne co bym w tym
zmienił kopiując rozwiązanie to dostosował poziom trudności.

>> A moim zdaniem musi go spróbować zaimplementować sam wcześniej.
>> Albo coś podobnego. Ucz małpę niezmienników ;)
>
> A co to za rożnica? Nie wymyślisz sam większośći algorytmów.
> Często trzeba podsunać pomysł.
>
> BTW, ja też przed studiami 'programowałem'. Bawilem sie pascalem,
> C, C++. 16 bitoiwym assemblerem. Nawet na olimpiade
> informatyczną się w liceum przejechałem.
>
> A na studiach przeszedłem się po sąsiedzku na parę semestrów
> różnych 'metod programowania' czy ASD i zrozumiałem,
> jaką kaszanę odwalałem;)

Ja tak czasami mam do dzisiaj. Przyzwyczaiłem się i niech się
nic nie zmienia w tym względzie, lubię nawyki ;)

>>> Myślę, że tu nie chodzi o sorta, tylko o nauczenie pewnego
>>> zestawu narzędi i sposobu myślenia _przydatnego_ przy
>>> projektowaniu algorytmów.
>>> Podstawy analizy zlozonośći, myślenie o niezmiennikach,
>>> ale też zwracanie uwagi na sytuacje krańcowe
>>> ("Z pętlą jest jak z lotem samolotem. Najtrudniejszy jest
>>> start i lądowanie. Sam lot jest stosunkowo prosty"//Diks;))
>>
>> No, nawet myśle podobnie, ale wciąż nie kumam o co chodzi
>> z tym sortem.
>
> N qsorcie łumaczysz rekurencję. 'dziel i zwyciezaj".
> Na takim insertionsorcie niezmienniki, pętle.
> Porównując oba masz ilustrację złożonośći obliczeniowej.
>
> Są to proste obrazki, przykłady do pojęć.
>
> Można to zastąpić innymi, bardizej wymyslnymi algorytmami,
> ale nijak nie da się tego zastąpić rzeźbieniem w asm
> i peepholami. To po prostu inne zagadnienia.
>
> Jedne cwiczenia na sortowanie można poswiecic.

A co na tych ćwiczeniach? Bo na próbowanie wymyslenia sorta
już jest trochę za późno, a reszta to wałkowanie danej już
wiedzy - nadaje się na utrwalenie, ale dużo więcej z tego
nie wyniknie.

>> Mi nie chodzi o to "czy uczyć całki", ale "jak uczyć całki". To samo
>> w kwestii algorytmów, czy bądźmy szczerzy: programowania.
>
> A ja mam wrażenie, że pod jak uczyć całek mówisz
> 'uczmy się algebry'. Algebry tez się trzeba nauczyć,
> ale na przedmiocie w sali obok. Teraz robimy całki.
> Rozumiesz mnie?

Nie. Ale już o tej porze średnio kojarzę, chyba się
pogubiłem w analogiach.

>>> Powiedzmy, okolice średniej trudności z tego:
>>> http://potyczki.mimuw.edu.pl/user.phtml?op=zadania
>>
>> Przejrzałem trzy. Wieże akurat nie są problemem, bo gram
>> szachy. Ten z odwiedzaniem miast ciekawszy. Ten z drzewem
>> jako "<bardzo ciekawa definicja>" też da się sprowadzić
>> do trywialnego. Wszystkie uczą rozwiązywania problemów,
>
> Już nie pamiętam. Były tam i trudne. Tzn ja nie wymeśliłem
> sprawnego sposobu, a z matmy dośc dobry jestem.

Drzewo:
Znalezienie wszystkiego, co da się zamienić jest nie takie
trudne. Potem mnoży sie ilość możliwych zamian przez siebie,
i tam jest jakieś modulo, może cos w 15 sekund mi się zgubiło
po drodze. Było jednym z ostatnich i wyglądało na zagmatwane.

>> to takie logiczne zagadki, a z narzędzi informatycznych
>> nadają się na "napisz coś co robi co wymyślisz". Niezłe,
>> ale spotkałem lepsze: durny peephole, który wielkim problemem
>> logicznym nie jest. Tak z innego poziomu: peephole uczy
>> programowania na przykładzie przekształcania programu,
>> przy okazji ucząc prostej optymalizacji (znowu: mało
>> kto będzie pisał kompilator, więc jest bardziej
>> abstrakcyjne niż te szachy).
>
> Tak, ale to są inne zagadnienia. Trzeba uczyć i jednych i
> drugich. Nie jednych zamiast drugich.

Sudoku tez rozwija i też je warto podłubać w gazetce,
a nie uczy się na tym programowania. Jedyną różnicą
pomiędzy tym linkiem a sudoku jest to, że sudoku mało kto
stosuje w celach nauczania (póxniej dopiero ktoś wykazał
jakieś właściwości sudoku zawsze prawdziwe, ale tylko
zerknąłem).

>>> No i oczywiście uświadomienie istnienia pewngo pakietu
>>> znanych algorytmów. Takie find-union czy drzewa
>>> przedziałowe przydają się czasem, a w STL ich nie ma.
>>> Pewnie są w boost, ale trzeba wiedzieć, czego szukać.
>>
>> Jak będę ich potrzebował, to będę o tym wiedział. Na dzisiaj
>
> Nie, jeśli nie jesteś świadomy istnienia czegoś, to
> znacznie utrudnia znalezienie tego.
> To pułapka wspolczesnie modnego poglądu na edukację,
> by nie uczyć faktów.

Tak poważnie, wszyscy te kilka modnych poglądów przekręcają
po swojemu. Nikt nie atakuje przekazywania wiedzy, jedynie
część wiedzy trzeba odpuścić, żeby zmieścić umiejętności.
(sorry za drukowane, ale prościej się nie da. W odpowiedzi
na post Michoo masz pełną wersję, w wersji Edziowatej).

--
Edek