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

When two distinct objects are drawn at random from a set, every unordered pair is equally likely, so the probability of any event is (favorable pairs) / C(n,2) — reducing the problem to two separate counts.

If one player tosses a fair coin one more time than another, the probability that the first gets strictly more heads is exactly $\tfrac12$ — proved by a clean symmetry split, no binomial sums needed.

Adding a **Stay** option keeps a TM at full recursively-enumerable power, but forbidding the head from re-scanning what it already passed collapses it: a head that can never (or only once) move back toward the start reads each cell at most once and recognizes only **regular** languages.

A <=T B means a decider for A exists given an oracle for B. Solvability flows OPPOSITE the arrow (B easy => A easy), <=T is a preorder not a partial order (mutual reduction gives Turing-equivalence, not equality), and oracles are closed under complement, so A <=T A^c always.

Stopping merge-sort recursion at blocks of a *constant* size $k$ and finishing each block with insertion sort keeps the running time at $\Theta(n\log n)$; the cutoff only shaves a constant factor. The bound changes only when $k$ is allowed to grow with $n$.

When the recurrence feeds its own output back into itself, like G(n)=n-G(G(n-1)), unroll a few terms and look for a golden-ratio floor closed form.

When a recurrence shrinks $n$ by a constant *factor* (e.g. $n\to n/2$ or $n\to\sqrt{n}$), the substitution $n=2^{m}$ converts division into subtraction, turning a hard recurrence in $n$ into an easy one in $m$ that you can unroll or hit with the Master Theorem.

A sorted array cyclically rotated by some unknown amount still hides enough order to binary-search it in $\Theta(\log n)$: there is exactly one "drop" where $A[i]>A[i+1]$, and at every midpoint one half is guaranteed sorted, so you can find the pivot, the minimum, the maximum, or any target in logarithmic time.

Two continuous functions that agree on a dense set (like $\mathbb{Q}$) are equal everywhere; one continuous function with a constant value on a dense set is that constant.

Integrals of the form 1/(x·√(x²±a²)) are antidifferentiated by the reciprocal substitution x = 1/t, which collapses them to ±1/√(1±t²) — an inverse-hyperbolic (or arcsin) form. The improper version converges because the tail decays like 1/x².

A limit of $f(x,y)$ as $(x,y)\to(a,b)$ exists only if it equals the same value along every path to $(a,b)$. Finding two paths that give different values proves the limit does not exist.

Area swept by a polar curve is the sum of thin circular sectors, giving A = ½∫ r² dθ; for a region between two curves integrate ½(r_outer² − r_inner²), and for an overlap take the smaller radius on each ray.

A quadrature rule $\int_a^b f \approx Q$ has degree of precision $d$ if it is exact for every polynomial of degree $\le d$ but not for degree $d+1$. Taylor-expanding both sides about a point and matching terms reveals $d$ and the leading error: the first mismatched power gives an error $\propto h^{d+2} f^{(d+1)}(\xi)$.

A sum whose number of terms grows with n is squeezed by replacing every term with the largest and smallest term; if both bounds (each n copies of a single term) share a limit, the sum has that limit too.

The area of the piece of a surface z=f(x,y) lying above a region R in the xy-plane is the double integral over R of √(1+f_x²+f_y²) — the local stretch factor between the surface and its shadow.

To average a permutation statistic over all of $S_n$, write it as a sum of indicators and use linearity of expectation — one object at a time.

Treat the curves as a planar graph and apply Euler's formula r = E - V + 1 + C: count intersection points (V) and arcs (E), then read off the number of regions.

Decidable = an algorithm always halts with the right yes/no; recursively enumerable (r.e.) = halts only on the YES-instances. Every decidable set is r.e., but not conversely — and the gap is exactly where logic problems live.

A base of a set of propositions $\Gamma$ is a subset that proves all of $\Gamma$ yet has no redundant member — a minimal generating set for the deductive closure of $\Gamma$.

A monotone path that takes a right-steps and b up-steps can be arranged in C(a+b, b) ways; to force a path through a checkpoint, count each leg separately and multiply.

The path Ramsey number $R(P_m,P_n)$ — the least $N$ so every red/blue coloring of $K_N$ has a red $P_m$ or blue $P_n$ — has the closed form $R(P_m,P_n)=m+\lfloor n/2\rfloor-1$ for $m\ge n\ge 2$; e.g. $R(P_4,P_4)=5$.

A function defined by recursion on a formula's parse tree is pinned down by structural induction; when each connective contributes a distinct prime factor, unique factorization reads back every connective count from the single value f(A).

