Bioinformatyk.eu nowy serwis o bioinformatyce i programowaniu

Codility.com to ciekawy projekt polskich programistów, którzy postanowili stworzyć narzędzie służące do testowania samodzielnie napisanego kodu. Mamy 30 min. na wykonanie określonego zadania w wyznaczonym języku programowania, projekt zostaje szczegółowo przetestowany i oceniony (max 100 pkt.) W wersji demo możemy się sprawdzić w jednym zadaniu, którego stopień trudności określono na 1 gwiazdkę. Teraz uwaga: wszystkich [...]

Algorytm Grahama do kalkulacji **convex hull** Wyobraź sobie stado krów na pastwisku. Ty, jako kowboy, masz za zadanie złapać wszystkie krowy jednym lassem. Kiedy zaciągasz lasso, część krów stanowi wierzchołki wielokąta, inne zaś stoją w jego środku. Pytanie jest, ile krów stoi na tych wierzchołkach? (ryc. 1) Dobry kowboy oczywiście potrafi policzyć krowy na wierzchołkach, [...]

Dzisiaj będzie trochę teorii n.t. tzw. notacji asymptotycznej. jest ona używana do szacowania złożoności obliczeniowej algorytmów, dzięki czemu można w miarę dokładnie wyznaczyć takie parametry jak czas wykonywania się określonych instrukcji, rozmiar alokowanej pamięci itp. trochę na ten temat pisałam już tutaj. Przyjmijmy, że f(n) i g(n) są funkcjami (czyli np. czas), dla n→ ∞ [...]

Postanowiłam sprawdzić w praktyce, jak się mają teoretyczne wyliczenia złożoności obliczeniowej algorytmów do rzeczywistych wyników uzyskiwanych w kompilatorze. Do testów wybrałam język Python oraz kompilator Eclipse. Problem: Znaleźć minimalny i maksymalny element w tablicy n-elementowej. Można to zrobić na 2 sposoby: