Q1Easy
Bellman's principle of optimality states that:
பெல்மேனின் உகந்த கொள்கை பின்வருமாறு கூறுகிறது:
- aWhatever initial state and decision, remaining decisions must be optimal for resulting state — ஆரம்ப நிலை மற்றும் முடிவு எதுவாக இருந்தாலும், மீதமுள்ள முடிவுகள் அதன் விளைவாக வரும் நிலைக்கு உகந்ததாக இருக்க வேண்டும்✓ Correct
- bEvery subproblem can be solved independently without tracking state transitions — நிலை மாற்றங்களைக் கண்காணிக்காமல் ஒவ்வொரு துணைக் கணக்கையும் சுயாதீனமாக தீர்க்க முடியும்
- cThe overall objective value is strictly equal to the sum of greedy local optima — ஒட்டுமொத்த குறிக்கோள் மதிப்பு பேராசை உள்ளூர் உகந்த மதிப்புகளின் கூட்டுத்தொகைக்கு கண்டிப்பாக சமம்
- dOptimal solutions are achieved exclusively when backward recursion equals forward recursion — பின்னோக்கிய மறுநிகழ்வு முன்னோக்கிய மறுநிகழ்வுக்கு சமமாக இருக்கும்போது மட்டுமே உகந்த தீர்வுகள் அடையப்படுகின்றன
Explanation
Principle of optimality: an optimal policy's tail is optimal for the remaining subproblem (Bellman, 1957).
உகந்த கொள்கை: மீதமுள்ள துணைப் பிரச்சனைக்கு உகந்த கொள்கையின் வால் உகந்ததாகும் (பெல்மேன், 1957).
Q2Easy
In dynamic programming, the state captures:
டைனமிக் நிரலாக்கத்தில், மாநிலம் கைப்பற்றுகிறது:
- aAn arbitrary index enumeration of decision alternatives available at current step — தற்போதைய படியில் கிடைக்கும் முடிவு மாற்றுகளின் தன்னிச்சையான குறியீட்டு பட்டியல்
- bAll information needed to make an optimal decision at current stage — தற்போதைய கட்டத்தில் உகந்த முடிவை எடுக்க தேவையான அனைத்து தகவல்களும்✓ Correct
- cThe total number of stages remaining until the planning horizon is reached — திட்டமிடல் எல்லை அடையும் வரை மீதமுள்ள நிலைகளின் மொத்த எண்ணிக்கை
- dThe cumulative cost incurred from the initial stage up to the terminal stage — ஆரம்ப கட்டத்திலிருந்து இறுதி கட்டம் வரை ஏற்பட்ட திரட்டப்பட்ட செலவு
Explanation
State: sufficient statistic for future decisions; Markov property ensures current state summarizes relevant past.
மாநிலம்: எதிர்கால முடிவுகளுக்கு போதுமான புள்ளிவிவரம்; மார்கோவ் சொத்து தற்போதைய நிலை தொடர்புடைய கடந்த காலத்தை சுருக்கமாக உறுதிப்படுத்துகிறது.
Q3Easy
The recurrence relation in dynamic programming (backward recursion) is:
டைனமிக் புரோகிராமிங்கில் (பின்னோக்கிய மறுநிகழ்வு) மறுநிகழ்வு உறவு:
- af_t(s) = min_{a} [c_t(s,a) + f_{t+1}(s'(s,a))] — f_t(s) = min_{a} [ c_t(s,a) + f_{t+1}(s'(s,a))]✓ Correct
- bf_t(s) = c_t(s,a) - f_{t+1}(s) — f_t(s) = c_t(s,a) - f_{t+1}(கள்)
- cf_t(s) = max_{s'}[c_t(s,s')] — f_t(s) = அதிகபட்சம்_{s'}[ c_t(s,s') ]
- df_t(s) = f_{t+1}(s) + c_t(s) — f_t(s) = f_{t+1}(கள்) + c_t(s)
Explanation
Bellman equation: optimal value function satisfies V(s) = min_a [c(s,a) + gamma*V(s')] for discounted problems.
பெல்மேன் சமன்பாடு: உகந்த மதிப்பு செயல்பாடு V(s) = min_a [c(s,a) + gamma* c_t(s,a)0 ] தள்ளுபடி சிக்கல்களுக்கு திருப்தி அளிக்கிறது.
Q4Easy
The shortest path problem from source s to all vertices can be solved by dynamic programming (Dijkstra's algorithm for non-negative weights) in time:
மூல s முதல் அனைத்து முனைகளுக்கும் உள்ள குறுகிய பாதை பிரச்சனையை டைனமிக் புரோகிராமிங் மூலம் (எதிர்மறை அல்லாத எடைகளுக்கான Dijkstra இன் அல்காரிதம்) தீர்க்க முடியும்:
- aO((V + E) * log V) using a priority queue (min-heap implementation) — முன்னுரிமை வரிசையைப் பயன்படுத்தி O((V + E) * log V) (min-heap செயல்படுத்தல்)✓ Correct
- bO(V * E) for arbitrary graphs containing potential negative cycle weights — சாத்தியமான எதிர்மறை சுழற்சி எடைகளைக் கொண்ட தன்னிச்சையான வரைபடங்களுக்கு O(V * E)
- cO(V^3) by computing all-pairs shortest paths via matrix multiplications — அணிப் பெருக்கல்கள் மூலம் அனைத்து ஜோடி குறுகிய பாதைகளையும் கணக்கிடுவதன் மூலம் O(V^3)
- dO(V + E) by topological ordering restricted to directed acyclic graphs — திசைசார் சுழற்சியற்ற வரைபடங்களுக்கு மட்டுப்படுத்தப்பட்ட இடவியல் வரிசைப்படுத்தல் மூலம் O(V + E)
Explanation
Dijkstra with a min-heap: O((V+E) log V); O(V^2) with adjacency matrix.
ஒரு நிமிடக் குவியலுடன் கூடிய Dijkstra: O((V+E) பதிவு V); பக்கத்து அணியுடன் O(V^2).
Q5Easy
The 0/1 Knapsack problem with n items and capacity W is solved by DP in time:
n உருப்படிகள் மற்றும் திறன் W உடன் 0/1 நாப்சாக் பிரச்சனை DP ஆல் சரியான நேரத்தில் தீர்க்கப்படுகிறது:
- aO(n*log(W))
- bO(2^n)
- cO(n^2)
- dO(n*W)✓ Correct
Explanation
Knapsack DP: dp[i][w] = max value using first i items with capacity w; O(nW) time and space.
நாப்சாக் DP: dp[i][w] = திறன் கொண்ட முதல் i பொருட்களைப் பயன்படுத்தி அதிகபட்ச மதிப்பு; O(nW) நேரம் மற்றும் இடம்.
20 more questions on Dynamic Programming and Decision Theory
Track your mastery, build a daily streak, and compete on the leaderboard across all 1 PG TRB subjects.