Temat: Torgowi Programiści - Nauka programowania od podstaw

Masz rację, sorki. Poprawione ;).

Podpisuję się też pod większością tego, co napisał Zeimer. Dodam tylko, że języki logiczne wcale nie są takie bezużyteczne - znajdują spore zastosowania w dziedzinie sztucznej inteligencji i parserów/lekserów DCG (chociaż teraz pisanie parserów/lekserów zostało zautomatyzowane i do tego służy Bison i Yacc). Dla początkujących - to drugie zagadnienie dotyczy tworzenia własnych języków programowania. To kolejna, zajebiście interesująca dziedzina informatyki - jeżeli mój mózg na to pozwoli, chciałbym pisać magisterkę z tego tematu...

Programowanie funkcyjne zaś pokazuje pięknie świat - jak nasze konstrukcje myślowe potrafią się przełożyć na coś formalnego. W dodatku pokazują, ile rzeczy na świecie jest fraktalnych ("złożonych z samych siebie") - np. listę możemy wyrazić za pomocą elementu startowego i mniejszej listy. W Common Lispie np. lista:
To:
W matematyce ma to nazwę tzw. indukcji strukturalnej i to naprawdę fajna rzecz. I wcale nie jest trudna, tylko groźnie brzmi ;).

Została powołana grupa użytkowników "Torgowi Programiści". Rozmawiamy tam o różnego rodzaju wskazówkach do zadań, oraz o własnych "programistycznych wojażach". Wszystkich zainteresowanych proszę o pisanie bodajże do użytkownika Abe PW, aby zaprosił ich do grupy.

Pozdrawiam
Killavus

Co do użyteczności języków logicznych - zależy ona od tego, ile można zarobić na rozwiązywaniu problemów z domeny logicznej. Strzelam, że pisanie kompilatorów i parserów oraz sztuczna inteligencja nie są dochodowe, więc języki logiczne pozostaną raczej ciekawostką i obiektem badań.

Co do pracy magisterskiej - sam chciałbym się zająć algorytmami lub językami programowania. Jako, że algorytmy mają się dobrze, a uniwersalny i idealny język programowania dalej nie istnieje skłaniam się ku temu drugiemu.

Dodam jeszcze listę języków programowania, których radzę unikać: Objective-C, Visual Basic, Perl, Pascal, Delphi, Lisp (jeżeli już bierzemy się do FP to tylko Haskell).

@down
Moim zdaniem to co jest czynnikiem decydującym o wyborze języka jest elegancja, prosta oraz łatwość rozumowania o poprawności.

Co do Lispów... może jeszcze nie dorosłem do lubienia ich.

O ile z Lispem się nie zgodzę, to do języków funkcyjnych wartych polecenia polecam jeszcze SML (Standard ML - chyba jedyny język programowania na ziemi, który posiada formalną specyfikację semantyki ;)). Lisp wraca do łask z pomocą Clojure.

Co do dochodowości sztucznej inteligencji nie jest to wcale taka słaba dziedzina - systemy inteligentnych agentów do systemów klasy ERP to potężna kasa. LLVM to np. przykład pracy nad kompilatorami i lekserami, na który wyłożono naprawdę sporo hajsu i ludzie nad nim pracujący z pewnością mają godną płacę ;).

Tak z czysto formalnego punktu widzenia Haskell jest nawet złym językiem na początek programowania funkcyjnego - ciężko się wnioskuje o wydajności programów (trzeba zaprzęgnąć koindukcję, a to dosyć wysoka matematyka), ponad to ukrywa się wiele aspektów często spotykanych w czystym FP - np. obliczenia za pomocą kontynuacji nie istnieją w Haskellu (są zastąpione leniwością). Najlepszy kurs formalnego programowania, słynny kurs z MIT używa Scheme do nauki FP. To gorliwy i dynamiczny język funkcyjny.

Pozdrawiam
Killavus

