|
|
|
Polski Serwis Naukowy - OnLine od 1999 roku
 RSS
Dodaj do:
Warto przeczytać: W dniach 16 - 17 grudnia 2011 r. w Sierra Nevada, Hiszpania, odbędzie się wydarzenie pt. "Wielka nauka - algorytmy, systemy i narzędzia do skalowalnego uczenia się".
Wydarzenie poświęcone będzie tematom dotyczącym narzędzi, algorytmów, systemów, sprzętu i problemów rzeczywistych powiązanych z ucz... Z biotechnologiami zetknęliśmy się wszyscy. Najpopularniejszym biofarmaceutykiem jest dowolna szczepionka. Są nimi także np. insuliny. Ostatnio przybywa leków biotechnologicznych, powstających po wygaśnięciu patentów na leki wytworzone p... [i]Rozmowa z endokrynologiem dziecięcym,
prof. dr n. med. Tomaszem Romerem [/i]
prof. dr hab. n. med. Tomasz Romer[size=9]Wybitny specjalista w dziedzinie endokrynologii; zaÅ‚ożyciel i czÅ‚onek ZespoÅ‚u Koordynacyjnego ds. Sto... Punktem wyjÅ›cia omawianego tematu bÄ™dzie dobrze znane rodzicielskie rozwiÄ…zanie problemu, polegajÄ…cego na podzieleniu ciasta pomiÄ™dzy dwoje dzieci tak, aby każde czuÅ‚o, że jest traktowane sprawiedliwie. Strategia podziaÅ‚u gwarantu... NastÄ™pny przedstawiony protokół bÄ™dzie protokoÅ‚em “bez zazdroÅ›ci” rozpatrzonym dla trzech graczy. Wymaga on kombinacji idei wprowadzonych przez Banacha i Knastera o przycinaniu oraz podstawowej struktury użytej przez Steinhau...
Ostatnio na Forum:
Dyskusje
8
odp.
4
odp. Reklama:
 Teoria grafówCzy wiesz że...? Skojarzeniem grafu nazywa się nie zawierający pętli podzbiór M krawędzi grafu E taki, że żadne dwie krawędzie w M nie są sąsiednie, tj. nie spotykają się w jednym wierzchołku. Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru. Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami. Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.
Algorytm najbliższego sąsiada - naiwny algorytm rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Bardzo prosty do zaprogramowania, szybki, ale daje słabe wyniki. Opis zagadnienia mostów królewieckich opublikowany w 1736 roku przez Leonharda Eulera jest uznawany za pierwszą pracę na temat teorii grafów. Zagadnienia teorii grafówWażne algorytmyZobacz też
Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.
Izomorfizm grafów – Grafy G i F nazywamy izomorficznymi, jeżeli istnieje bijekcja zbioru wierzchołków grafu G na zbiór wierzchołków grafu F, która zachowuje strukturę grafu (krawędzie). Intuicyjnie oznacza to, że grafy G i F są tym samym grafem, jedynie poddanym jakiejś permutacji wierzchołków.
Czy wiesz że...? beta Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.
Reprezentacja grafu to sposób zapisu grafu umożliwiający jego obróbkę z użyciem programów komputerowych. Dwa najpopularniejsze sposoby zapisu informatycznego grafów to macierz sąsiedztwa oraz listy sąsiedztwa.
Informatyka (łac. informatio - "wyobrażenie", "wizerunek", "pomysł", ang. computer science, computing science, information technology, informatics) – dziedzina nauki i techniki zajmująca się przetwarzaniem informacji – w tym technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informacje. Pierwotnie część matematyki, została rozwinięta do osobnej dyscypliny nauki, pozostaje jednak nadal w ścisłym związku z matematyką, która dostarcza jej podstaw teoretycznych.
Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
CPM - Metoda Ścieżki Krytycznej (z ang. Critical Path Method) to jedna z metod stosowanych w zarządzaniu projektami. Utworzona została w roku 1958 w amerykańskiej firmie chemicznej DuPont, w celu usprawnienia procesów produkcji. Metoda ta pozwala na graficzną prezentację kolejnych czynności wykonywanych w ramach projektu, z zaznaczeniem szacowanego czasu trwania tych czynności, oraz z zachowaniem ich sekwencji. Metodę ta stosujemy wtedy, gdy znane są czasy trwania poszczególnych czynności.
Algorytm Johnsona - algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie O( | V | 2lg | V | + | V | | E | ) (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych o kopce Fibonacciego), dla grafów rzadkich jest więc asymptotycznie szybszy od algorytmu Floyda-Warshalla. Algorytm Johnsona zwraca albo macierz wag najkrótszych ścieżek, albo informuje, że graf wejściowy ma cykl o ujemnej wadze. W algorytmie Johnsona jako podprogramy używane są algorytmy Dijkstry i Bellmana-Forda. Powyższa treść oraz zamieszczone w niej powiązane definicje/pojęcia - udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń.
Zobacz szczegółowe informacje o warunkach korzystania
Wszystkie hasła znajdujące się w naszym mirrorze Wikipedii mają znaczenie informacyjne i edukacyjne. Nie mogą być traktowane jako porady. |
