Strona główna

Z RNO-Wiki
(Różnice między wersjami)
m (Konfiguracje)
m (Algorytmy)
Linia 20: Linia 20:
 
## [[BFS]] - algorytm przeglądania grafu wszerz
 
## [[BFS]] - algorytm przeglądania grafu wszerz
 
## [[Sortowanie topologiczne]] wierzchołków w grafie skierowanym
 
## [[Sortowanie topologiczne]] wierzchołków w grafie skierowanym
 +
## [[Znajdowanie mostów]] w~grafie prostym
 
## Grafy dwudzielne:
 
## Grafy dwudzielne:
 
### [[Dwudzielność grafu]] - sprawdzanie, czy graf jest dwudzielny
 
### [[Dwudzielność grafu]] - sprawdzanie, czy graf jest dwudzielny
Linia 53: Linia 54:
 
<table width="100%">
 
<table width="100%">
 
<tr><td valign="top">
 
<tr><td valign="top">
 +
 
= Struktury danych =
 
= Struktury danych =
 
# [[Struktury]] - co to jest w ogóle
 
# [[Struktury]] - co to jest w ogóle

Wersja z 07:35, 28 lut 2008

Witaj na stronie RNO-Wiki, którą administruje Rafał Nowak

http://www.rafalnowak.pl

Spis treści

Algorytmy

  1. Algorytmy liczbowe
    1. Algorytm Euklidesa, Rozszerzony algorytm Euklidesa
    2. Sito Eratostenesa
    3. Funkcja phi Eulera
    4. Liczby Fibonacciego
  2. Algorytmy tekstowe
    1. LCS (ang. Longest Common Subsequence) - najdłuższy wspólny podciąg dwóch słów
    2. KMP - algorytm Knutha-Morrisa-Pratta - wyszukiwanie wzorca w tekscie
    3. Równoważność cykliczna dwóch słów
    4. Minimalne słowo pokrywające
  3. Algorytmy grafowe
    1. DFS - algorytm przeglądania grafu w głąb
    2. BFS - algorytm przeglądania grafu wszerz
    3. Sortowanie topologiczne wierzchołków w grafie skierowanym
    4. Znajdowanie mostów w~grafie prostym
    5. Grafy dwudzielne:
      1. Dwudzielność grafu - sprawdzanie, czy graf jest dwudzielny
      2. Maksymalne skojarzenie w grafie dwudzielnym - Algorytm Hopcrofta-Karpa
    6. Znajdowanie najkrótszych ścieżek z jednego źródła
      1. Algorytm Dijkstry : graf z nieujemnymi wagami
      2. Algorytm Bellmana-Forda : graf bez cyklu o ujemnej wadze
    7. Algorytm Floyda-Warshalla - znajdowanie nakrótszych ścieżek pomiędzy dowolną parą wierzchołków
    8. MST - znajdowanie minimalnego drzewa spinającego grafu
      1. Algorytm Kruskala
      2. Algorytm Prima-Dijkstry
    9. 2SAT - problem spełnialności zdań 2CNF
  4. Algorytmy sortujące
    1. SelectSort - Sortowanie przez wybór - O(n²)
    2. InsertSort - Sortowanie przez wstawianie - O(n²)
    3. MergeSort - Sortowanie przez scalanie - O(n log n)
    4. QuickSort - "Szybkie" sortowanie - O(n log n)


Struktury danych

  1. Struktury - co to jest w ogóle
  2. Kopiec
  3. Drzewo przedziałowe
  4. UNION FIND - Struktura danych dla zbiorów rozłącznych
  5. bignum - Arytmetyka długich liczb
  6. STL
    1. vector - Wektor - czyli fajna tablica
    2. slist, list - lista jednokierunkowa i dwukierunkowa
    3. stack - Stos
    4. queue - zwykła kolejka (jak do lekarza)
    5. priority_queue - kolejka priorytetowa (kopiec)
    6. set, multiset - Zbiór uporządkowany
    7. map - mapa , czyli tablica z dziurami

Programowanie w C++

  1. Funkcje i procedury w C/C++
  2. Struktury

Blog

Wiele ciekawych rozwiązań w C++ znajdziesz na moim blogu RNO-Blog. Szukaj w nim artykułów z etykietą c++.

Konfiguracje

Zobacz także konfiguracje i inne prace

Osobiste