Witam, programuje jako freelancer od prawie 6 lat, znam C++, C, Javę, PHP, Asma x86 , Asma PPC i SPU, Lua. Jeśli macie pytania dawać .

@Killavus
rozwiązanie zadań w c++ (jeśli można)
o krowie: http://ideone.com/gfOZRq //przy planszy 10x10 zdarzaja sie juz bledy - naprawa in progress
sito: http://ideone.com/L1ad0s
Oceńcie czy dobrze rozwiązane.
Zapewne te problemy dałoby się rozwiązać w prostszy sposób niż ja to zrobiłem, no ale cóż - jestem początkujący.
Mam nadzieję, że nie zepsuję nikomu zabawy swoimi rozwiązaniami :)

Zadanie o krowie jest źle. Sprawdź sobie taką planszę:
Twój algorytm wybierze tą ścieżkę:
A powinien wziąć tą:
Co do sita, wygląda ok, tylko jeden krok mnie zastanawia: //wypelnienie tablicy liczbami z zakresu(1,zakres) - po co to robisz, skoro i tak zaraz zamieniasz to na 0 wszędzie?

PS Taka technika, którą obrałeś przy rozwiązywaniu krów to tzw. strategia zachłanna - w ten sposób np. można wydawać resztę w automatach z napojami. W tym problemie jednak jest wymagane rozwiązanie dynamiczne - musisz sprawdzić wszystkie możliwe trasy w kolumnie, bo być może kiepska początkowo droga przerodzi się w cośbardzo dobrego.


Pozdrawiam
Killavus

Taa, niezła gafa. Już pracuję nad naprawą. Teraz dopiero widzę ile błędów xdddddddd
#edit
no właśnie, po głębszym zastanowieniu się też do tego doszedłem...
no to pierw spróbuję tą strategią zachłanną poprawnie wykonać, a potem zastanowię się nad rozwiązaniem dynamicznym
Dzięki za wskazówki ;)
#edit 2
http://ideone.com/gfOZRq
juz jest wersja poprawiona (nadal greedy)

Dobra, ja zrobię implementacje krówek w PHP . Generacja możliwych ścieżek , liczenie całkowitych sum i sortowanie, klucze w tablicy są X i Y w jednym bajcie ( po 4 bity na każdy, więc nie obsluguje więcej niż 8x8, jak ktos bedzie chcial to niech se zmieni xD ja oszczędzam pamięć lol ;_: poza tym, dla ciekawskich jak można wykorzystać operacje logiczne w programowaniu chciałem zastosować XD ) , mam prawie gotowe, pewno jutro wrzucę ;d

Super temat :D Aż sie ciepło na sercu robi widząc taki zapał do nauki. Programuje od 2 gim (teraz 1 rok studiów) i do dziś nie straciłem ani troche zainteresowania chociaż niektorzy ludzie (np moi prof) usilnie starają się mi to obrzydzić.

I pamiętajcie:
"Komputery są głupsze od ludzi. Programiści są głupsi od komputerów" P.Coelho

Co do funkcji podzielny - niestety, Twoja funkcja łapie także 2 i 4. Sprawdź to.

Co do sita, działa ono poprawnie, niestety - jest trochę wolne. Chodzi głównie o pętlę z k. Musisz oznaczyć tylko 2*x, 3*x, ... k*x. Czemu więc przelatujesz przez całą tablicę za każdym razem gdy znajdziesz liczbę pierwszą, zwłaszcza, że możesz to zrobić łatwo w programie, żeby odwiedzał tylko te liczby, co trzeba?

Tzw. asymptotyczna złożoność jest ta sama, co prawda (O(n^2)), ale warto pomyśleć jak w praktyce łatwo to przyspieszyć.

Nikt jeszcze nie zrobił dobrze zadania z krowami - zapraszam do zmierzenia się z tym problemem. Co więcej, zapraszam też do grupy - PW do użytkownika Abe pozwoli Wam do niej dołączyć! :)