To delete a node with two children, overwrite its key with its in-order predecessor (max of the left subtree) or successor (min of the right subtree), then delete that easier node.

In a complete binary tree of n nodes, the root's left subtree is largest when the last level fills the left side first; its size is then a full tree of height h-1 plus the overflow leaves, capped at 2^h-1.

The height of a tree is one more than the taller of its two subtrees; recurse to the leaves and combine on the way back up.

Treat objects that must stay together as one glued block, then multiply by the internal orderings — the standard tool for computing probabilities of adjacency in a random row arrangement.

A dataset has zero variance (equivalently zero standard deviation) if and only if every value is identical; then the mean, median, every percentile, and the single distinct value all collapse to that same constant.

A CFG is ambiguous iff some string has two distinct leftmost derivations (equivalently, two distinct parse trees) — exhibit ONE such string to prove it. Ambiguity is a property of the grammar, not the language: two grammars can generate the same language while one is ambiguous and the other unambiguous, as the classic dangling-else grammar shows.

The empty language and every finite language are regular, so a non-regular language must be infinite and nonempty. Two cheap regular subsets sit inside ANY language L: the empty set, and any finite subset you pick. Use these facts to instantly kill exam claims like 'some language has no regular subset' or 'a non-regular language could be finite'.

Ambiguity is a property of a **grammar** (a string with $\ge 2$ parse trees); *inherent* ambiguity is a property of a **language** (every grammar for it is ambiguous). These nest into a strict chain $\text{Regular}\subsetneq\text{DCFL}\subsetneq\text{Unambiguous CFL}\subsetneq\text{CFL}$: every deterministic CFL is unambiguous, but some CFLs are inherently ambiguous and lie outside even the unambiguous class.

Drop ε-transitions and force one accepting state, and if ε∈L the start must equal that accepting state — which forces every accepted string to loop back, making L closed under concatenation.

L is RE iff it is the DOMAIN of a partial computable function, iff it is the RANGE of one (or empty), iff it is enumerable. RE is closed under finite union/intersection, concatenation, star, homomorphism, and EFFECTIVE countable union (dovetailing) — but NOT under complement nor arbitrary countable union.

Over a one-letter alphabet the language hierarchy collapses: every context-free L over a single symbol is already regular. This follows from Parikh's theorem (CFL Parikh images are semilinear, and over a unary alphabet the Parikh image IS the language, so the set of lengths is eventually periodic = regular). It does NOT say arbitrary subsets of a^* are regular.

The set of points at distance zero from $A$ is exactly $\overline{A}$, so it is always closed, contains $A$, and equals $A$ iff $A$ is closed.

Matrix multiplication is associative but its scalar-multiplication cost is not, so dynamic programming over interval splits finds the cheapest parenthesization in $\Theta(n^{3})$ time.

LSD radix sort is correct only if the per-digit auxiliary sort is stable, so heapsort and quicksort cannot be plugged in while stable counting sort can.

To turn an n-element universe into a structure you interpret each symbol independently and multiply: a k-ary relation gives 2^(n^k) choices, a k-ary function gives n^(n^k), and a constant gives n.

The transitive closure $R^{+}$ is the smallest transitive relation containing $R$: it adds $(x,y)$ whenever a directed path of length $\ge 1$ runs from $x$ to $y$.

A multi-dimensional array is flattened into linear memory either row-by-row (row-major) or column-by-column (column-major), and you locate any cell with a base-plus-offset address formula.

For nonnegative integrands, domination decides convergence: if $0\le f\le g$ then $\int g<\infty$ forces $\int f<\infty$, and $\int f=\infty$ forces $\int g=\infty$.

Each finite ordinal is the set of all smaller ordinals, so $n=\{0,1,\dots,n-1\}$; inside an iterated power set $\mathcal{P}^k(\emptyset)$ only finitely many subsets happen to be exactly such ordinals.

Sort items by value-to-weight ratio and fill the knapsack greedily, taking a fraction of the last item; this is provably optimal for the fractional knapsack, unlike 0/1.

Schedule unit-time jobs for maximum profit by taking them in decreasing-profit order and placing each in the latest free slot before its deadline — provably optimal because the feasible sets form a matroid.

A binary heap is a complete binary tree stored in an array; MAX-HEAPIFY repairs one node by sifting it down in $\Theta(\lg n)$, while BUILD-MAX-HEAP turns an unordered array into a heap bottom-up in $\Theta(n)$ — not $\Theta(n\lg n)$.

Recognize "strings that avoid a fixed pattern" with a DFA that tracks the longest matched prefix of the pattern and drops into an absorbing non-accepting trap state the instant the whole pattern appears.