The average search time for a hash table using separate chaining with a load factor α is..
A
O(1+α)
B
O(log α)
C
O(α2)
D
O(α)
উত্তরের বিবরণ
একটি hash table-এ যদি separate chaining ব্যবহার করা হয় এবং load factor α থাকে, তবে এর গড় সার্চ সময় (average search time) হবে O(1 + α)। তাই সঠিক উত্তর হলো ক) O(1 + α)।
বিশ্লেষণ:
-
Separate Chaining: সংঘর্ষ (collision) হলে একই স্লটে থাকা উপাদানগুলো একটি linked list-এ সংরক্ষণ করা হয়।
-
Load Factor (α): এটি সংজ্ঞায়িত হয় ( α = \frac{n}{m} ), যেখানে
-
n = উপাদানের সংখ্যা,
-
m = স্লট বা বাকেটের সংখ্যা।
-
-
Hash Function: যদি হ্যাশ ফাংশন ভালো হয় এবং উপাদানগুলো সমভাবে বিতরণ করে, তবে প্রতিটি স্লটে গড়ে α সংখ্যক উপাদান থাকবে।
-
Search Time:
-
সঠিক উপাদান খুঁজতে হলে আগে হ্যাশ ফাংশন দ্বারা সঠিক স্লট খুঁজতে হয় — এর সময় লাগে O(1)।
-
তারপর সেই স্লটে থাকা লিস্টে উপাদান খুঁজতে হয় — গড়ে O(α) সময় লাগে।
-
-
সফল সার্চ: গড়ে লিস্টের অর্ধেক অংশ (≈ α/2) স্ক্যান করতে হয়।
-
অসফল সার্চ: পুরো লিস্ট স্ক্যান করতে হয় (≈ α)।
-
মোট সময়:
[
O(1) + O(α) = O(1 + α)
]
অতিরিক্ত বিশ্লেষণ:
-
যদি α ছোট হয় (α < 1), তবে সার্চ সময় প্রায় O(1)।
-
যদি α বড় হয়, তবে O(α) অংশ প্রাধান্য পায়, কিন্তু O(1 + α) রূপটি সবচেয়ে সঠিক, কারণ এটি উভয় ক্ষেত্রই কভার করে।
অতএব, separate chaining ব্যবহৃত হ্যাশ টেবিলে গড় সার্চ সময় হলো O(1 + α)।
0
Updated: 14 hours ago
Von Neumann architecture uses__________memory for data and instructions.
Created: 14 hours ago
A
separate
B
same
C
no
D
None of the above
Von Neumann architecture-এ data ও instruction উভয়ের জন্য একই মেমরি ব্যবহৃত হয়, তাই সঠিক উত্তর হলো খ) same।
Von Neumann Architecture ব্যাখ্যা:
-
এটি stored-program concept-এর ওপর ভিত্তি করে গঠিত, যেখানে প্রোগ্রামের নির্দেশনা (instructions) এবং ডেটা একই shared memory space-এ সংরক্ষিত থাকে।
-
মূল বৈশিষ্ট্য (Von Neumann Bottleneck): CPU একই বাস (bus) ব্যবহার করে মেমরি থেকে নির্দেশনা ও ডেটা উভয়ই আনে। ফলে এক সময়ে কেবল একটি কাজ (instruction fetch বা data fetch) করা যায়, যা প্রসেসিং গতি কমিয়ে দেয়।
-
Contrast with Harvard Architecture: Harvard স্থাপত্যে instructions ও data-এর জন্য আলাদা মেমরি ও আলাদা বাস থাকে, ফলে একসাথে নির্দেশনা ও ডেটা আনা সম্ভব হয়, যা সিস্টেমকে দ্রুততর করে।
অতএব, Von Neumann স্থাপত্যের মূল বৈশিষ্ট্য হলো — একই মেমরিতে ডেটা ও নির্দেশনা সংরক্ষণ (same memory for both)।
0
Updated: 14 hours ago
প্রোগ্রামিং এ ‘JMP’ অপ-কোডের নির্দেশ কী?
Created: 1 month ago
A
নির্দিষ্ট মেমোরি লোকেশনে যাওয়া
B
কোড কম্পাইল করা
C
আউটপুট ডিভাইস বন্ধ করা
D
রেজিস্টার রিসেট করা
অপ-কোড (Operation Code / Opcode)
সঠিক উত্তর: ক) নির্দিষ্ট মেমোরি লোকেশনে যাওয়া
সংজ্ঞা:
অপ-কোডে ইনস্ট্রাকশন বা কমান্ডের নেমোনিক থাকে যা কম্পিউটারের বিভিন্ন কাজ নির্দেশ করে। নেমোনিকগুলো বিভিন্ন কম্পিউটারে ভিন্ন হতে পারে, তবে অধিকাংশ ক্ষেত্রে সাধারণ নেমোনিকগুলো নিম্নরূপ—
প্রধান অপ-কোড ও তাদের কার্য:
-
STO / STA: Store Accumulator; অ্যাকুমুলেটরের ডাটাকে নির্দিষ্ট মেমোরি লোকেশনে সংরক্ষণ।
-
CLR: Clear Accumulator; অ্যাকুমুলেটর পরিষ্কার করা।
-
ADD: প্রধান মেমোরির নির্দিষ্ট অবস্থানের সংখ্যার সঙ্গে অ্যাকুমুলেটরের সংখ্যা যোগ করা।
-
SUB: প্রধান মেমোরির নির্দিষ্ট অবস্থানের সংখ্যা থেকে অ্যাকুমুলেটরের সংখ্যা বিয়োগ করা।
-
MUL: গুণ করার নির্দেশ।
-
DIV: ভাগ করার নির্দেশ।
-
JMP: পরবর্তী নির্দেশের জন্য নির্দিষ্ট মেমোরি অবস্থানে যাওয়া।
-
INP: ইনপুট নেওয়া; ডাটা প্রধান মেমোরিতে রাখা।
-
OUT: আউটপুট প্রদর্শন; প্রধান মেমোরির তথ্য আউটপুটের মাধ্যমে প্রকাশ করা।
-
STP: প্রোগ্রাম থামানোর নির্দেশ।
0
Updated: 1 month ago
Which of the following is true for the Superposition Theorem?
Created: 14 hours ago
A
Duality
B
Linearity
C
Reciprocity
D
Non linearity
Superposition Theorem প্রযোজ্য হওয়ার জন্য যে মৌলিক গুণটি থাকা আবশ্যক, তা হলো Linearity। তাই সঠিক উত্তর হলো খ) Linearity।
Superposition Theorem ব্যাখ্যা:
-
এটি একটি গুরুত্বপূর্ণ সার্কিট বিশ্লেষণ নীতি, যা একাধিক independent source-যুক্ত সার্কিটকে সরলভাবে বিশ্লেষণ করতে সহায়তা করে।
-
এই তত্ত্ব অনুযায়ী, কোনো linear circuit-এ নির্দিষ্ট একটি পয়েন্টে পাওয়া মোট কারেন্ট বা ভোল্টেজ হলো প্রতিটি উৎস আলাদাভাবে সক্রিয় করলে উৎপন্ন কারেন্ট বা ভোল্টেজের যোগফল।
-
এর জন্য একবারে একটি উৎস সক্রিয় রাখা হয় এবং বাকিগুলো বন্ধ করা হয় —
-
Voltage source বন্ধ করতে সেটিকে short circuit করা হয়।
-
Current source বন্ধ করতে সেটিকে open circuit করা হয়।
-
কেন Linearity অপরিহার্য:
-
Linearity থাকলেই সার্কিটে superposition principle প্রযোজ্য হয়, কারণ তখন ভোল্টেজ ও কারেন্টের সম্পর্ক সরলভাবে যোগফল আকারে প্রকাশ করা যায়।
-
Linear components হলো সেসব উপাদান যেখানে ভোল্টেজ (V) ও কারেন্ট (I) এর সম্পর্ক একটি সরল রেখায় প্রকাশ পায় (যেমন, Ohm’s Law: V = IR)।
-
সার্কিটে যদি non-linear components (যেমন diode বা transistor) থাকে, তাহলে এই তত্ত্ব প্রযোজ্য হয় না।
ভুল বিকল্পগুলো:
-
(ক) Duality: এটি সার্কিটে ভোল্টেজ-কারেন্ট বা ইম্পিডেন্স-অ্যাডমিট্যান্সের পারস্পরিক সম্পর্ক বোঝায়, কিন্তু superposition-এর শর্ত নয়।
-
(গ) Reciprocity: এটি নির্দিষ্ট লিনিয়ার সার্কিটে প্রযোজ্য অন্য একটি থিওরেম, কিন্তু superposition-এর সাথে সরাসরি সম্পর্কিত নয়।
-
(ঘ) Non-linearity: সার্কিটে non-linear উপাদান থাকলে superposition theorem প্রযোজ্য হয় না।
অতএব, Superposition Theorem প্রযোজ্য হওয়ার জন্য সার্কিটের অবশ্যই Linearity থাকতে হবে।
0
Updated: 14 hours ago
