אני שוקל ללמוד מדעי המחשב בתיכון.

זה מה שאמרו לנו שנלמד שם (לאחר כל ציטוט ממה שאמרו לנו,ישנה שאלה שלי שאשמח שתענו ,ובבקשה תסבירו לי במילים פשוטות כי אני מתחיל בכל הנושא הזה) :

"לימוד לקראת פיתוח וניתוח אלגוריתם מילולי לפתרון בעיה וכתיבת תכנית מחשב מובנית,המיישמת את הפתרון. "

*שאלתי : מה זה אלגוריתם ? ולמה הכוונה בפיתוחו וניתוחו ?

"להכיר את עקרונות העברת המידע באינטרנט (html, javascript ), להכיר את המושגים הבסיסיים של ASP ולאפשר לתלמידים ליצור אתרים אינטראקטיביים"

*שאלתי : בכלליות מה זה html ? javascript ? asp ?

"תורת המחשב - אוטומטים, דקדוקים, שפות פורמליות ותורת הגרפים."

*שאלתי : מה פירוש שפות פורמליות ותורת הגרפים ?

1) אלגוריתם - רצף פעולות לפתרון בעיה כלשהי. פיתוח אלגוריתם - מציאת רצף הפעולות האלה. ניתוח אלגוריתם - כנראה הכוונה לחישוב זמן ריצה.

2)ASP - שפת תכנות צד שרת באינטרנט(אתה לא רואה את הקוד). JS - שפת פיתור צד לקוח(אתה יכול לראות את הקוד). HTML - שפת תאגים להצגת אתרים(גם כאן אתה רואה את הקוד).

3) שפות פורמליות - קבוצת מילים המקיימות חוקים כלשהם(חוקים המוגדרים באמצעות מונחים מן המתמטיקה - לוגיקה, תורת הקבוצות וכו'). תורת הגרפים - גרף הוא אוסף קודקודים וקשתות המחברות ביניהם(אתה תעסוק בהגדרות כנראה, מחוקים שנוצרו כתוצאה מההגדרות, ובאלגוריתמים שיעסקו לפתרון בעיה מסויימת בגרפים).

לדוגמא(אם לא תצליח לפתור את הבעיה הזו לא כדאי לך ללכת):

מצא אלגוריתם שמוצא תת גרף(שבו אין קשתות בין כל 2 קודקודים בו) מגרף נתון. זמן הריצה צריך להיות O(|V|+|E|) כאשר V זו קבוצת הקודקודים, ו- E זו קבוצת הקשתות. הפעולה |V| מחזירה את הגודל של V.

אתה יודע מה, גם אם לא תצליח לעשות את זה לפי ההגבלה של זמן הריצה(אלא תצליח למצוא אלגוריתם כלשהו) כדאי לך ללכת.

אם תמצא אלגוריתם כזה אתה סוס.

קודם כל תודה על העזרה.

אני לא אמור לפתור כזה דבר,כי אנחנו מתחילים מהבסיס של הבסיס מה שנקרא.

אמרו לנו בפירוש שאין צורך לבוא עם ידע מוקדם בנושאים האלה,ששם נלמד הכל הכל מהתחלה.

אז רק תנסה..

כל מה שאתה צריך זה לאהוב את המקצוע וגם קצט היגיון וגישה לנושא

בקיצור אם אתה ראלי אז שווה ללכת לכיבון הטכנולוגי

מצא אלגוריתם שמוצא תת גרף(שבו אין קשתות בין כל 2 קודקודים בו) מגרף נתון. זמן הריצה צריך להיות O(|V|+|E|) כאשר V זו קבוצת הקודקודים, ו- E זו קבוצת הקשתות. הפעולה |V| מחזירה את הגודל של V.

אני אפילו לא הבנתי מה אתה רוצא ממנו ואני בוגר מגמת מחשבים ורובוטיקה וגם הנדסאי אלקטרוניקה

ואף פאם לא שאלו אותי משהוא דומה לזה

אז לא משנה.. גם ככה לא הייתם מצליחים לפתור את זה.

ככה, אתה רוצה תת גרף שבין כל שתי קדקדים שבו אין קשת. הפתרון הטריוויאלי (אך נכון) הוא תת גרף ריק (שים לב, הוא מקיים את הדרישות שלך) זמן ריצה - קבוע.

אני מניח שרצית תת גרף מקסימלי שמקיים את שביקשת, כלומר למצוא אוסף מקסימלי של קדקדים שבין כל שתיים מהם אין צלע.

הדרך ההכי "פשוטה" שאני יכול לחשוב עליה היא: נמצא את כל רכיבי הקשירות של הגרף, (באמצעות 2 סריקות bfs - אורדר של מספר הצלעות) ואח"כ נבחר נציג מכל רכיב כזה - אורדר של מספר הרכיבים ~ הקדקדים.

זמן ריצה במקרה הגרוע, מספר הצלעות + הקדקדים.

שני אגבים, אמנם השאלה פתירה והיא די קלה אבל היא לא ברמה של ידע כללי של תלמיד תיכון.

דבר שני, לא חשוב באיזו רמה השאלה, נהוג להגדיר היטב את תנאי הבעיה.

מטי.

זה לא המקסימאלי..

אם כבר העלינו את הדיון בכמה רמות,

זה כן המקסימלי (למעשה ההוכחה שזה המקסימלי פשוטה, אבל ניתן לך לחשוב על זה)

מטי.

תפעיל את האלגוריתם שלך עם הגרף הזה.

[attachment deleted by admin]