Chapter_10

Список прикладів

Алгоритмічна складність, наближені та рандомізовані алгоритми

1. color_graph.py - задача розфарбування графа методом грубої сили
2. greedy_set.py - реалізація жадібного алгоритму для покриття множини
3. fptas.py - реалізація FPTAS для задачі про рюкзак
4. subsetsum_bruteforce.py - приклад застосування грубої сили, щоб знайти підмножину чисел, сума яких максимально наближається до деякого цільового значення $T$, але не перевищує його.
5. subsetsum_fptas.py - приклад застосування FPTAS, щоб знайти підмножину чисел, сума яких максимально наближається до деякого цільового значення $T$, але не перевищує його.
6. quicksort.py - реалізації рандомізованого QuickSort
7. markova_chain.py - нерухомий розподіл марковського механізму, що визначається матрицей переходів і початковим розподілом імовірностей.