Drzewo (matematyka)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Drzewograf nieskierowany, który jest acykliczny i spójny, czyli taki graf, że z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, brak możliwości chodzenia „w kółko”).

B-drzewo – drzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych. Popularniejsze w zastosowaniach bazodanowych i systemach plików są B+drzewa, które są szczególnym przypadkiem B-drzew, przechowującym dane tylko w liściach.Drzewo – w informatyce to struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych.

Równoważne definicje[ | edytuj kod]

Graf prosty G jest drzewem jedynie, jeśli spełnia jeden z warunków:

Drzewo decyzyjne – graficzna metoda wspomagania procesu decyzyjnego, stosowana w teorii decyzji. Algorytm drzew decyzyjnych jest również stosowany w uczeniu maszynowym do pozyskiwania wiedzy na podstawie przykładów.Graf planarny – graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.
  • dowolne dwa wierzchołki łączy dokładnie jedna ścieżka prosta
  • G jest acykliczny i dodanie krawędzi łączącej dowolne dwa wierzchołki utworzy cykl
  • G jest spójny i usunięcie dowolnej krawędzi spowoduje, że G przestanie być spójny
  • Przykłady drzew[ | edytuj kod]

  • Tree graph.svg
  • Star network 7.png
  • Complete bipartite graph K3,1.svg
  • Complete graph K2.svg
  • 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.Rachunek lambda – system formalny używany do badania zagadnień związanych z podstawami matematyki jak rekurencja, definiowalność funkcji, obliczalność, podstawy matematyki np. definicja liczb naturalnych, wartości logicznych itd. Rachunek lambda został wprowadzony przez Alonzo Churcha i Stephena Cole’a Kleene’ego w 1930 roku.


    Podstrony: 1 [2] [3] [4]




    Warto wiedzieć że... beta

    Drzewo AVL, nazywane również drzewem dopuszczalnym – zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielskij i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962.
    Algorytmika to nauka o algorytmach. Jest działem informatyki, cybernetyki, a także, dla większości nauk matematyczno-przyrodniczych, ekonomii i techniki. Algorytmika zajmuje się badaniem algorytmów. Częścią algorytmiki jest algorytmizacja, czyli proces budowy konkretnego algorytmu.
    Las - graf, którego każdy spójny podgraf jest drzewem. Równoważnie można zdefiniować las po prostu jako acykliczny graf nieskierowany (czyli nie zawierający żadnych cykli). Wtedy jego spójne składowe są drzewami.
    Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.
    Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.
    MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).
    Biblioteka Narodowa Izraela (hebr. הספרייה הלאומית; dawniej: Żydowska Biblioteka Narodowa i Uniwersytecka, hebr. בית הספרים הלאומי והאוניברסיטאי) – izraelska biblioteka narodowa w Jerozolimie.

    Reklama