لطفا منتظر باشید ...
Index
F
factor, 851
twiddle, 836
factorial function (!), 54–55
factorization, 896–901, 905
unique, 854
failure in a Bernoulli trial, 1112
fair coin, 1101
fan-out, 988
Farkas's lemma, 819 pr.farthest-pair problem, 948
FASTER-ALL-PAIRS-SHORTEST-PATHS, 627, 628 ex.FASTEST-WAY, 329
Fast Fourier Transform (FFT)circuit for, 842–843
iterative implementation of, 839–842
multidimensional, 845 pr.recursive implementation of, 834–836
using modular arithmetic, 847 pr.feasibility problem, 601, 818 pr.feasible linear program, 778
feasible region, 773
feasible solution, 601, 773, 778
Fermat's theorem, 877
FFT, see Fast Fourier Transform
FIB-HEAP-CHANGE-KEY, 497 pr.FIB-HEAP-DECREASE-KEY, 489
FIB-HEAP-DELETE, 492
FIB-HEAP-EXTRACT-MIN, 483
FIB-HEAP-INSERT, 480
FIB-HEAP-LINK, 486
FIB-HEAP-PRUNE, 497 pr.FIB-HEAP-UNION, 482
Fibonacci heap, 476–497
changing a key in, 497 pr.creating, 480
decreasing a key in, 489–492
deletion from, 492, 496 pr.in Dijkstra's algorithm, 599
extracting the minimum key from, 482–488
insertion into, 480–481
in Johnson's algorithm, 640
maximum degree of, 479, 493–496
minimum key of, 481
potential function for, 479
in Prim's algorithm, 573
pruning, 497 pr.running times of operations on, 456 fig.uniting, 481–482
Fibonacci numbers, 56, 86 pr., 494
computation of, 902 pr.field of an object, 20
FIFO (first-in, first-out), 200
see also queue
final-state function, 917
FIND-DEPTH, 519 pr.find path, 506
FIND-SET, 499
disjoint-set-forest implementation of, 508, 522
linked-list implementation of, 501
finished vertex, 540
finishing time, in depth-first search, 541
and strongly connected components, 555
finish time, in activity selection, 371
finite automaton, 916
for string matching, 917–922
FINITE-AUTOMATON-MATCHER, 919
finite group, 862
finite sequence, 1078
finite set, 1073
first-fit heuristic, 1049 pr.first-in, first-out, 200
see also queue
fixed-length code, 385
floating-point data type, 22
floor function (⌊⌋), 51
in master theorem, 81–84
floor instruction, 22
flow, 644–650
aggregate, 788
blocking, 697
excess, 669
integer-valued, 666
sum, 650 ex.total net, 645
total positive, 645
value of, 644
flow conservation, 644
flow network, 644–650
corresponding to a bipartite graph, 665
cut of, 654–657
with negative capacities, 695 pr.FLOYD-WARSHALL, 630
FLOYD-WARSHALL', 635 ex.Floyd-Warshall algorithm, 629–632, 634 ex.for
and loop invariants, 18 n.in pseudocode, 19
FORD-FULKERSON, 658
Ford-Fulkerson method, 651–664
FORD-FULKERSON-METHOD, 651
forest, 1083, 1085
depth-first, 540
disjoint-set, 505–509
formal power series, 86 pr.formula-satisfiability problem, 996–998
forward edge, 546
forward substitution, 744–745
fractional knapsack problem, 382, 384 ex.freeing of objects, 210–212
free list, 211
FREE-OBJECT, 212
free tree, 1083, 1085–1087
frequency domain, 822
full binary tree, 1089, 1091 ex.
relation to optimal code, 386
full node, 439
full rank, 731
full walk of a tree, 1030
fully parenthesized, 331
fully polynomial-time approximation scheme, 1023
for the maximum-clique problem, 1050 pr.for the subset-sum problem, 1043–1049
function, 1077–1080
Ackermann's, 521
basis, 762
convex, 1109
linear, 25, 772
objective, see objective function
prefix, 923–925
quadratic, 25
suffix, 917
transition, 916
functional iteration, 55
fundamental theorem of linear programming, 816
fusion tree, 182, 433
fuzzy sorting, 163 pr.
