پیمایش (Traversal) در علوم کامپیوتر به معنای بازدید از تمامی گرهها یا عناصر یک ساختار دادهای به منظور انجام عملیات خاصی روی آنها است. عملیات پیمایش یکی از اجزای اساسی در بسیاری از الگوریتمها و ساختارهای دادهای مانند درختها، گرافها و لیستها است. در این فرایند، هدف این است که به هر گره یا عنصر از ساختار داده دسترسی پیدا کرده و عملیاتهای مختلفی مانند جستجو، ویرایش یا نمایش دادهها را انجام دهیم.
پیمایش در ساختارهای دادهای مختلف میتواند به روشهای مختلفی انجام شود. در اینجا به بررسی چند نوع اصلی پیمایش میپردازیم که بیشتر در درختها و گرافها کاربرد دارند:
در پیمایش پیشوندی، ابتدا داده گره جاری بازدید میشود، سپس به ترتیب گرههای فرزند چپ و راست (در درختهای دودویی) بازدید میشوند. این نوع پیمایش بهویژه در زمانی که نیاز به ذخیرهسازی ساختار درخت یا انجام عملیاتی قبل از بررسی فرزندان است، کاربرد دارد.
# پیمایش پیشوندی درخت دودویی def pre_order(node):
if node:
print(node.data, end=" ") # بازدید از گره جاری
pre_order(node.left) # پیمایش فرزند چپ
pre_order(node.right) # پیمایش فرزند راست در پیمایش پسوندی، ابتدا فرزندان چپ و راست بازدید میشوند و سپس داده گره جاری. این نوع پیمایش معمولاً در مواردی که لازم است ابتدا تمامی عملیاتهای فرزندان انجام شوند و سپس عملیات روی گره جاری انجام گردد، مفید است.
# پیمایش پسوندی درخت دودویی def post_order(node):
if node:
post_order(node.left) # پیمایش فرزند چپ
post_order(node.right) # پیمایش فرزند راست
print(node.data, end=" ") # بازدید از گره جاری در پیمایش میانهای، ابتدا گره فرزند چپ بازدید میشود، سپس داده گره جاری و در نهایت فرزند راست بازدید میشود. این نوع پیمایش بهویژه در درختهای دودویی جستجو (Binary Search Tree) کاربرد دارد، زیرا با این روش، دادهها به ترتیب مرتب شده نمایش داده میشوند.
# پیمایش میانهای درخت دودویی def in_order(node):
if node:
in_order(node.left) # پیمایش فرزند چپ
print(node.data, end=" ") # بازدید از گره جاری
in_order(node.right) # پیمایش فرزند راست در پیمایش سطح به سطح (که به آن پیمایش به روش صف نیز گفته میشود)، ابتدا گره ریشه بازدید میشود، سپس گرههای هر سطح از درخت به ترتیب از چپ به راست بررسی میشوند. این نوع پیمایش معمولاً با استفاده از صف (Queue) انجام میشود.
# پیمایش سطح به سطح درخت دودویی با استفاده از صف from collections import deque def level_order(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.data, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right) پیمایش در گرافها به دو روش اصلی انجام میشود: پیمایش به روش عمق اول (DFS) و پیمایش به روش عرض اول (BFS).
در این روش، ابتدا یک گره انتخاب میشود، سپس بهطور عمقی به سراغ فرزندهای آن گره میرود تا زمانی که به گرهای برسد که دیگر فرزند نداشته باشد یا به گرهی که قبلاً بازدید شده است، برخورد کند.
# پیمایش به روش عمق اول (DFS) با استفاده از بازگشت def dfs(node, visited):
if node not in visited:
print(node.data, end=" ")
visited.add(node)
for neighbor in node.neighbors:
dfs(neighbor, visited) در این روش، ابتدا گره ریشه بازدید میشود، سپس بهطور عرضی به بررسی گرههای همسطح پرداخته میشود. این پیمایش معمولاً با استفاده از صف (Queue) انجام میشود.
# پیمایش به روش عرض اول (BFS) با استفاده از صف def bfs(root):
if not root:
return
queue = deque([root])
visited = set([root])
while queue:
node = queue.popleft()
print(node.data, end=" ")
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) پیمایشها در بسیاری از مسائل کاربرد دارند، از جمله:
در نهایت، پیمایش یکی از عملیاتهای اساسی در علوم کامپیوتر است که برای دسترسی و پردازش دادهها در ساختارهای دادهای مختلف بهکار میرود. برای آشنایی بیشتر با مفاهیم پیمایش و دیگر ساختارهای دادهای، میتوانید به سایت saeidsafaei.ir مراجعه کنید و از اسلایدهای محمد سعید صفایی بهرهمند شوید.
در این مبحث، به شناخت، انواع و طرز استفاده از آرایهها پرداخته میشود و چندین مثال عملی با استفاده از فلوچارت و آرایهها رسم خواهیم کرد. همچنین، با توجه به اهمیت فلوچارت در طراحی الگوریتمها، در بخش دوم اسلایدها، چندین تمرین مهم با رسم فلوچارت در اختیار شما قرار خواهد گرفت تا مهارتهای عملی شما در این زمینه تقویت شود.
ماشینی است قابل برنامهریزی که از اجزای الکترونیکی و الکترومکانیکی تشکیل شده است و میتواند دادهها و دستورات را از محیط خارج دریافت کرده، آنها را پردازش کرده و نتایج را تحویل دهد.
ساختارهایی در برنامهنویسی شیگرا هستند که دادهها و متدهای مربوط به آنها را به یک واحد منطقی گروهبندی میکنند.
مدلسازی سهبعدی به فرآیند ایجاد مدلهای دیجیتالی از اشیاء یا محیطها با استفاده از نرمافزارهای کامپیوتری اطلاق میشود.
فرآیند تبدیل اطلاعات به کدی غیرقابل فهم برای محافظت از دادهها در برابر دسترسی غیرمجاز.
سیگنال آنالوگ سیگنالی است که میتواند هر مقدار پیوستهای از دادهها را منتقل کند.
تبدیل نوع به فرآیند تبدیل یک نوع داده به نوع دیگر در زبانهای برنامهنویسی گفته میشود. این کار برای اطمینان از هماهنگی انواع دادهها در برنامه انجام میشود.
پروتکلی که ترکیبی از ویژگیهای Distance Vector و Link State است و از نقاط قوت هر دو استفاده میکند.
این واژه به پردازش دادهها در نزدیکی محل ایجاد آنها (در لبه شبکه) اشاره دارد، بهجای ارسال دادهها به مراکز داده اصلی. این باعث کاهش تأخیر و مصرف پهنای باند میشود.
نویز ناشی از انتقال سیگنالها از یک خط به خط دیگر، که معمولاً در کابلهای جفت تابیده یا کابلهای چند هستهای رخ میدهد.
نرمافزارهایی هستند که وظیفه مدیریت منابع سختافزاری و نرمافزاری یک کامپیوتر را بر عهده دارند.
سیستم عددی مبنای 16 است که از ارقام 0 تا 9 و حروف A تا F برای نمایش اعداد استفاده میکند.
انتزاع به پنهان کردن جزئیات پیچیده و تنها نشان دادن جنبههای ضروری یک شیء یا فرآیند گفته میشود.
بینایی رباتها به فناوریهایی اطلاق میشود که به رباتها امکان شبیهسازی دید انسان را میدهند تا محیط اطرافشان را درک کنند.
عملگر یا دستور کانتینیو برای ادامه دادن به مرحله بعدی در یک حلقه یا فرایند استفاده میشود.
پارامترها مقادیری هستند که به یک تابع داده میشوند و به عنوان ورودی تابع عمل میکنند.
عملگرهای مقایسهای برای مقایسه دو مقدار و تعیین روابط آنها مانند بزرگتر از، کوچکتر از و مساوی استفاده میشوند.
دستگاههای متصل به شبکه که دادهها را ارسال یا دریافت میکنند، مانند کامپیوترها، سرورها، یا سایر تجهیزات شبکه.
شبکهای که در محدودهای جغرافیایی محدود مانند یک ساختمان یا اداره قرار دارد و به اشتراکگذاری منابع بین دستگاهها میپردازد.
آزادسازی حافظه به فرآیند آزاد کردن حافظه اختصاصیافته به برنامه یا دادهها پس از پایان استفاده از آنها اطلاق میشود.
سیستمهای دفترکل توزیعشده (DLS) به استفاده از شبکههای غیرمتمرکز برای ذخیرهسازی و مدیریت دادهها با شفافیت و امنیت اشاره دارد.
شبکههای خودترمیمی به شبکههایی اطلاق میشود که قادر به شناسایی و اصلاح خطاها یا مشکلات خود بهطور خودکار هستند.
عملگرهایی هستند که برای انجام عملیات منطقی مانند AND, OR, NOT و XOR بر روی دادهها به کار میروند.
سیگنال دیجیتال یک نوع سیگنال است که در آن اطلاعات به صورت دادههای دیجیتال (0 و 1) منتقل میشوند.
بلاکچین برای مدیریت هویت به استفاده از شبکههای بلاکچین برای ایجاد سیستمهای شفاف و غیرمتمرکز مدیریت هویت افراد اطلاق میشود.
شیوهای برای سازماندهی و ذخیرهسازی دادهها به گونهای که دسترسی به آنها سریعتر و مؤثرتر باشد. انواع مختلفی از ساختار داده مانند آرایهها، لیستهای پیوندی و درختها وجود دارد که هر یک برای مسائل خاصی مناسب هستند.
مقداردهی اولیه به متغیرها یا دادهها به معنای اختصاص مقدار اولیه به آنها پیش از استفاده در برنامه است.
اضافه بار یا اوورفلو زمانی رخ میدهد که سیستم محاسباتی نمیتواند عددی بزرگتر از ظرفیت ذخیرهسازی خود را پردازش کند.
آدرسهای IP که از subnet maskهای غیر استاندارد استفاده میکنند، ناشی از عملیاتهای Subnetting و Supernetting.
عبور پارامتر به معنای ارسال دادهها از برنامه اصلی به یک تابع هنگام فراخوانی آن است. این دادهها به پارامترهای تابع منتقل میشوند تا در داخل آن پردازش شوند.
بلاکچین 2.0 به نسخهای پیشرفته از بلاکچین گفته میشود که ویژگیهایی مانند قراردادهای هوشمند و مقیاسپذیری بهتر را ارائه میدهد.
کامپیوترهای آنالوگ برای پردازش دادههای پیوسته مانند دما، فشار و سرعت طراحی شدهاند.
نرمافزارهای کاربردی هستند که برای انجام کارهای خاص مانند پردازش کلمات، تجزیه و تحلیل دادهها و طراحی گرافیکی استفاده میشوند.
ثباتها یا رجیسترها حافظههای بسیار سریع و کوچک هستند که درون پردازنده قرار دارند. آنها برای ذخیرهسازی دادهها و دستورالعملهای پردازش شده با سرعت بالا استفاده میشوند.
سیستمهای پرواز خودران به هواپیماها و وسایل پرنده اطلاق میشود که قادر به انجام عملیات پروازی بهطور خودکار هستند.
یادگیری انتقالی به روشی برای استفاده از مدلهای آموزشدیده در یک دامنه بهمنظور بهبود عملکرد در دامنههای دیگر گفته میشود.
