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

A* expands the frontier node of smallest $f(n)=g(n)+h(n)$; an admissible heuristic makes tree-search A* optimal while the stronger consistency condition is needed for graph-search A*, and real-time cousins like LRTA* trade optimality for a bounded $O(n^2)$ worst case.

Any deterministic algorithm that sorts $n$ distinct keys using only comparisons needs $\lceil \log_2(n!)\rceil = \Omega(n\log n)$ comparisons in the worst case, because its decision tree must have at least $n!$ leaves.

Overall speedup is limited by the un-accelerated fraction: improve a part by dividing only its time-fraction by its local speedup, while CPU time itself is set by instruction count, average CPI, and clock period.

Split every address into tag/index/offset (offset = log2 block, index = log2 of the number of SETS), place blocks by the mapping (direct / set-associative / fully associative), evict by the replacement policy (e.g. LRU), and rate the design with the hit ratio and AMAT.

A hazard is a dependency that stops the next instruction from entering its stage on time; structural, data, and control hazards are resolved by stalling, forwarding, branch prediction, or compiler reordering.

Normal forms are a nested hierarchy 1NF ⊇ 2NF ⊇ 3NF ⊇ BCNF ⊇ 4NF that progressively removes redundancy by restricting which functional dependencies a schema may keep; classify a relation by first computing its candidate keys, then decompose losslessly (mandatory) and — where possible — dependency-preservingly (guaranteed only down to 3NF).

NAND and NOR are universal because De Morgan turns any two-level AND-OR into a NAND-NAND (or OR-AND into NOR-NOR) network; a static-1 hazard in such a circuit is a momentary glitch fixed by adding one redundant consensus term.

Match each required operation to the cheapest structure that supports it; when an ADT mixes order queries with lookup-by-identity, combine a balanced BST (or heap) with a hash index instead of forcing one structure to do everything.

A complementary NMOS/PMOS pair gives a sharp rail-to-rail VTC whose switching threshold $V_M$ is set by the $\beta_n/\beta_p$ sizing ratio, and whose power is dynamic ($CV_{DD}^2 f$) plus a short-circuit pulse that peaks exactly at $V_M$.

Pick a MOSFET's region from its overdrive vs. $V_{DS}$ and the matching current law, then model the on-transistor as a switched resistor $R\propto 1/W$ driving node capacitance $C\propto W$ to estimate gate delay and switching energy — remembering that each network speeds only the edge it drives.

Two area-saving alternatives to static CMOS: pass-transistor logic steers inputs through MOS switches (mind the threshold drop, strong-vs-weak pull-up races, and output conflicts), while dynamic/domino logic precharges then evaluates (mind charge sharing).

Short-term scheduling picks the next ready process for the CPU; you must know each algorithm's preemption behavior plus the standard time metrics (turnaround, waiting, response).

A monitor is a high-level synchronization construct that bundles shared data with an implicit lock granting one-thread-at-a-time access, plus condition variables for blocking wait/signal coordination without busy waiting.

Virtual memory keeps only part of a process resident and pages the rest on demand; the MMU translates and protects every access in hardware, multi-level segmentation+paging slices the logical address into countable table fields, and the working-set / page-fault-frequency models keep total frame demand under capacity to avoid thrashing.

The Fourier transform turns convolution into multiplication, so an LTI system's output spectrum is just the input spectrum times the frequency response.

A pole-zero map is ambiguous: only the ROC — always a pole-free strip (Laplace) or ring (Z) whose side is fixed by causality or absolute-summability — pins down the signal and its stability verdict; two-sided signals intersect their causal and anti-causal ROCs, and a causal impulse response is read straight off the power-series (long-division) expansion of H(z).

Classify a system by testing four independent properties — linearity, time-invariance, causality, stability — and remember that any time-scaling or shifting of the input argument breaks time-invariance while a future argument breaks causality.

CFLs are closed under union, concatenation, star, homomorphism and intersection-with-regular, but NOT under intersection or complement; deterministic CFLs flip exactly the complement rule (closed under complement, open under union/intersection).

Three workhorse techniques — u-substitution (reverse chain rule), integration by parts (reverse product rule), and partial fractions — reduce most integrals to standard forms like logs and arctangents.

Count with the sum/product rules, then classify by whether order matters (permutation vs. combination) and whether repetition is allowed; reach for inclusion–exclusion on "at least one / none" constraints and the gap method for no-two-adjacent placements.

A propositional formula is fixed by its truth table, and everything else — logical equivalence, validity, inference rules, and 'how many functions imply another' — reduces to comparing or counting the rows where formulas are true.

An intelligent agent maps percept histories to actions to maximize a performance measure; PEAS specifies the task, and it is the nature of the task environment—not the sensors, actuators, or designer—that caps how well any agent can behave.

Supervised classifiers differ by how they draw a decision boundary and how they generalize — SVM maximizes the margin using only support vectors, kernels lift data to higher dimensions, while tree ensembles do implicit feature selection and distance methods die under many irrelevant features.

A greedy algorithm builds a solution by repeatedly taking the locally best choice; it is optimal exactly when the problem has the greedy-choice property plus optimal substructure, proved by an exchange argument.

Model a recursive algorithm's cost as a recurrence, then read its asymptotic order off the Master Theorem — or, when the shape doesn't fit, via variable substitution, Akra–Bazzi, or a recursion tree.

Every SQL SELECT compiles to relational algebra, so knowing the clause-to-operator map lets you count operators, simplify joins to products/intersections, and read division as a for-all query.

A sequential circuit is combinational logic plus flip-flop memory; you design it by turning a state diagram into a state table and reading off each flip-flop's next-state (excitation) equations.

TCP delivers a reliable, in-order byte stream using cumulative ACKs, while pacing itself with two windows: a receiver-set flow-control window and a sender-computed congestion window that grows by slow start then congestion avoidance.

Discrete probability reduces either to counting equally-likely outcomes with binomial coefficients, or to counting successes in independent trials via the Binomial distribution — often by folding a multi-stage experiment into one per-trial success probability.

A confidence interval brackets a population parameter as $\hat\theta \pm z\,\mathrm{SE}$, while a hypothesis test standardizes the estimate under $H_0$ and rejects when the $p$-value falls below $\alpha$.