Dnia Sun, 14 Oct 2012 00:41:44 +0200, bartekltg napisal:

> W dniu 2012-10-13 16:58, Edek Pienkowski pisze:
>> Dnia Sat, 13 Oct 2012 16:13:55 +0200, bartekltg napisal:
>>
>>> W dniu 2012-10-13 16:13, Edek Pienkowski pisze:
>>>
>>>>
>>>> Peephole - o ile wszyscy rozumieją przez to to samo - to zbiór drobynch
>>>> optymalizacji kodu przeprowadzanych na niewielkim fragmencie kodu, stąd
>>>> przynajmniej jest nazwa. Jest to optymalizacja obecna we wszystkich
>>>> optymalizujących kompilatorach, niektóre robią ją kilka razy tak
>>>> dla oczyszczenia, bo po to głównie jest.
>>>
>>> Ok, to wiem, ale... przecież to nie na temat.
>>>
>>> Pytamy się, co byś polecił na zapoznanie się z algorytmiką,
>>> a ty odpowiadasz 'szukanie wąskich gardeł'. To jest bardzo
>>> pożyteczne i rozwijające zajęcie, ale algorytmika jest o czym innym.
>>
>> Shite. To powiedz mi, o czym jest algorytmika.
>
> 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.

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.

> Obok jest dyskusja o qsorcie. Na takiej algorytmice student na dzien
> dobry ląduje z qsortem. Ma załapać ideę. Robimy podział
> porządkujący, i odpalamy rekurencyjnie.
> Ma rozumieć, dlaczgo to prowadzi do szybkiego posortowania.
>
> Od tego, czy będzie tam warunek sprawdzający zakres, czy
> student sobie poradzi bez niego, ważniejsze będzie
> zrozumienie niezmienników.

A moim zdaniem musi go spróbować zaimplementować sam wcześniej.
Albo coś podobnego. Ucz małpę niezmienników ;)

>> Ten sam problem: nie wiem - jak widać - co to jest algorytmika. Przynajmniej
>> ta "czysta". Nie potrafię ekstrapolować z sorta, jedynego w takim razie
>> przykładu, że to algorytmika.
>
> 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.

>> Widziałem prace z obu tematów w kwestii rozwiązywania problemów NP-hard
>> i uważałem to za algorytmikę, ale już teraz nic nie wiem.
>
> Wiesz, ludzie pisząc prace z analizy atakują równie trudne problemy.
> Ale jednak analiza na pierwszym roku to całki i różniczki.
> I to całki i różniczki, czyli 200-300 letnie podstawy będą
> potrzebne inżynierom, nie najnowsze wyniki w sprawie istnienia
> rozwiązań równań naviera-stokesa;)
>
> Chociaż masz trochę racji. Mówimy na to popularnie
> algforytmika, a takin MIM nazywa to algorytmi
> i struktury danych. Algorytmika to osobny przedmiot,
> semestr później i tam robi się druga polowę Cormena
> (czyli właśnie m.in wspomina o tych zawansowanych
> problemach z klasami obliczalnosci).

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.

>>> Ok, nieważne
>>
>> Zazwyczaj nie gadasz bzdur, więc moze czegoś się dowiem.
>
> :)
> Ale ostrzegam, ja nie jestem prawdziwym informatykiem.

Przyszywanym bardziej niż ja nie jesteś. Ale jakoś dajesz radę?

>> Przeczytałem wikipedię polską i angielską - poza tym, że polska mówi o
>> etymologii z XIX wieku a angielska o XII w. i nadużyciu słowa w XIX - nic
>> się nie dowiedziałem. Znalazłem tylko tą definicję z "... worker/solver
>> moving around a problem vector space ...", taką bliską sercu.
>
> Trochę nam chyba ucieka dyskusja. Ustalać definicji algorytmiki
> się nie podejmuję. Pozostańmy przy tym, z czym zapoznać studenta
> w ramach takiego przedmiotu.
>
> Ja uważam, że powinno się ich nauczyć metod pomocnych
> w atakowaniu problemów niesprowadzających się wprost
> do 'wpakuj do kontnera i posortuj'.

Dajesz mi argumenty?

> 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,
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).

> 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
mam co innego na głowie, i stwierdzam, że w tej kwestii
tak było nie tylko dzisiaj, ale dotychczas zawsze. Union
się mi prawdopodobnie zdarzył.

Jest masę różnych algorytmów, o których człowiek nie wie.
Ja się na przykład kiedyś natknąłem na takie: jak
zrealizować w systemie rozproszonym decyzję, który node
ma największą liczbę mając do dyspozycji atomiczne
rejestry (inne prace pokazały niezawodną implementację)
i Omegę, która daje każdemu node'owi pewną informację
na temat tego, czy pozostałe node'y jeszcze dychają.
Komunikacja jest typu "messaging", algorytm ma się
skończyć w skończonym czasie. Problem polega na
znalezieniu ściśle słabszej wyroczni (słabsza
to taka, że z silniejszej da się wyprowadzić słabszą;
"ściśle", że odwrotne jest niemożliwe). Niektórych
Omeg nie jestem w stanie odtworzyć tak były pokręcone,
a co tu mówić o wymyślonych algorytmach. A, i mają zastosowanie,
chociaż nie wszystkie.

"My point is": można dać studfentowi kilka popularnych
algorytmów, i tak użyje części a inne musi albo
znaleźć, albo wymyśleć samemu. Jednemu wystarczy to
za wstęp do algorytmów, innemu nie, i różnica nie
polega na wiedzy tylko umiejętnościach.

--
Edek