Leseplan - 5. Semester

Uke\Ukedag	Mandag	Tirsdag	Onsdag	Torsdag	Fredag	Lørdag	Søndag
Uke 47	-	-	-	-	D: Eksamen 2022	D: Filterdesign A: Problemer og algoritmer	D: Kap 12 og 14 (estimering) A: Datastrukturer
Uke 48	D: A: Splitt og hersk	D: A: Rangering i lineær tid	D: A: Rotfaste trestrukturer	D: A: Dynamisk programmering	D: A: Grådighet og stabil matching	D: A: Traversering av grafer	D: 2018k A: Minimale spenntrær
Uke 49	D: 2017h A: Korteste vei fra en til alle	D: Eksamen 2017k	D: Eksamen 2015/2022	Eksamen Digsig	A: Korteste vei fra alle til alle, Maksimal flyt	A: NP	A: Eksamen 20__
Uke 50	A: Eksamen 20__	Eksamen Algdat				K2019	H2019, K2022
Uke 51	L: H2022	Eksamen Linsys		-	-	-	Julaften

Digital Signalbehandling, 07.12.2023

Forelesningsplan: TTT4120_forelesningsplan_h2023.pdf Formelark: TTT4120_formulas.pdf

.	Gjort	Bemerkninger
2022	x	3e,3f
2019	x	1c, 2, 4d, 4f
2018h	x	1a, 2b, 3b, 4c
2018k	x	3b,3c
2017h
2017k
2015
2014
2012

**Spørsmål:**1

1. Forskjell på Autocovariance og Autocorrelation. Hvorfor er

$$\begin{array}{rl}{\gamma }_{vv}(l)& ={\sigma }_v^2\delta (l)\\ A_v& ={\sigma }_v^2\delta (0)\end{array}$$

* $\delta(l)=0 \;\forall\; l\neq 0$ 

1. Plassering av multiplikasjonstegn i opg2b. Blir det annerledes?

Svakheter:

• Filterdesign og estimering
• Minimum phase
• Forskjell FT,DFT,DTFT
• radix-2-fft
• Linear prediction

Pugg:

• Scaling factor $A_x\le \frac{1}{{\sum }_{n=-\infty }^{\infty }|h[n]|}$
• Evaluate the performance of an AR(2) estimate: ${\sigma }_f^2={\gamma }_{xx}[0]+a_1{\gamma }_{xx}[1]+a_2{\gamma }_{xx}[2]$
• Minimum length of radix-2 FFT needed to compute a signal $N_{FFT}=2^{\nu }>M+L-1$, where $M+L-1$ is the length of the sequence $Y(k)$
• Autocorrelation estimators
  • 1. ${\hat{\gamma }}_{xx}[l]=\frac{1}{N}{\sum }_{n=0}^{N-|l|-1}x[n]x[n+|l|]$
    • $E\{{\hat{\gamma }}_{xx}[l]\}=\left(1-\frac{|l|}{N}\right){\gamma }_{xx}$, BIASED FOR $l\ne 0$ or $N<\infty$
    • ${\lim }_{N\to \infty }var\{{\hat{\gamma }}_{xx}[l]\}=0$
  • 2. ${\hat{\gamma }}_{xx}[l]=\frac{1}{N-|l|}{\sum }_{n=0}^{N-|l|-1}x[n]x[n+|l|]$
    • $E\{{\hat{\gamma }}_{xx}[l]\}={\gamma }_{xx}[l]$ UNBIASED
    • ${\lim }_{N\to \infty }var\{{\hat{\gamma }}_{xx}[l]\}=0$, BUT variance increases as $|l|\to N$
• ${\sigma }_e^2=\frac{2^{-2B}}{12}$
• Linear phase if we have a point of symmetry!!!

Algoritmer og Datastrukturer, 12.12.2023

Oversikt: Oversikt AlgDat Pensumoversikt: Pensumoversikt AlgDat Forelesningsplan: TDT4120_forelesningsplan_h2023

Les:

• Rekurrensligninger (Master-theorem spesielt, Substitution Method)
• Korrekthetsbevis
• Kap 9
• Amortisert tid
• Trestrukturer
• Binære ryggsekkproblemet
  • Kodingen av en problem instans har mye å si for kompleksiteten av å løse problemet. Kompleksiteten er direkte avhengig av størrelsen på input som igjen avhenger av kodingen av probleminstansen. Ta for eksempel det binære ryggsekkproblemet (se appendiks D). Om vi koder heltall i entallssystemet og ikke totallssystemet, så går kjøretiden fra å være eksponentiell til polynomisk (3, Ø13)
• Kantklassifisering (19,20 ø8)
• Parantesteoremet
• Heuristics to improve the running time (19.3)
• MST-PRIM
• Ø10 opg 12
• Slow, fast asps (opg9 2022h)
• Opg 5, Ø12
• Maskimal flyt
• H2022, 16
• LCS

Spørsmål:

• Hvorfor er top down mer overhead enn bottom up? (Dynamisk programmering)
  • Flere funksjonskall (Derav høyere konstant)
• Hvordan lagrer egt bottom up variablene i cut rod? Mtp at vi risikerer å løse samme delproblem flere ganger

Dump kræsjkurs:

• Visualiser oppgavene, tegninger.
• Master teoremet med substitution ($T(n)=T(\sqrt{n})+n$, $n=2^m$ → $s(m)$ → $T(n)=\Theta (n)$)
• Reduser fra et NPC problem til problemet for å bevise NPC. Ikke motsatt

.	Gjort	Bemerkninger
2023k
2022h
2022k
2019h
2019k
2018h
2018k
2017h
2017k

Svakheter:

• Fredrik :D

Lineær Systemteori, 19.12.2023

Forelesningsplan: TTK4115_forelesningsplan_h2023.png Pensumoversikt: TTK4115-Pensum Oversikt

Vanskelig

• Opg1 ø3
• opg5 ø4
• h2021, opg 5b

Pugg:

• Algebraic equivalence $⟹$ Zero-state equivalence
• Minimal Realizations
  • A system is a minimal realization if and only if $dim(A)=deg(\hat{G}(s))$
  • A system is a minimal realization if and only if it is controllable and observable.
• Kalman filter
  • More noise (higher value or $R_v$) gives lower Kalman gain (less emphasis on measurements)
  • Stronger disturbance (higher values of $Q_w$) gives higher Kalman gain (less emphasis on the model)
• Transformation matrices ($\bar{x}=Tx$)
  • Diagonal form - $\Lambda =Q^{-1}AQ$, $T=Q^{-1}$
  • Modal form - $T=M=\left[\begin{array}{cc}1/2& -i/2\\ 1/2& i/2\end{array}\right]$
• Integral Effect
  • Given this plant$$ \begin{align} \dot{x}&=Ax+Bu+Bw \ y&=Cx \end{align}

* We add $x_{a}$. and can later state feedback+reference feedforward * $x_{a}=\int _{0}^tr(\tau)-Cx(\tau) \, d\tau$ * ![[Pasted image 20231218203149.png]] * LQR * Feedforward | . | Gjort | Bemerkninger | | ----- | ----- | ------------ | | 2022h | | | | 2021h | | | | 2021k | | | | 2019h | | | | 2019k | | | | 2018h | | | | 2017h | | | | 2017k | | |