کارت‌های مفهوم و فرمول کنکور ارشد علوم کامپیوتر

An NFA accepts a string iff at least one choice of transitions ends in an accepting state — track the whole set of reachable states symbol by symbol instead of guessing one lucky path.

Bellman-Ford relaxes every edge n-1 times to settle all shortest paths; a single extra (n-th) pass that still relaxes an edge proves a negative cycle is reachable.

Bubble sort (and any sort that only swaps adjacent out-of-order elements) performs exactly as many swaps as there are inversions in the input — so you can count swaps without simulating the passes.

Bubble, selection, and insertion sort all run in Theta(n^2) on a random array; what distinguishes them is whether their cost depends on the input — selection sort is always Theta(n^2), bubble and insertion can drop to Theta(n) on sorted data.

Split [a,b] into n equal panels of width h=(b-a)/n and sum trapezoids: the interior nodes count twice, the two endpoints once, giving (h/2)[f0 + 2(f1+...+f_{n-1}) + fn].

If f is differentiable on [a,b], then f' takes every value between f'(a) and f'(b) — even though f' need not be continuous. So a derivative can never have a jump discontinuity.

The ratio $\dfrac{\sin\frac{(2n+1)x}{2}}{\sin\frac{x}{2}}$ collapses into the clean sum $1+2\sum_{k=1}^{n}\cos kx$ — making any integral of it trivial.

When the limits a, b of a definite integral are free, the integral is largest when [a, b] is exactly the set where the integrand is nonnegative — so set the limits at consecutive roots of f.

To glue two formulas at a breakpoint so the result is n-times continuously differentiable, force the two pieces to agree in value and in every derivative up to order n at that point — that single requirement chains all the lower orders along with it.

Use $f'$ to split the line into monotone pieces, then count exactly one root per piece whose endpoints straddle zero — no factoring required.

Revolving a curve sweeps a surface whose area is $\int 2\pi(\text{radius})\,ds$, where $ds$ is arc length — pick the variable so the radius is the distance to the axis.

The mass of a solid is $M=\iiint_V \rho\,dV$ — integrate the (possibly variable) density over the region; when $\rho$ is constant this collapses to $\rho\cdot\text{volume}$.

Build the integral from sup/inf over partitions: the lower integral pushes up from below, the upper pushes down from above. They always satisfy lower ≤ upper, and f is integrable exactly when they are equal.

To count how many small boxes fit in a grid, multiply the number of orientations by the number of positions per orientation — and each axis of size N holds a segment of length L in exactly N-L+1 positions.

Key lower and upper bounds on the chromatic number $\chi(G)$: the independence-number lower bound $\chi \ge n/\alpha$, greedy degree-based upper bounds, and the minimum-degree property of color-critical graphs.

The exact number of spanning trees is any cofactor of the Laplacian (Matrix-Tree), but for graphs glued at cut vertices the count simply multiplies block by block — a cycle of length k contributes a factor of k.

If G is Hamiltonian then deleting any set S of vertices leaves at most |S| connected components: c(G-S) ≤ |S|. Deleting many vertices and counting components that shatter is the fastest way to prove a graph is NOT Hamiltonian.

The sum of all vertex degrees equals twice the number of edges — so the number of odd-degree vertices is always even, and many "does this graph exist?" questions collapse to one parity/counting check.

A consistent set is satisfiable by some valuation; a maximal consistent one decides every proposition, and Lindenbaum's lemma says every consistent set extends to one.

When each position independently contributes an odd value with probability 1/2, exactly half of all configurations have an even total — so the count is simply (total)/2.

To split distinct objects into unlabeled groups, start from the labeled multinomial count, then divide by j! for every block of j same-size groups — because permuting equal-size groups gives the same partition.

Composition distributes fully over UNION (both sides, always equality), but only ONE-WAY (subset, not equality) over intersection and difference — because it is built from an existential quantifier.

When each iteration replaces every segment by k copies scaled by factor r, the total length is multiplied by kr each step — so it grows geometrically as (kr)^n.

To add up every number formed by permuting a digit set, exploit symmetry: each digit lands in each position equally often, so sum once per position and weight by place value.

A sum of products of binomials whose lower indices add to a constant collapses to a single binomial: the inner indices telescope into one combined choose.

When an unknown matrix appears together with its transpose and trace, write it with literal entries, expand both sides entrywise, and turn the matrix identity into a small linear system.

For independent events, attack 'at least one' through its complement 'none' (a product of failure probabilities), and build 'exactly one' by swapping a single factor — then collapse the product by telescoping.

Changing one data value shifts the mean by (change)/n, but leaves the median untouched as long as the order of the middle values is unchanged.

Linear = at most ONE nonterminal per rule body. They sit strictly between regular and context-free, and are closed under union, reversal and homomorphism but NOT under intersection, complement or concatenation.

Convert any (epsilon-)NFA to an equivalent DFA whose states are sets of NFA states — then, if the question asks for the minimum number of states, minimize the result rather than reporting the raw subset count.

Sort an array of three distinct key values into low-mid-high order in a single linear, in-place pass using three pointers.

Computing $x^{n}$ with the four basic operations needs only $\Theta(\log n)$ multiplications, not $\Theta(n)$: repeatedly square the base while halving the exponent, multiplying in an extra $x$ whenever a bit of $n$ is $1$.

The greedy "take the largest coin that fits" rule for making change is *not* always optimal — it works only for **canonical** denomination systems. On a non-canonical set like $\{10,7,2,1\}$, greedy can use more coins than the true minimum.

To rank functions slowest-to-fastest, first unmask the impostors: rewrite each as a power of $2$ via $n=2^{\log n}$. Some "functions" are secretly constants, and $\log^{*}n$ grows slower than any iterated logarithm.

