מילות קישור מסייעות לחבר את חלקי השיח, הן קיימות בין פסקאות (בעברית כמילה הפותחת את המשפט הפותח של הפיסקה), בתוך משפטים מורכבים הבנויים מאוסף משפטים חלקיים (פסוקיות), בתוך משפטים מאוחים - בעלי נושא אחד אך פעולות אחדות (יותר מנשוא אחד), ואפילו במשפטים פשוטים - בעלי נושא יחיד ונשוא יחיד.
לדוגמה בכיתוב הבא:
לעיתים יש מילות קישור שמתאימים אך ורק למשפט הפשוט או המאוחה, בעוד מילים אחרות משמשות למשפטים מורכבים. לדוגמה: הביטוי "כמו כן", והביטוי "בניגוד ל" משמשים במשפט הפשוט והמאוחה, בעוד המילית המשעבדת "ש" משמשת במשפט המורכב.
סוגי מילות הקישור.
מילות הקישור מתחלקות לפי נושאים:
להלן נושאי מילות הקישור, ודוגמה אחת מכל נושא. ישנן מילות קישור רבות אחרות.
לכידות מתפקיד רקע תימטי במבנה התחבירי.
ראו בהרחבה: מבנים תחביריים , יחס תימטי (בלשנות) וכן תפקידי תיטה
לדעת זליג הריס, אותה פיתח בהמשך תלמידו נעם חומסקי ופרסם בשנת 1957, השיח הלכיד הקיים בכלל השפות שבעולם בנוי ממשפטים שנוסחו בראשו של המשוחח על פי תבניות תחביריות קבועות. במרכזו של כל משפט יש את הפעולה, וסביבה נמצאים משלימי הפעולה. לכל אחת מהפעולות בשפה יש מספר נתון של משלימים, ההכרחיים לאותה הפעולה. החסרת משלימים אלו או הוספת משלימים מיותרים הם הגורמים למשפט לאבד את משמעותו מבחינה תחבירית.
למשל לפועל "נתן" דרושים שלושה משלימים: מי נתן, מה ניתן, ולמי נתנו את הניתן. בלעדי משלימים אלו המשפט יהיה משפט "חסר" ולא תקני באוזני המאזין או בעיני הקורא. והנה דוגמה אחרת. לפעולת הטביעה יש רק משלים אחד: מי או מה טבע, ואין מושא לפעולה (בדקדוק המסורתי, פועַל מסוג זה נקרא "פועל עומד"). "מישהו טבע" הוא משפט מקובל, אבל "מישהו טבע מישהו" אינו תקני.
לדעת חומסקי, הסיבה שמשפט יאבד את משמעותו באופן זה כשהפעולה אינה עם כל השלמותיה, או כשהפעולה הובעה עם משלימים מיותרים, קשור בלכידות הצירופים התחביריים שבמשפט סביב הפעולה. המבנה התחבירי המסודר והמתוכנן במוחם של הדוברים לפני הפקתו נקרא בפי הבלשנים מבנה הבסיס, או מבנה העומק המופשט. בסופו של דבר לא תמיד ההפקה הנאמרת "בזמן אמת" יוצאת כפי שתוכננה.
אבל מניתוח מבנה הצירופים התחביריים של הפקות המבע במציאות, כלומר מניתוח "מבנה השטח" וזיהוי תפקידי הרכיבים המשלימים סביב הפעולה, ניתן לזהות מה היו הכללים התחביריים וסדר הצירופים לפיהם תוכנן המבע, כלומר ניתן לזהות את "מבנה הבסיס". לאור ניתוח זה ניתן לזהות את תפקידי הרקע (התפקיד התימטי) של אותם משלימים ההכרחיים להשלמת הבעת הפעולה, תפקידים משמעיים שמחברים את הפעולה עצמה למבנה אחיד לכיד ומובן עם המשלימים שלה.
תפקידים תימטיים אלו הם:
עיקרון ההיטל התימטי והתבחינים לקיומו.
עיקרון ההיטל התימטי - עיקרון תפקיד תימטי לכל צירוף לשוני קובע:
ובלשון המקצועית:
הפרת עיקרון זה תגרום לכך שלא ייווצר "תסריט" הגיוני לכיד של הפעולה, והמשפט יהיה חסר משמעות.
הערה: העיקרון נקרא כך על שם ההיטל (הפרוייקציה), כי במינוח שבאנגלית כל חלק דיבר (שם עצם, פועל, תואר השם, תואר הפועל ומילת יחס) "מטיל" על המשפט את הצירוף הלשוני שלו.
הקריטריון התימטי: המדד לבחינת עמידתו של מבע שיחה בעיקרון ההיטל, בנוי על שתי דרישות וקריטריונים:
בלעדי המשלימים המשמעותיים הללו המשפט הופך ללא קוהרנטי.
המשלים המתאר את הזמן אינו דרוש להשלמת פעולת הנתינה, ולכן אינו משפיע על הבנת המשפט.
דוגמאות לדרישת משלימי פעולה.
כאמור, לפי תפישה זו, משפטים בהם הוחסרו משלימים או הוסיפו משלימים שאין להם פירוש רקע-תימטי הם משפטים חסרי לכידות תחבירית, ולכן לא קוהרנטיים.
איש חדש
פורט או פרנס
קארל פומרנץ
קארל פומרנץ (באנגלית: Carl Pomerance; נולד ב-1944) הוא מתמטיקאי אמריקאי מתחום תורת המספרים.
את תואר הדוקטור קיבל פומרנץ ב-1972 מאוניברסיטת הרווארד, על עבודה בה הראה שכל מספר משוכלל אי-זוגי מתחלק לפחות בשבעה מספרים ראשוניים שונים. אחר כך עבר ללמד באוניברסיטת ג'ורג'יה. הוא אף עבד מספר שנים בחברת לוסנט טכנולוגיות. ומשם עבר לקולג' דרטמות שם קיבל גם תואר פרופסור כבוד.
פומרנץ זכה בפרסים רבים על מחקר. הוא פיתח את הנפה הריבועית, אלגוריתם לפירוק לגורמים שעל פיו בשנת 1994 הצליחו לפרוץ RSA עם 129 ביטים. הוא אף השתתף בפיתוח האלגוריתם APR לבדיקת ראשוניות (APR - ראשי תיבות של שמות המפתחים לאונרד אדלמן, קארל פומרנץ ורוברט רומלי).
נפה ריבועית
שיטת הנפה הריבועית היא שיטה מהירה לפירוק לגורמים של מספר שלם, המתאימה בעיקר למספרים בני 40–100 ספרות עשרוניות (שיטת רו של פולארד עדיפה לפירוק מספרים קטנים יותר, בעוד שבמספרים ארוכים יותר נפת שדה המספרים היא השיטה היעילה ביותר).
שיטת הנפה הריבועית, שהייתה השיטה הראשונה בעלת סיבוכיות תת-אקספוננציאלית לבעיית הפירוק לגורמים, פותחה על ידי קארל פומרנץ בשנת 1981. פומרנץ הרחיב, למעשה, רעיונות קודמים של קרייטצניק (Kraitchnik) וג'ון ד' דיקסון. זו הייתה השיטה המהירה ביותר (באופן אסימפטוטי), עד להמצאתה של נפת שדה המספרים, ב-1993.
עקרונות הנפה הריבועית.
בדומה לשיטות פירוק אחרות של מספרים שלמים הנקראות "ריבוע אקראי" (Random square), גם שיטת הנפה הריבועית מנסה לאתר זוג שלמים אקראיים, formula_1 ו-formula_2, כך ש- formula_3 אבל formula_4 (מודולו formula_5). זוג כזה מאפשר לפרק את formula_5, משום ש- formula_7 אולם אינו מחלק של formula_8 או formula_9. על כן בסבירות גבוהה המחלק המשותף המקסימלי formula_10 (שאותו אפשר למצוא ביעילות באמצעות אלגוריתם אוקלידס) יהיה גורם אמיתי של formula_5.
בקווים כלליים, הנפה הריבועית מבוססת על ייצור מספרים שיש להם הצגה ידועה כמספר ריבועי מחד, והצגת מספרים השקולים למכפלות של מספרים כאלה מודולו n כריבועים בעזרת פירוק חלקי לגורמים, מאידך.
נגדיר formula_12, ונחשב את formula_13
(בסעיפים הבאים יוסבר כיצד למצוא xi מתאימים).
מתוך קבוצת ה-(Q(x אנחנו מחפשים תת-קבוצה של מספרים, שמכפלתם היא ריבוע ידוע: formula_14. ברגע שמטרה זו הושגה, מתקיים formula_15, ולכן גם formula_16; כך מצאנו x ו-y מתאימים לדרישות. אם המספר n הוא מכפלה של שני מספרים ראשוניים גדולים, אז מתקיים בהסתברות ½ formula_17, ואז תוצאת ה-GCD תהיה n או 1; במקרה כזה יש להמשיך את תהליך הייצור, ולמצוא זוג אחר של מספרים כמתואר לעיל.
תיאור האלגוריתם.
קלט: מספר פריק formula_5
פלט: אחד הגורמים הראשוניים של formula_5
הגדרת בסיס הגורמים וטווח הניפוי.
שיטת הנפה דורשת דרך יעילה למצוא xi כך שהמכפלה formula_77
תתן מספר ריבועי. כדי שזה יתקיים צריך שכל גורם ראשוני המחלק את המכפלה יחלק אותה מספר זוגי של פעמים. לשם כך צריך לפרק לגורמים ראשוניים כל אחד מן המספרים formula_78 המרכיבים את המכפלה.
כדי לפשט את הבדיקה אנחנו מעוניינים ש-
formula_78
יהיו קטנים ככל האפשר, ויתחלקו בראשוניים מתוך קבוצת ראשוניים ידועה לנו – לקבוצה זו נקרא "בסיס הגורמים" ונסמן אותה ב-B. גודלה של הקבוצה B משפיע על ביצועי האלגוריתם, ולכל ווריאנט של הניפוי הריבועי יש לחשב את ה-B האופטימלי לפי גודלו של n.
לצורך הצגת האלגוריתם, נסמן formula_80, המספרים הראשוניים הקטנים, לפי סדרם. כדי ש-(Q(x יהיה קטן אנחנו צריכים לבחור x קטן, ואז formula_81. נבחר איפה את טווח הניפוי [M,1].
שיפורים אפשריים.
א. אם נוסיף לבסיס הגורמים גם את 1-, אז מספרים הקרובים ל-n מלמטה גם הם מספרים קטנים יחסית, וניתן לבחור x שלילי ועדיין לקבל מספרים שקל יחסית לעבוד איתם. כך הכפלנו את טווח הניפוי ל- [M,M-].
ב. את בסיס הגורמים אפשר להקטין על ידי "בדיקת היתכנות": אם formula_82, אז
formula_83, ולכן צריך להכניס לבסיס הגורמים רק מספרים ראשוניים המקיימים, עבור x מתוך טווח הניפוי, את התנאי
formula_84.
זוהי בדיקה שאפשר להשלים בסיבוכיות נמוכה, לפי משפט ההיפוך הריבועי של גאוס, שמאפשר לחשב את סימן לז'נדר בזמן לוגריתמי (בדומה לחישוב המחלק המשותף המקסימלי באלגוריתם אוקלידס).
הניפוי - Sieving.
הגדרה: המספר X הוא חלק מעל הקבוצה B, אם כל הגורמים הראשוניים של X נמצאים ב- B
בשלב הניפוי אנחנו מחפשים formula_85 שיכולים להיות חלק מקבוצה המרכיבה מכפלה שהיא מספר ריבועי.
לשם כך אנחנו צריכים לעבור על x מתוך טווח הניפוי, לחשב את formula_85 ולבדוק האם formula_85 חלק מעל B.
עבור כל אחד מהמספרים שמתקבלים, אנו צריכים לבדוק אם הוא חלק על ידי מעבר וחלוקה בבסיס הגורמים.
פעולה סדרתית כזו אינה מעשית מבחינת זמן ביצוע. לכן נעבוד על בסיס הגורמים במקביל.
לכל p בבסיס הגורמים אם formula_88 אז גם formula_89.
ובכיוון ההפוך, אם formula_90 אז גם formula_91.
לכל p נפתור:
formula_92
את המשוואה הזאת ניתן לפתור על ידי האלגוריתם של Shanks-Tonelli.
פתרון המשוואה הריבועית יתן לנו שני שורשים, נסמן אותם ב-
formula_93 ו-formula_94.
מכאן אנו רואים ש-formula_95 עבור formula_96 מתוך טווח החיפוש מתחלק ב-p כאשר
formula_97 עבור k שלם.
כעת בתהליך שמזכיר מאוד את מכונת השרשראות של להמר, אנחנו מתקדמים ולכל x אנחנו בודקים באלו ראשוניים מבסיס הגורמים formula_85 מתחלק.
כדי לבצע את החיפוש הזה על כל טווח הניפוי כדאי לחלק את העבודה למספר מחשבים במקביל – וכל מחשב יקבל חלק מטווח הניפוי.
אנחנו בודקים האם formula_85 הוא חלק, אם לא – זורקים אותו ועוברים ל-x הבא, ואם כן שומרים אותו בתוך מטריצה שתוגדר בהמשך.
שיפורים אפשריים.