Dorzucę kolejną wskazówkę, która w sumie jest rozwiązaniem jak dobrze się ją zrozumie.

Zauważmy jedną rzecz - mianowicie możemy rozpatrywać mniejsze względem liczby kolumn plansze.

Dla jednokolumnowej planszy rozwiązanie jest bardzo proste - wybieramy maksimum ze wszystkich liczb w kolumnie. Możemy sobie przepisać do pomocniczej tablicy całą tą kolumnę, wtedy będziemy mogli szybko odpowiadać na pytanie "najlepsza ścieżka z wiersza x".

Dla dwukolumnowej planszy możemy zauważyć, że skoro mamy już policzone dobre rozwiązanie dla pierwszej kolumny, to wystarczy skorzystać z tego rozwiązania. Aby uzyskać 'dobre' rozwiązanie dla dwukolumnowej planszy wystarczy popatrzeć na poprzednią kolumnę, po czym dodać maksymalną wartość z pól które są w poprzedniej kolumnie i możemy z nich dojść do aktualnego pola.

Przykładowo:
Rozpatrując x bierzemy wartość liczbową z pola x i dodajemy maksimum z 1 i 8. Czyli 8. Przy y patrzymy na maksimum 1, 8, 3. Przy z patrzymy na 8, 3.

A co z k-kolumnową planszą, gdy rozpatrujemy k+1 kolumnę?

W czwartek ogarniam następną część, niestety wcześniej mam kolokwium ;)

Pozdrawiam
Killavus

Próbowałem zrobić krowę i nie rozumiem jednej rzeczy w moim kodzie http://ideone.com/us5q8d
Przepuszczałem go przez http://www.pythontutor.com i nie rozumiem kroku 63 -> 64 (linia 25). Dlaczego gdy zapisuję wartość do pomocniczej listy suma_pom, to nadpisuje mi też wartość w liście suma? Dalej nie sprawdzałem.

#edit
poprawione i mam nadzieję, że działa :) nie wiem czy bym to rozkminił bez podpowiedzi :p

Lista to typ złożony. Z punktu widzenia zarządzania pamięcią wpada do wielu szuflad (i pamiętamy adres pierwszego elementu). W Pythonie (i w większości języków funkcyjnych) w przypadku operatora "=" przepisywane są adresy, a nie obiekty. Na przykładzie:

Jedyne typy, w których wartości przy przypisaniu zostają skopiowane to tzw. typy proste (liczby, pojedyńcze znaki).
Dlaczego tak jest? Obiekty potrafią być wielkie, a kopiowanie z jednego miejsca pamięci do drugiego jest operacją czasochłonną. Z kolei skopiowanie adresu (która jest liczbą) do drugiej zmiennej jest bardzo proste i szybkie. Co ciekawe, w przypadku C wszystkie typy są jednakowo traktowane - zostają po prostu skopiowane. Dlatego też powstały tzw. wskaźniki, żeby zachować wydajność.

Ty zaczynasz wskazywać na ten sam kawałek pamięci w linii 29.

Rozwiązaniem tego problemu w przypadku list jest kopiowanie ich element po elemencie (za pomocą pętli for). W tym wypadku z racji tego, że w liście przechowujemy typy proste zostają one skopiowane. Istnieją również inne metody (trudniejsze), które jednak nie opłacająsię w przypadku tak prostego przypadku. Np. deep copy - http://docs.python.org/2/library/copy.html.

Aby udowodnić, że C robi to kopiowaniem, podrzucam kawałek kodu - http://pastie.org/7720395. Wykracza on troszeczkę ponad poziom naszego kursu, ale tylko nieznacznie - już niedługo nie dojdziemy do struktur.

Dzisiaj, późno w nocy (taki mam tryb życia) napiszę kolejną część ;).

Pozdrawiam
Killavus