The cost of a loop is the SUM of the work each iteration does, not (iterations) x (max cost). When the body costs a constant, the sum collapses to (count) x O(1); when the body cost varies with i, evaluate the series. Split a loop with several statements into separate sums and add them.

The cost of a single counted loop is set by how the counter is UPDATED, not how it is compared. Solve the recurrence on the counter, set it equal to the bound n, and invert: i+=c gives n/c steps, i*=c gives log_c n steps, and i=i*i gives log log n steps.

When the work to split/combine, $f(n)$, exactly matches the leaf cost $n^{\log_b a}$, the recurrence $T(n)=aT(n/b)+f(n)$ solves to $\Theta\!\left(n^{\log_b a}\log n\right)$ — every level costs the same, and there are $\Theta(\log n)$ levels.

Model one run of merge sort as a recursion tree with n leaves: there are n-1 internal (splitting) nodes, so merge is called n-1 times, total mergesort invocations are 2n-1, and the worst-case element comparisons are at most n*ceil(log2 n) - 2^ceil(log2 n) + 1. Don't confuse 'total calls' with 'recursive calls'.

A function into a discrete codomain like $\mathbb{Z}$ is continuous exactly where it is locally constant, so its continuity set is open and its discontinuity set is closed.

Sum series like sum n/(2n+1)! by writing the numerator as a combination of the factorial's argument, so each term collapses onto a known e, sinh, or cosh series.

Split a rational function into simple poles 1/(x-r) — each differentiates n times to a tidy (-1)^n n!/(x-r)^{n+1}, giving the n-th derivative with no product-rule mess.

For bounded sequences, limsup of a sum is at most the sum of limsups, and liminf is at least the sum of liminfs.

Integrate a ratio of two linear sine-cosine expressions by splitting the numerator into a multiple of the denominator, a multiple of the denominator's derivative, and a constant — turning the integral into a constant, a log, and a standard half-angle integral.

A rapidly oscillating factor like $\sin(nx)$ or $\cos(nx)$ averages any fixed integrable function to zero, so $\int_a^b f(x)\sin(nx)\,dx \to 0$ as $n\to\infty$. When $f'$ is continuous, integration by parts proves it and gives the $\Theta(1/n)$ decay rate.

Consistency = having a model. The intersection of two consistent theories is always consistent, but their union can be inconsistent.

When a count splits by one free parameter d and equals a linear formula in d, total it with the arithmetic-series sum instead of listing cases — the running counts form an arithmetic progression you add in one stroke.

Sweep a linear (chain-like) graph left to right; the only state that crosses each cut is whether the boundary vertex is already matched, giving a small linear recurrence you solve like a Fibonacci.

Count relations by splitting the n^2 pairs into independent diagonal loops and off-diagonal blocks, multiplying the choices each property allows. Handle 'not P' constraints by complementary counting: (all) minus (those with P).

Forbidding a length-2 pattern like '01' freezes the string into one rigid shape (a block of 1s then a block of 0s), so the count collapses to choosing a single boundary: n+1 strings. Recognize a union of A_i as 'contains the pattern somewhere', then count the complement.

An occurrence of a variable is bound when it lies inside the scope of a quantifier on that same variable, and free otherwise. Count occurrences, not names, and remember a quantifier's scope stops at its subformula.

Rewrite A -> B as not A or B, then distribute. A conjunction/disjunction in the CONSEQUENT splits cleanly; in the ANTECEDENT the connective FLIPS, so (P or Q) -> R becomes a conjunction.

A function $f$ has a **left** inverse ($g\circ f=\mathrm{id}$) exactly when it is **injective**, and a **right** inverse ($f\circ g=\mathrm{id}$) exactly when it is **surjective**. So "is $f$ invertible on one side?" is just a disguised injectivity/surjectivity question.

To count tuples of subsets $(A,B,C,\dots)$ of an $n$-set that satisfy a membership condition, decide each element's fate **independently**: count the legal membership patterns for one element, then raise that number to the power $n$.

To pick r objects from groups while taking at least one from each, hand one slot to every group up front, then split into cases on how the few leftover slots are distributed — usually a tiny, forced casework.

Symmetric closes every pair under swapping; antisymmetric forbids two-way arrows between distinct points. The only relations that are both are subsets of the diagonal I = {(x,x)}.

Vertex connectivity, edge connectivity, and minimum degree obey $\kappa(G)\le\lambda(G)\le\delta(G)$; Menger's theorem recasts connectivity as a max number of disjoint paths, and cubic graphs force $\kappa=\lambda$.

A system $Ax=b$ is **ill-conditioned** when a tiny change in the data ($b$ or $A$) produces a huge change in the solution $x$. The **condition number** $\kappa(A)=\lVert A\rVert\,\lVert A^{-1}\rVert\ge 1$ measures this sensitivity: it is the worst-case amplification factor from relative input error to relative output error.

Matrix similarity ($A=PBP^{-1}$) survives both inverting and transposing: if $A\sim B$ then $A^{-1}\sim B^{-1}$ and $A^{t}\sim B^{t}$. Plus every square matrix is similar to its own transpose, $A\sim A^{t}$. Chaining these rules lets you transform a given similarity into many others.

A square system $A\mathbf{x}=\mathbf{b}$ has exactly one solution for every right-hand side if and only if $A$ is invertible, i.e. $\det(A)\neq 0$ — so "for which parameter is the solution unique?" always reduces to solving $\det(A)\neq 0$.

Average speed is total distance over total time, never the plain average of the leg speeds; when you know the distance fraction of each leg it equals the distance-weighted harmonic mean of the speeds.