የኮምፒተር ሳይንስ ክፍል የሂሳብ መሠረቶችን ለማጥናት ዘዴ። የኮምፒተር ሳይንስ የሂሳብ መሠረቶች - የተመረጠ ኮርስ - የመማሪያ መጽሐፍ - አንድሬቫ ኢ.ቪ.

ቅድመ እይታ፡

የተገመገመ ስምምነት አጽድቋል

በ MC ስብሰባ ላይ የ MBOU "ጂምናዚየም ቁጥር 3" የምርምር እና ልማት ዳይሬክተር ምክትል ዳይሬክተር

ከርን ኤ.ቢ. ____ G.V. Mazina

2010

MBOU "ጂምናሲያ ቁጥር 3"

በኮምፒውተር ሳይንስ ውስጥ የተመረጠ ኮርስ ፕሮግራም

« የሂሳብ መሰረታዊ ነገሮችየኮምፒውተር ሳይንስ"

ለ11ኛ ክፍል

ለ 2010 - 2011 የትምህርት ዓመት

(34 HOURS)

MBOU "ጂምናዚየም ቁጥር 3"

Kiselman Nadezhda Yurievna

G. Oktyabrsky, 2010

ገላጭ ማስታወሻ

ይህ የመራጭ ኮርስ የተዘጋጀው ለ11ኛ ክፍል ተማሪዎች የተዘጋጀው በሩሲያ የትምህርት ሚኒስቴር መረጃ ደብዳቤ ህዳር 13 ቀን 2003 ነው። ቁጥር 14-51-277 / 13 በከፍተኛ ደረጃ አጠቃላይ ትምህርት በልዩ ትምህርት ስርዓት ውስጥ በተመረጡ ኮርሶች ላይ.

ኮርሱ ለ 34 ሰአታት, በሳምንት 1 ሰአት ለአንድ የክፍል ተማሪዎች ቡድን ይቆያል.

የኮምፒውተር ሳይንስ በ ይህ ክፍልአልተጠናም።

የተመረጠ ኮርስላይ የተመሰረተ የተመረጠ ኮርስ, የአማራጭ ኮርስ ደራሲዎች "የኮምፒዩተር ሳይንስ የሂሳብ መሠረቶች" የፊዚካል እና የሂሳብ ሳይንስ እጩዎች E.V. አንድሬቫ, የፔዳጎጂካል ሳይንስ እጩ ኤል.ኤል. ቦሶቫ እና የፔዳጎጂካል ሳይንሶች እጩ K.N. ፋሊና ቁሱ በሂሳብ እና በኮምፒተር ሳይንስ መካከል ያለውን ግንኙነት ያሳያል, ከእነዚህ ውስጥ የአንዱን እድገት እንዴት ያሳያል ሳይንሳዊ መስኮችየሌላውን እድገት አነሳሳ. በኮምፒዩተር ሳይንስ ውስጥ ጥቅም ላይ የሚውሉትን የሂሳብ አፓርተማዎች ጠለቅ ያለ ግንዛቤ የተሰጠ ሲሆን በሂሳብ የተገኙ ውጤቶች እንዴት ለአዳዲስ ሀሳቦች ምንጭ ሆነው ሲያገለግሉ እና በአልጎሪዝም ፣ ፕሮግራሚንግ እና ሌሎች የኮምፒዩተር ሳይንስ ፅንሰ-ሀሳቦች ላይ ውጤቱን አሳይቷል።

የዘመናዊነት ዋና ተግባር የሩሲያ ትምህርትመገኘቱን, ጥራቱን እና ብቃቱን ማሳደግ ነው. ይህ የሚያመለክተው ጉልህ የሆነ የትምህርት ይዘት ማሻሻያ ነው, እሱም በተራው, በኮምፒውተር ሳይንስ እና በኢንፎርሜሽን ቴክኖሎጂ ውስጥ አዲስ የትምህርት ደረጃ ብቅ እንዲል አድርጓል.

የትምህርቱ ዓላማ የሚለውን ሚና ግምት ውስጥ ማስገባት ነው። መሠረታዊ እውቀት(ማለትም የሂሳብ ሊቃውንት) በኮምፒተር ሳይንስ ፣ በኢንፎርሜሽን እና በመገናኛ ቴክኖሎጂዎች ልማት ውስጥ።

የዚህ የምርጫ ኮርስ አንዱ ጠቃሚ ጠቀሜታ ከፒሲ ነፃ መሆኑ ነው፣ በዚህ ምክንያት የኮርሱ ትምህርቱ ፒሲ በማይኖርበት ጊዜ ወይም የኮምፒዩተር ክፍል በቂ የሰው ኃይል በማይኖርበት ጊዜ በተሳካ ሁኔታ ማስተማር ይችላል።

የኮርሱ ዓላማዎች፡-

የተማሪዎችን ግንዛቤ ማስፋት ፣
ተግባራዊ የትግበራ ክህሎቶችን በመለማመድ የንድፈ ሐሳብ ቁሳቁስችግሮችን ለመፍታት.

የኮርሱ መርሃ ግብር አግድ-ሞዱላር መዋቅር ያለው ሲሆን የሚከተሉትን ክፍሎች ያካትታል፡ የቁጥር ሥርዓቶች፣ የመረጃ ውክልና በኮምፒውተር እና አልጀብራ ኦፍ ሎጂክ።

ውስጥ የተሸፈኑ ጉዳዮች ይህ ኮርስመሰረታዊ የኮምፒዩተር ሳይንስ ትምህርትን አይረዱም ወይም ከፊል ጋር በተገናኘ ብቻ የተሸፈኑ ናቸው በቂ ያልሆነ ደረጃየመጀመሪያ ደረጃ ተማሪዎች የሂሳብ ስልጠና.

በተጨማሪ አጠቃላይ መረጃስለ ቁጥር ሥርዓቶች፣ እንደ መሠረት፣ ፊደላት፣ የቁጥር ሥርዓት መሠረት፣ የአቀማመጥ እና የአቀማመጥ ሥርዓት ጽንሰ-ሐሳብ፣ የቁጥር ሥርዓቶች ታሪክ፣ ባህላዊ ያልሆኑ የቁጥር ሥርዓቶች (ፋብሪካዊ፣ ፊቦናቺ)፣ የትርጉም ጉዳዮች ቁጥሮች (ኢንቲጀር ፣ ውሱን እና ማለቂያ የሌላቸው ክፍልፋዮች) ከ የአስርዮሽ ስርዓትለማንኛውም የአቀማመጥ ቁጥር እና በተገላቢጦሽ ላይ ምልክት, እንዲሁም ለእንደዚህ አይነት ትርጉም ህጋዊነት የሂሳብ ማረጋገጫ. በተጨማሪም, ሁሉም ነገር ይጠናል የሂሳብ ስራዎችቪ የተለያዩ ስርዓቶችካልኩለስ, ሥራ የሚከናወነው በሙሉ ቁጥሮች ብቻ ሳይሆን በክፍልፋዮችም ጭምር ነው. ንድፈ ሐሳብን በመተግበር ላይ ተግባራዊ ክህሎቶችን መለማመድ የሚከናወነው ችግሮችን በቁጥር ኮድ በመፍታት ነው.

ትምህርቱን ለማጥናት መሰረታዊ ቅጾች እና ዘዴዎች-

የትምህርቱን መጠነ-ሰፊ አቀራረብ የሚያቀርብ የትምህርት ቤት ንግግር;
የሴሚናር ክፍሎች, በዚህ ጊዜ ቁሳቁስ የተገነዘበ, የተስፋፋ እና ዝርዝር;
ችግር ፈቺ አውደ ጥናቶች.

የትምህርት ቁጥር	ርዕሰ ጉዳይ	የትምህርት ቀን	ማስታወሻዎች
	ምዕራፍ 1. የቁጥር ስርዓቶች
	የአቀማመጥ ቁጥር ስርዓቶች. መሰረታዊ ትርጓሜዎች. በ P-ary ቁጥር ስርዓቶች ውስጥ የቁጥሮች ውክልና ልዩነት.
	አፈጻጸም የዘፈቀደ ቁጥሮችበአቀማመጥ ቁጥር ስርዓቶች. የተስፋፉ እና የተሰበሩ የመግቢያ ቅጾች።
	በአቀማመጥ ቁጥር ስርዓቶች ውስጥ የዘፈቀደ ቁጥሮች ውክልና. ማስተላለፍ የተፈጥሮ ቁጥሮች.
	በአቀማመጥ ቁጥር ስርዓቶች ውስጥ የዘፈቀደ ቁጥሮች ውክልና. ተራ አቀራረብ አስርዮሽበ P-ary ቁጥር ስርዓቶች.
	የሂሳብ ስራዎችበ P-ary ቁጥር ስርዓቶች. መደመር እና መቀነስ።
	በ P-ary ቁጥር ስርዓቶች ውስጥ የሂሳብ ስራዎች. ማባዛትና መከፋፈል.
	ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ። የኢንቲጀር P-ary ቁጥሮች ትርጉም።
	ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ። የተጠናቀቁ P-ary ክፍልፋዮች ትርጉም።
	ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ። ወቅታዊ የP-ary ክፍልፋዮች ትርጉም።
	ቁጥሮችን ከአስርዮሽ ቁጥር ስርዓት ወደ P-ary ቁጥር ስርዓት መለወጥ። ኢንቲጀርን ለመቀየር ሁለት መንገዶች።
	ቁጥሮችን ከአስርዮሽ ቁጥር ስርዓት ወደ P-ary ቁጥር ስርዓት መለወጥ። የመጨረሻ የአስርዮሽ ክፍልፋዮችን በመቀየር ላይ።
	የተቀላቀለ ቁጥር ስርዓቶች.
	የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር። የተመጣጠነ የሶስትዮሽ ቁጥር ስርዓትን በመጠቀም።
	የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር። የ Fibonacci ቁጥር ስርዓትን በመጠቀም.
	የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር። ሁለትዮሽ ያልሆነ የኮምፒውተር ስሌት።
	ምዕራፍ 2. የሎጂክ አልጀብራ.
	የሎጂክ አልጀብራ። የንግግር ጽንሰ-ሐሳብ.
	ምክንያታዊ ክንውኖች. የእውነት ጠረጴዛዎች.
	ምክንያታዊ ቀመሮች. የአልጀብራ ሎጂክ ህጎች።
	የመፍትሄ ዘዴዎች ምክንያታዊ ችግሮች.
	የወረዳ መቀያየርን አልጀብራ።
	ቡሊያን ተግባራት.
	የሎጂካዊ ቀመሮች ቀኖናዊ ቅርጾች። ንድፈ ሐሳብ ስለ SDNF.
	ምዕራፍ 3. በኮምፒተር ላይ መረጃን ማቅረቡ.



	የእውነተኛ ቁጥሮች ውክልና. መደበኛ የቁጥር ምልክት።
	በተንሳፋፊ ነጥብ ቅርጸት የእውነተኛ ቁጥሮች ውክልና


	የጽሑፍ እና የግራፊክ መረጃ አቀራረብ. አጠቃላይ አቀራረቦች. የግራፊክ መረጃ ቬክተር እና ራስተር ውክልና።
	የግራፊክ መረጃ አቀራረብ. የቀለም ሞዴሎች RGB, CMYK, HSB.
	የድምጽ መረጃ አቀራረብ. የድምፅ ቀረጻ። የ pulse code modulation.
	የድምጽ መረጃ አቀራረብ. MIDI ቅርጸት የኮምፒተር ድምጽ ማባዛት መርሆዎች.
	የመጨመቂያ ዘዴዎች ዲጂታል መረጃ.

1. የቁጥር ስርዓቶች (15 ሰዓቶች).

§1. የአቀማመጥ ቁጥር ስርዓቶች.

መሰረታዊ ትርጓሜዎች.

§2. በ P-ary ቁጥር ስርዓቶች ውስጥ የቁጥሮች ውክልና ልዩነት.

§3. በአቀማመጥ ቁጥር ስርዓቶች ውስጥ የዘፈቀደ ቁጥሮች ውክልና.

የተስፋፉ እና የተሰበሩ የመግቢያ ቅጾች።

የተፈጥሮ ቁጥሮች መቁጠር.

በP-ary ቁጥር ስርዓቶች ውስጥ ተራ የአስርዮሽ ክፍልፋዮችን መወከል።

§4. በ P-ary ቁጥር ስርዓቶች ውስጥ የሂሳብ ስራዎች.

መደመር። መቀነስ። የማባዛት ክፍፍል.

§5. ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ።

የኢንቲጀር P-ary ቁጥሮች ትርጉም።

የተጠናቀቁ P-ary ክፍልፋዮች ትርጉም።

ወቅታዊ የP-ary ክፍልፋዮች ትርጉም።

§6. ቁጥሮችን ከአስርዮሽ ቁጥር ስርዓት ወደ P-ary ቁጥር ስርዓት መለወጥ።

ኢንቲጀርን ለመቀየር ሁለት መንገዶች።

የመጨረሻ የአስርዮሽ ክፍልፋዮችን በመቀየር ላይ።

§7. የተቀላቀለ ቁጥር ስርዓቶች.

§8. የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር።

የተመጣጠነ የሶስትዮሽ ቁጥር ስርዓትን በመጠቀም።

የ Fibonacci ቁጥር ስርዓትን በመጠቀም.

ሁለትዮሽ ያልሆነ የኮምፒውተር ስሌት።

2. የሎጂክ አልጀብራ. (7 ሰዓት)።

§1. የሎጂክ አልጀብራ። የንግግር ጽንሰ-ሐሳብ.

§2. ምክንያታዊ ክንውኖች. የእውነት ጠረጴዛዎች.

§3. ምክንያታዊ ቀመሮች. የአልጀብራ ሎጂክ ህጎች።

§4. ሎጂካዊ ችግሮችን ለመፍታት ዘዴዎች.

§5. የወረዳ መቀያየርን አልጀብራ።

§6. ቡሊያን ተግባራት.

§7. የሎጂካዊ ቀመሮች ቀኖናዊ ቅርጾች። ንድፈ ሃሳብ ስለ SDNF.

3. በኮምፒተር ላይ መረጃን ማቅረብ.(12 ሰዓታት).

§1. ኢንቲጀሮች ውክልና.

የአዎንታዊ ኢንቲጀሮች ውክልና እና አሉታዊ ቁጥሮች.

በኢንቲጀር ኮምፒውተር ስሌት ውስጥ የቁጥሮች መቁጠር።

በ ውስጥ የሂሳብ ስራዎች አተገባበር ባህሪያት የመጨረሻ ቁጥርፈሳሾች.

§2. የእውነተኛ ቁጥሮች ውክልና.

መደበኛ የቁጥር ምልክት።

በተንሳፋፊ ነጥብ ቅርጸት የእውነተኛ ቁጥሮች ውክልና.

በእውነተኛ ቁጥሮች ላይ የሂሳብ ስራዎችን ያከናውኑ.

የእውነተኛ ኮምፒዩተር አርቲሜቲክ ትግበራ ባህሪዎች።

§3. የጽሑፍ እና የግራፊክ መረጃ አቀራረብ.

አጠቃላይ አቀራረቦች.

የግራፊክ መረጃ ቬክተር እና ራስተር ውክልና።

የቀለም ሞዴሎች RGB, CMYK, HSB.

§4. የድምጽ መረጃ አቀራረብ.

የድምፅ ቀረጻ።

የ pulse code modulation.

MIDI ቅርጸት

የኮምፒተር ድምጽ ማባዛት መርሆዎች.

§5. ዲጂታል መረጃን ለመጨመቅ ዘዴዎች.

የትምህርት እና ዘዴዊ ስብስብ ስብስብ።

ትምህርታዊ ሥነ ጽሑፍ;

ኢ.ቪ.አንድሬቫ, ኤል.ኤል.ቦሶቫ, አይ.ኤን.ፋሊና. - የኮምፒተር ሳይንስ የሂሳብ መሠረቶች። የተመረጠ ኮርስ፡ አጋዥ ስልጠና. - ኤም: BINOM የእውቀት ላብራቶሪ, 2005
A.V. Mogilev, N.I. Pak, E.K. Henner. - በኮምፒተር ሳይንስ ላይ አውደ ጥናት. - ኤም.: የሕትመት ማዕከል"አካዳሚ", 2001
V. Lyskova, E. Rakitina. በኮምፒተር ሳይንስ ውስጥ ሎጂክ. - ኤም. ላቦራቶሪ መሰረታዊ እውቀት, 2006
ከ10-11ኛ ክፍል ኢንፎርማቲክስ፡የተመረጡ ኮርሶች ስብስብ። ኮም. ኤ.ኤ.ቼርኖቭ, ኤ.ኤፍ.ቼርኖቭ. - ቮልጎግራድ: መምህር, 2006.

በርዕሶች ላይ የዝግጅት አቀራረቦች:

የቁጥር ስርዓቶች
የሂሳብ ሎጂክ
በኮምፒተር ላይ መረጃ.

ስምየኮምፒተር ሳይንስ የሂሳብ መሠረቶች - የተመረጠ ኮርስ - የመማሪያ መጽሐፍ.

የመማሪያ መጽሃፉ ለከፍተኛ ክፍሎች በማስተማሪያ ቁሳቁሶች ውስጥ ከሥነ-ዘዴ እና ከአንቶሎጂ ጋር ተካትቷል.
ጽሑፉ በሂሳብ እና በኮምፒዩተር ሳይንስ መካከል ያለውን ግንኙነት የሚገልጽ ሲሆን ከእነዚህ ሳይንሳዊ መስኮች የአንዱ እድገት የሌላውን እድገት እንዴት እንዳነሳሳ ያሳያል። በኮምፒዩተር ሳይንስ ውስጥ ጥቅም ላይ የሚውሉትን የሂሳብ አፓርተማዎች ጠለቅ ያለ ግንዛቤ የተሰጠ ሲሆን በሂሳብ የተገኙ ውጤቶች እንዴት ለአዳዲስ ሀሳቦች ምንጭ ሆነው ሲያገለግሉ እና በአልጎሪዝም ፣ ፕሮግራሚንግ እና ሌሎች የኮምፒዩተር ሳይንስ ፅንሰ-ሀሳቦች ላይ ውጤቱን አሳይቷል።

ዝርዝር ሁኔታ
ከደራሲያን። 8
ምዕራፍ 1. የቁጥር ስርዓቶች. 11
§1.1. የአቀማመጥ ቁጥር ስርዓቶች. መሰረታዊ ትርጓሜዎች. 13
ጥያቄዎች እና ስራዎች. 19
§1.2. በ P-ary ቁጥር ስርዓቶች ውስጥ የቁጥሮች ውክልና ልዩነት. 20
ጥያቄዎች እና ስራዎች. 24
§1.3. በአቀማመጥ ቁጥር ስርዓቶች ውስጥ የዘፈቀደ ቁጥሮች ውክልና. 25
1.3.1. የተስፋፉ እና የተሰበሩ የመግቢያ ቅጾች። 25
1.3.2. የተፈጥሮ ቁጥሮች መቁጠር. 26
1.3.3. በP-ary ቁጥር ስርዓቶች ውስጥ ተራ የአስርዮሽ ክፍልፋዮችን መወከል። 28
ጥያቄዎች እና ስራዎች. ሰላሳ
§1.4. በ P-ary ቁጥር ስርዓቶች ውስጥ የሂሳብ ስራዎች. 31
1.4.1. መደመር። 31
1.4.2. መቀነስ። 33
1.4.3. ማባዛት። 33
1.4.4. ክፍፍል 35
ጥያቄዎች እና ስራዎች. 37
§1.5. ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ። 38
1.5.1. የኢንቲጀር P-ary ቁጥሮች ትርጉም። 38
1.5.2. የተጠናቀቁ P-ary ክፍልፋዮች ትርጉም። 40
1.5.3. ወቅታዊ የP-ary ክፍልፋዮች ትርጉም። 42
ጥያቄዎች እና ስራዎች. 44
§1.6. ቁጥሮችን ከአስርዮሽ ቁጥር ስርዓት ወደ P-ary ቁጥር ስርዓት መለወጥ። 44
1.6.1. ኢንቲጀርን ለመቀየር ሁለት መንገዶች። 44
1.6.2. የመጨረሻ የአስርዮሽ ክፍልፋዮችን በመቀየር ላይ። 47
ጥያቄዎች እና ስራዎች. 49
§ 1.7. የተቀላቀለ ቁጥር ስርዓቶች. 50
ጥያቄዎች እና ስራዎች. 54
§ 1.8. የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር። 54
1.8.1. የተመጣጠነ የሶስትዮሽ ቁጥር ስርዓትን በመጠቀም። 56
1.8.2. የ Fibonacci ቁጥር ስርዓትን በመጠቀም. 58
1.8.3. ሁለትዮሽ ያልሆነ የኮምፒውተር ስሌት። 60
ጥያቄዎች እና ስራዎች. 61
መደምደሚያ. 61
ምዕራፍ 2. በኮምፒተር ላይ መረጃን ማቅረብ. 63
§ 2.1. ኢንቲጀሮች ውክልና. 65
2.1.1. የኢንቲጀር ውክልና አዎንታዊ ቁጥሮች. 66
2.1.2. አሉታዊ ኢንቲጀሮች ውክልና. 68
2.1.3. በኢንቲጀር ኮምፒውተር ስሌት ውስጥ የቁጥሮች መቁጠር። 71
2.1.4. በተወሰኑ አሃዞች ውስጥ የሂሳብ ስራዎችን የመተግበር ባህሪያት. 73
ጥያቄዎች እና ስራዎች. 74
§2.2. የእውነተኛ ቁጥሮች ውክልና. 74
2.2.1. መደበኛ የቁጥር ምልክት። 75
2.2.2. በተንሳፋፊ ነጥብ ቅርጸት የእውነተኛ ቁጥሮች ውክልና. 80
2.2.3. በእውነተኛ ቁጥሮች ላይ የሂሳብ ስራዎችን ያከናውኑ. 81
2.2.4. የእውነተኛ ኮምፒዩተር አርቲሜቲክ ትግበራ ባህሪዎች። 84
ጥያቄዎች እና ስራዎች. 88
§ 2.3. የጽሑፍ መረጃ አቀራረብ. 89
ጥያቄዎች እና ስራዎች. 95
§ 2.4. የግራፊክ መረጃ አቀራረብ. 96
2.4.1. በኮምፒተር ላይ መረጃን ለመወከል አጠቃላይ አቀራረቦች የተፈጥሮ አመጣጥ. 97
2.4.2. የግራፊክ መረጃ ቬክተር እና ራስተር ውክልና። 102
2.4.3. የቀለም መጠን. 104
2.4.4. የ RGB ቀለም ሞዴል. 107
2.4.5. CMYK ቀለም ሞዴል. 112
2.4.6. የ HSB ቀለም ሞዴል. 115
ጥያቄዎች እና ስራዎች. 119
§ 2.5. የድምጽ መረጃ አቀራረብ. 120
2.5.1. የድምፅ ቀረጻ ጽንሰ-ሐሳብ. 122
2.5.2. የ pulse code modulation. 123
2.5.3. MIDI ቅርጸት 127
2.5.4. የኮምፒተር ድምጽ ማባዛት መርሆዎች. 128
ጥያቄዎች እና ስራዎች. 129
§ 2.6. የዲጂታል መረጃን ለመጨመቅ ዘዴዎች. 130
2.6.1. ሊለወጡ የሚችሉ ዘዴዎች አልጎሪዝም. 132
2.6.2. ከቁጥጥር የመረጃ መጥፋት ጋር የመጨመቂያ ዘዴዎች። 141
ጥያቄዎች እና ስራዎች. 145
መደምደሚያ. 145
ምዕራፍ 3. የሎጂክ አልጀብራ መግቢያ. 147
§ 3.1. የሎጂክ አልጀብራ። የመናገር ጽንሰ-ሐሳብ. 148
ጥያቄዎች እና ስራዎች. 151
§ 3.2. ምክንያታዊ ክንውኖች. የእውነት ጠረጴዛዎች. 152
ጥያቄዎች እና ስራዎች. 162
§ 3.3. ምክንያታዊ ቀመሮች. የአልጀብራ ሎጂክ ህጎች። 164
ጥያቄዎች እና ስራዎች. 167
§ 3.4. ሎጂካዊ ችግሮችን ለመፍታት ዘዴዎች. 168
ጥያቄዎች እና ስራዎች. 172
§ 3.5. የወረዳ መቀያየርን አልጀብራ። 173
ጥያቄዎች እና ስራዎች. 175
§ 3.6. ቡሊያን ተግባራት. 176
ጥያቄዎች እና ስራዎች. 178
§ 3.7. የሎጂክ ቀመሮች ቀኖናዊ ቅርጾች። ንድፈ ሐሳብ ስለ SDNF. 178
ጥያቄዎች እና ስራዎች. 184
§ 3.8. ማሳነስ ቡሊያን ተግባራትበተለዋዋጭ መደበኛ ቅርጾች ክፍል ውስጥ. 185
ተግባራዊ ተግባራት. 189
§ 3.9. የተሟሉ ስርዓቶችቡሊያን ተግባራት. 190
ጥያቄዎች እና ስራዎች. 192
§ 3.10. የወረዳ ንድፍ ክፍሎች. አመክንዮ. 193
ጥያቄዎች እና ስራዎች. 197
መደምደሚያ. 197
ምዕራፍ 4. የአልጎሪዝም ንድፈ ሐሳብ አካላት. 199
§ 4.1. የአልጎሪዝም ጽንሰ-ሐሳብ. የአልጎሪዝም ባህሪያት. 200
ጥያቄዎች እና ስራዎች. 208
§ 4.2. የአልጎሪዝም ጽንሰ-ሐሳብ ማብራሪያ. የቱሪንግ ማሽን. 209
4.2.1. የአልጎሪዝም ጽንሰ-ሐሳብን የማብራራት አስፈላጊነት. 209
4.2.2. የቱሪንግ ማሽን መግለጫ። 212
4.2.3. የቱሪንግ ማሽኖች ምሳሌዎች። 215
4.2.4. የአልጎሪዝም መደበኛ መግለጫ። የሂሳብ መግለጫየቱሪንግ ማሽኖች. 218
ጥያቄዎች እና ስራዎች. 220
§4.3. የፖስታ ማሽን እንደ የአልጎሪዝም ጽንሰ-ሀሳብ ማብራሪያ። 220
ጥያቄዎች እና ስራዎች. 223
§4.4. በአልጎሪዝም ሊፈቱ የማይችሉ ችግሮች እና ሊሰሉ የሚችሉ ተግባራት. 224
ጥያቄዎች እና ስራዎች. 229
§4.5. የአልጎሪዝም ውስብስብነት ጽንሰ-ሐሳብ. 230
ጥያቄዎች እና ስራዎች. 234
§ 4.6. የፍለጋ ስልተ ቀመሮች ትንተና. 234
4.6.1. ቅደም ተከተል ፍለጋ ባልታዘዘ ድርድር። 235
4.6.2. የሁለትዮሽ ፍለጋ አልጎሪዝም በታዘዘ ድርድር። 237
ጥያቄዎች እና ስራዎች. 238
§ 4.7. የመደርደር ስልተ ቀመር ትንተና. 238
4.7.1. የ "አረፋ" ዘዴን በመጠቀም መለዋወጥ. 239
4.7.2. በምርጫ መደርደር። 241
4.7.3. የማስገቢያ ዓይነት 243
4.7.4. መደርደር አዋህድ። 244
ጥያቄዎች እና ስራዎች. 247
መደምደሚያ. 248
ምዕራፍ 5. የመረጃ ንድፈ ሐሳብ መሰረታዊ ነገሮች. 249
§ 5.1. የመረጃ ጽንሰ-ሐሳብ. የመረጃ መጠን። የመረጃ መለኪያ አሃዶች. 250
ጥያቄዎች እና ስራዎች. 254
§ 5.2. የመረጃውን መጠን ለመወሰን የሃርትሊ ቀመር። 254
ጥያቄዎች እና ስራዎች. 260
§ 5.3. የሃርትሊ ቀመር አተገባበር። 261
ጥያቄዎች እና ስራዎች. 265
§ 5.4. የመረጃ ተጨማሪነት ህግ. ለመረጃ መለኪያ የፊደል አቀራረብ። 266
ጥያቄዎች እና ስራዎች. 269
§5.5. መረጃ እና ዕድል. የሻነን ቀመር. 269
ጥያቄዎች እና ስራዎች. 276
§ 5.6. ምርጥ የመረጃ ኮድ እና ውስብስብነቱ። 277
ጥያቄዎች እና ስራዎች. 280
መደምደሚያ. 281
ምዕራፍ 6. የሂሳብ ጂኦሜትሪ የሂሳብ መሰረቶች እና የኮምፒውተር ግራፊክስ. 283
§ 6.1. በአውሮፕላኑ ላይ መጋጠሚያዎች እና ቬክተሮች. 285
ጥያቄዎች እና ስራዎች. 292
§ 6.2. በአውሮፕላን ላይ መስመሮችን የሚገልጹ ዘዴዎች. 292
6.2.1. አጠቃላይ እኩልታቀጥታ። 292
6.2.2. የአንድ ቀጥተኛ መስመር መደበኛ እኩልታ። 294
6.2.3. ፓራሜትሪክ እኩልታዎችቀጥተኛ መስመር, ሬይ, ክፍል. 296
6.2.4. ክበብን ለመግለጽ መንገዶች። 297
ጥያቄዎች እና ስራዎች. 298
§6.3. የኮምፒተር ግራፊክስ ችግሮች የጋራ ዝግጅትነጥቦች እና አሃዞች. 298
6.3.1. በተሰጠው መስመር ቀጥ ያለ መስመር እና የሚያልፍ የተሰጠው ነጥብ. 298
6.3.2. ከመስመር፣ ጨረር ወይም ክፍል አንጻራዊ የሆነ የነጥብ ቦታ። 299
6.3.3. ቀጥተኛ መስመሮች, ክፍሎች, ጨረሮች አንጻራዊ አቀማመጥ. 301
6.3.4. የአንድ ክበብ እና ቀጥተኛ መስመር አንጻራዊ አቀማመጥ. 303
6.3.5. የሁለት ክበቦች አንጻራዊ አቀማመጥ. 305
ጥያቄዎች እና ስራዎች. 307
§ 6.4. ፖሊጎኖች 307
6.4.1. የባለብዙ ጎን ውሱንነት መፈተሽ። 308
6.4.2. ነጥቡ የአንድ ፖሊጎን ውስጠኛ ክፍል መሆኑን በማጣራት ላይ። 308
6.4.3. የአካባቢ ስሌት ቀላል ፖሊጎን. 310
ጥያቄዎች እና ስራዎች. 311
§6.5. ጂኦሜትሪክ እቃዎችበጠፈር ውስጥ. 312
6.5.1. መሰረታዊ ቀመሮች. 312
6.5.2. በጠፈር ውስጥ የቀጥታ መስመር እና የሶስት ማዕዘን መገናኛን መወሰን. 314
6.5.3. በጠፈር ውስጥ በተሰጠው መስመር ዙሪያ የአንድ ነጥብ መዞር። 315
ጥያቄዎች እና ስራዎች. 317
መደምደሚያ. 318
መተግበሪያ. 319
የርዕስ ማውጫ.

የ Fibonacci ቁጥር ስርዓትን በመጠቀም.
በኮምፒዩተር ዘመን መባቻ ላይ ፣ ቁጥሮችን በሚወክሉበት የአቀማመጥ ዘዴዎች መስክ ሁለት ተጨማሪ ግኝቶች ተደርገዋል ፣ ሆኖም ግን ብዙም ያልታወቁ እና በዚያን ጊዜ የሂሳብ ሊቃውንት እና መሐንዲሶች ብዙ ትኩረት አልሳቡም። ስለ ነው።ስለ ፊቦናቺ ቁጥር ስርዓት ባህሪያት እና ስለ ወርቃማው ተመጣጣኝ ቁጥር ስርዓት.

በ 20 ኛው ክፍለ ዘመን የመጨረሻዎቹ አስርት ዓመታት ውስጥ በዩኤስኤስአር ውስጥ በፕሮፌሰር ኤ.ፒ. ስታኮቭ መሪነት የሒሳብ ሊቃውንት ቡድን እጅግ በጣም ብዙ አገኘ ። አስደሳች ውጤቶችበ ውስጥ የመረጃ ማከማቻ ፣ ማቀነባበሪያ እና የማስተላለፍ አስተማማኝነት ችግርን ከመፍታት ጋር የተገናኘ የኮምፒተር ስርዓቶች. የሂሳብ ሊቃውንት የ Fibonacci ስርዓትን በኮምፒተር ውስጥ እንደ የቁጥር ስርዓት ለመጠቀም ሀሳብ አቅርበዋል ። የዚህ ስርዓት ፊደላት ቁጥሮች 0 እና 1 መሆናቸውን እናስታውስ እና መሰረቱ የፊቦናቺ ቁጥሮች ቅደም ተከተል ነው 1, 2, 3, 5, 8, 13, 21, 34 ....

የነፃ ቅጂ ኢ-መጽሐፍበሚመች ቅርጸት ይመልከቱ እና ያንብቡ፡-
መጽሐፉን ያውርዱ የኮምፒተር ሳይንስ የሂሳብ መሠረቶች - የተመረጠ ኮርስ - የጥናት መመሪያ - አንድሬቫ ኢ.ቪ. ቦሶቫ ኤል.ኤል. ፋሊና አይ.ኤን. - fileskachat.com ፣ ፈጣን እና ነፃ ማውረድ።

የማዘጋጃ ቤት የበጀት ትምህርት ተቋም

"የሁለተኛ ደረጃ ትምህርት ቤት ቁጥር 30"

PDOU ፕሮግራም

በኮምፒዩተር ሳይንስ እና አይሲቲ

"የኮምፒውተር ሳይንስ የሂሳብ መሠረቶች"

ቱናኤቫ ናታሊያ አናቶሊዬቭና።

ለ9ኛ ክፍል

ለ 2016-2017 የትምህርት ዘመን

ሚካሂሎቭስክ, 2016

ገላጭ ማስታወሻ

ኮርሱ "የኢንፎርማቲክስ የሂሳብ መሠረቶች" የተዘጋጀው በ E.V. Andreev, L.L. Bosov, I. N. Falin - M.: BINOM የማስተማሪያ ቁሳቁሶች መሰረት ነው. የእውቀት ላቦራቶሪ, 2007. "የኮምፒዩተር ሳይንስ የሂሳብ መሠረቶች" እና የተቀናጀ, ሁለገብ ተፈጥሮ ነው, የኮርሱ ቁሳቁስ በሂሳብ እና በኮምፒዩተር ሳይንስ መካከል ያለውን ግንኙነት ያሳያል, ከእነዚህ ሳይንሳዊ መስኮች የአንዱ እድገት የሌላውን እድገት እንዴት እንዳነሳሳ ያሳያል.

ትምህርቱ ለ9ኛ ክፍል ተማሪዎች ያለመ ነው። ሁለተኛ ደረጃ ትምህርት ቤትበኮምፒዩተር ሳይንስ እና በኮምፒተር ሳይንስ በሂሳብ የሂሳብ ግንዛቤን ለማስፋት የሚፈልጉ።

ትምህርቱ የተዘጋጀው በኮምፒውተር ሳይንስ መሠረታዊ ሥልጠና ላላቸው ተማሪዎች ነው፤ ሁለቱንም በኮምፒዩተር ድጋፍ እና ከማሽን ነጻ በሆነ ስሪት ማጥናት ይቻላል.

የኮርሱ ዓላማዎች፡-

በትምህርት ቤት ተመራቂዎች መካከል የሳይንሳዊ የዓለም እይታ መሠረቶች መመስረት;

በአጠቃላይ እና መካከል ያለውን ቀጣይነት ማረጋገጥ የሙያ ትምህርትተጨማሪ ምክንያት ውጤታማ ዝግጅትየትምህርት ቤት ተመራቂዎች የከፍተኛ ሙያዊ ትምህርት ፕሮግራሞችን ለመቆጣጠር;

ለራስ-ልማት እና ለግለሰብ ራስን ማስተማር ሁኔታዎችን መፍጠር.

የኮርሱ ዓላማዎች፡-

በተማሪዎች መካከል ስልታዊ ግንዛቤ ለመፍጠር የንድፈ ሐሳብ መሠረትየመረጃ እና የመገናኛ ቴክኖሎጂዎች;

የሂሳብ እና የኮምፒዩተር ሳይንስ ግንኙነት እና የጋራ ተጽእኖ ማሳየት;

ተማሪዎችን በአብዛኛዎቹ ዓይነቶች የሚፈለጉትን ችሎታዎች ያስታጥቁ ዘመናዊ እንቅስቃሴዎች(ከሌሎች የቡድን አባላት ጋር መገናኘት፣ ማቀድ እና ማደራጀት) የጋራ እንቅስቃሴዎችወዘተ.)

የምርምር ችግሮችን የመፍታት ክህሎቶችን ማዳበር;

የውሳኔ ክህሎቶችን ማዳበር ተግባራዊ ችግሮች, የተጠናቀቀውን ምርት ማምረት የሚያስፈልገው;

ራስን የመማር ችሎታ ማዳበር.

ኮርሱ ተሰጥቷል በሳምንት 3 ሰዓታት ፣ በአጠቃላይ 96 የማስተማር ሰዓታት።

ኮርሱ "የኮምፒዩተር ሳይንስ የሂሳብ መሠረቶች" ብሎክ-ሞዱላር መዋቅር አለው ፣ የመማሪያ መጽሀፉ 6 ምዕራፎችን ያቀፈ ነው ፣ በማንኛውም ቅደም ተከተል ሊጠና ይችላል።

ቲማቲክ እና ትምህርት ማቀድ

ርዕስ ቁጥር	ርዕስ ስም	የሰዓታት ብዛት
	የቁጥር ስርዓቶች
	በኮምፒተር ላይ መረጃን ማቅረብ
	የሎጂክ አልጀብራ መግቢያ
	የአልጎሪዝም ፅንሰ-ሀሳብ አካላት
	የመረጃ ንድፈ ሐሳብ መሰረታዊ ነገሮች
	የስሌት ጂኦሜትሪ እና የኮምፒተር ግራፊክስ የሂሳብ መሰረቶች
	ጠቅላላ

ሞጁል 1. የቁጥር ስርዓቶች

“የቁጥር ሥርዓቶች” የሚለው ርዕስ ብዙውን ጊዜ በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ውስጥ ይማራል ፣ ስለሆነም የትምህርት ቤት ልጆች የተወሰኑ እውቀቶች እና ክህሎቶች አሏቸው ፣ በተለይም በኢንቲጀር ትርጉም ውስጥ። የአስርዮሽ ቁጥሮችወደ ሁለትዮሽ ስርዓት እና ወደ ኋላ.

ርዕሱን የማጥናት ዓላማዎች-

የቁጥር ስርዓቶችን የመገንባት መርሆዎችን እና በመጀመሪያ ደረጃ የአቀማመጥ ስርዓቶችን መግለጥ;

የአቀማመጥ ቁጥር ስርዓቶችን ባህሪያት ማጥናት;

ቁጥሮችን ከአንድ የቁጥር ስርዓት ወደ ሌላ ለመለወጥ ስልተ ቀመሮች ምን ሀሳቦች እንደተመሰረቱ አሳይ ፣

በኮምፒተር ውስጥ መረጃን ለመደበቅ ጥቅም ላይ በሚውለው የቁጥር ስርዓት እና በኮምፒዩተር አርክቴክቸር መካከል ያለውን ግንኙነት መግለጽ;

የአጠቃቀም ዋና ጉዳቶችን ያስተዋውቁ ሁለትዮሽ ስርዓትበኮምፒተር ውስጥ;

በኮምፒተር ሲስተሞች ውስጥ ጥቅም ላይ ስለሚውሉ ሁለትዮሽ ካልሆነ በስተቀር ስለ የቁጥር ስርዓቶች ይናገሩ።

ይህ ሞጁል 145 ተግባራትን ይዟል - 103 በጥናት መመሪያ ውስጥ እና 42 ተግባራትን በገለልተኛ እና ፈተናዎች (የመሳሪያ ስብስብ).

ሞጁል 2. በኮምፒተር ላይ መረጃን መወከል

ልማት ዘመናዊ ዘዴዎችመረጃን ዲጂታል ማድረግ አንዱ ነው። ብሩህ ምሳሌዎችበተለያዩ መስኮች የስፔሻሊስቶች ትብብር: የሂሳብ ሊቃውንት, ባዮሎጂስቶች, የፊዚክስ ሊቃውንት, መሐንዲሶች, የአይቲ ስፔሻሊስቶች, ፕሮግራመሮች. የተፈጥሮ መረጃን (MP3, JPEG, MPEG, ወዘተ) ለማከማቸት ሰፊ ቅርጸቶች ውስብስብ ይጠቀማሉ የሂሳብ ዘዴዎች. ምዕራፍ 2 አያስተዋውቅም " ውስብስብ ሂሳብ", ግን ስለ መንገዶች ብቻ ይናገራል, በኮምፒተር ውስጥ መረጃን ለማቅረብ ዘመናዊ አቀራረቦች.

በዚህ ሞጁል ውስጥ የተብራሩት ጉዳዮች በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ውስጥ አይቀርቡም.

ርዕሱን የማጥናት ዓላማዎች-

ኢንቲጀር እና እውነተኛ ቁጥሮች የኮምፒውተር ውክልና ዘዴዎችን በበቂ ዝርዝር ተማሪዎች አሳይ;

የጽሑፍ, የግራፊክ እና የድምጽ መረጃን ለማቅረብ የተለመዱ ልዩነቶችን መለየት;

የመረጃ መጨናነቅን ችግር ለመፍታት ዋና ዋና የንድፈ ሃሳቦችን ያስተዋውቁ.

ቁሳቁስ ይህ ክፍል, ልክ እንደ አጠቃላይ ኮርሱ, ከመጠን በላይ ነው. በሞጁል 2, 138 ተግባራት በዝርዝር ተንትነዋል (ከመማሪያ መጽሀፍ እና የፈተና ስራዎች ምሳሌዎች እና ተግባራት ጋር).

ሞዱል 3. የሎጂክ አልጀብራ መግቢያ

ርዕሱን የማጥናት ዓላማዎች-

በኮምፒተር ሳይንስ ውስጥ ጥቅም ላይ የዋለውን የሎጂክ አልጀብራ መሰረታዊ ፅንሰ-ሀሳቦችን በጥብቅ መዘርዘር በቂ ነው ።

በተጠቀሰው ንድፈ ሐሳብ መካከል ያለውን ግንኙነት አሳይ እና ተግባራዊ ፍላጎቶችየኮምፒውተር ሳይንስ እና ሂሳብ;

በዚህ ርዕስ ላይ ቀደም ሲል የተገኘውን እውቀት በስርዓት ማደራጀት።

የመማሪያ መጽሃፉ ለ 124 ችግሮች መፍትሄዎችን በዝርዝር ይሸፍናል.

ሞጁል 4. የአልጎሪዝም ንድፈ ሐሳብ አካላት

"Algorithmization" የሚለው ርዕስ በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ውስጥ ተካትቷል, እና እንደ አንድ ደንብ, የትምህርት ቤት ልጆች እንደ "አልጎሪዝም", "አስፈፃሚ", "አስፈፃሚ አካባቢ", ወዘተ የመሳሰሉትን ጽንሰ-ሐሳቦች ያውቃሉ. ይህን ሞጁል በማጥናት ላይ ሳለ ከፍተኛ ትኩረትለክፍሎች (አንቀጾች) ተወስኗል, ይዘቱ በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ውስጥ ያልተካተተ ነው. የዚህ ርዕስ አላማ ተማሪዎችን ስልተ ቀመሮችን እንዴት እንደሚጽፉ ማስተማር አይደለም. አልጎሪዝም አስተሳሰብ በጠቅላላው የትምህርት ጊዜ ውስጥ ያድጋል። ሆኖም ፣ ይህንን ርዕስ በሚያጠኑበት ጊዜ ስልተ ቀመሮችን በማዘጋጀት እና የእነሱን ስሌት ውስብስብነት በመገምገም ብዙ ችግሮች ይፈታሉ ፣ ምክንያቱም አልጎሪዝም እራሳቸው ሳይዘጋጁ የግለሰቦችን የአልጎሪዝም ንድፈ ሀሳቦችን ማጥናት የማይቻል ነው።

ርዕሱን የማጥናት ዓላማዎች-

በሂሳብ መስክ “የአልጎሪዝም ፅንሰ-ሀሳብ” እና የኮምፒተር ቴክኖሎጂው መስክ ቅድመ ሁኔታዎች እና የእድገት ደረጃዎች ሀሳብ መፈጠር ፣

የቱሪንግ ወይም የፖስታ ማሽኖች ምሳሌዎችን በመጠቀም የአልጎሪዝም መደበኛ (የሂሳብ ጥብቅ) ፍቺን ማወቅ;

የ "ሊሰላ ተግባር", "በአልጎሪዝም ሊፈቱ የማይችሉ ችግሮች" እና "የአልጎሪዝም ውስብስብነት" ጽንሰ-ሐሳቦች ጋር መተዋወቅ.

ይህ ሞጁል 82 ተግባራትን ይዟል።

ሞጁል 5. የመረጃ ንድፈ ሐሳብ መሰረታዊ ነገሮች

ርዕሱን የማጥናት ዓላማ፡-

ተማሪዎችን ያስተዋውቁ ዘመናዊ አቀራረቦችበ ላይ የተመሰረተ መረጃን ወደ ውክልና, መለካት እና መጨናነቅ የሂሳብ ንድፈ ሐሳብመረጃ;

አሳይ ተግባራዊ አጠቃቀምየዚህ ቁሳቁስ.

ሞጁል 6. የሂሳብ መሠረቶች የሂሳብ ጂኦሜትሪ እና የኮምፒተር ግራፊክስ

ርዕሰ ጉዳዩን የማጥናት ዓላማ-ተማሪዎችን በፍጥነት በማደግ ላይ ያለውን የኮምፒዩተር ሳይንስ ቅርንጫፍ ማስተዋወቅ - የኮምፒዩቴሽን ጂኦሜትሪ; የኮምፒዩተር ግራፊክስ ስልተ ቀመሮችን የሚያጠቃልለው በትክክል ይህ መሆኑን አሳይ።

ይህ ሞጁል የጂኦሜትሪክ ችግሮችን ለመፍታት አንዳንድ ስልተ ቀመሮችን ያብራራል። በኮምፒተር ግራፊክስ ውስጥ እንደዚህ ያሉ ችግሮች ይነሳሉ ፣ የተቀናጁ ወረዳዎች ዲዛይን ፣ የቴክኒክ መሣሪያዎች ፣ ወዘተ ። በእንደዚህ ያሉ ችግሮች ውስጥ ያሉ የመጀመሪያ መረጃዎች የነጥቦች ስብስብ ፣ የክፍሎች ስብስብ ፣ ፖሊጎን ፣ ወዘተ ሊሆኑ ይችላሉ ።

የዚህ ሞጁል ርዕስ ለመረዳት በጣም አስቸጋሪ ነው. በዚህ ሞጁል ውስጥ እንደ "መረጃ", "የመረጃ መለካት" ያሉ ጽንሰ-ሐሳቦች ትርጓሜ በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ውስጥ ከሚደረገው ፈጽሞ በተለየ ደረጃ ተሰጥቷል. በተጨማሪም, ለ ሙሉ እድገትከታቀዱት ቁሳቁሶች ውስጥ በቂ የሆነ ከፍተኛ ያስፈልገዋል የሂሳብ ስልጠና; በተለይም የትምህርት ቤት ልጆችን ከሎጋሪዝም ጽንሰ-ሀሳብ ጋር ማስተዋወቅ ጥሩ ነው. ለዚህም ነው ይህ ሞጁል በኮርሱ መጀመሪያ ላይ ሳይሆን ወደ ፍጻሜው ሲቃረብ፣ በሂሳብ ኮርስ ውስጥ ያሉ ተማሪዎች ሎጋሪዝምን በደንብ በሚያውቁበት ጊዜ እንዲጠና የታቀደው።

የቁሱ ክፍል፣ ለምሳሌ የሻነን ቀመር ወይም አመጣጡ፣ ሊቀር ይችላል፣ እና የተለቀቀው ጊዜ ለበለጠ ጥቅም ላይ ሊውል ይችላል። ዝርዝር ጥናትየመረጃ ጽንሰ-ሀሳብ መሰረታዊ አካላት ፣ መኖር አስፈላጊበኮምፒውተር ሳይንስ. እንደነዚህ ዓይነቶቹ ንጥረ ነገሮች የሃርትሌይ ቀመር ፣ የመረጃ ተጨማሪነት ህግ ፣ ስለ አንድ የተወሰነ ርዕሰ ጉዳይ የእውቀት እርግጠኛ አለመሆንን በመተንተን ላይ በመመርኮዝ መረጃን ለመለካት የፊደል አቀራረቡ ግንኙነት እና የመረጃ ኮድ ኮድ።

ይህንን ሞጁል በማጥናት ምክንያት፣ ተማሪዎች በሁለቱም በሂሳብ ኮርስ እና በመሠረታዊ የኮምፒዩተር ሳይንስ ኮርስ ያልተካተቱ በርካታ አዳዲስ ፅንሰ ሀሳቦችን ማወቅ አለባቸው። ሁለተኛ ደረጃ ትምህርት ቤት. በዚህ ሞጁል ውስጥ ያለው የቁሳቁስ አቀራረብ የጂኦሜትሪክ ችግሮችን ለመፍታት እንደዚህ ያሉ አቀራረቦችን ለማሳየት በሚያስችል መንገድ የተዋቀረ ነው ፣ ይህም ለወደፊቱ ለአብዛኛዎቹ የመጀመሪያ ደረጃ ንዑስ ችግሮች በፍጥነት እና በተቻለ መጠን መፍትሄዎችን ለማግኘት ያስችላል ፣ በተለይም ፣ የኮምፒውተር ግራፊክስ.

ይህ ሞጁል 33 ተግባራትን ይዟል - 24 በመማሪያ መጽሀፍ እና 9 ተግባራዊ ስራዎች.

የመማሪያው ተዛማጅ ክፍል ቁሳቁሶች በማንኛውም የመማሪያ መጽሐፍ ውስጥ አልተካተቱም። መሰረታዊ ኮርስየኮምፒውተር ሳይንስ. እና ከ ሙያዊ መጻሕፍትበዚህ ርዕስ ላይ በአቀራረብ ተደራሽነት እና በሂሳብ አሠራሮች አጠቃቀም ተለይተው ይታወቃሉ ፣ ይህም በተግባር ከዚህ በላይ አይሄድም የትምህርት ቤት ኮርስየመጀመሪያ ደረጃ ሒሳብ.

የማስተማር እና የመማር ዘዴዎች

"የኮምፒዩተር ሳይንስ የሂሳብ መሠረቶች" ትምህርቱን ለማጥናት ከተማሪዎች ጋር አብሮ ለመስራት መሠረት በሚከተሉት የእድገት ትምህርት መርሆዎች ላይ የተመሠረተ ዘዴ ነው ።

የመማር መርህ ከፍተኛ ደረጃችግሮች;

የንድፈ እውቀት የመሪነት ሚና መርህ;

የድርጅት ትኩረት መርህ የትምህርት ሂደትእና የትምህርት ቁሳቁስ;

የቡድን ወይም የጋራ መስተጋብር መርህ;

የትምህርት ተግባራት ሁለገብነት መርህ.

ይህ ዘዴ በእውቀት (ኮግኒቲቭ) ሳይኮሎጂ መርሆዎች ላይ የተመሠረተ ነው-

በመማር ሂደት ውስጥ የሚነሱት እውቀት, ችሎታዎች እና ችሎታዎች አይደሉም, ነገር ግን የስነ-ልቦና አቻዎቻቸው - የግንዛቤ አወቃቀሮች, ማለትም, ተማሪው ዓለምን የሚመለከትበት, የሚያየው እና የሚገነዘበው እቅዶች;

የሰዎች ባህሪ መሪ መወሰኛ እንደ ማነቃቂያ ሳይሆን እውቀት ነው። በአንድ ሰው ዙሪያእውነታው, በአእምሮ ነጸብራቅ ሂደት ውስጥ የሚከሰት ውህደት;

ከሁሉም የሰው ልጅ ችሎታዎች የአስተሳሰብ ተግባር የአመለካከት, ትኩረት እና የማስታወስ እንቅስቃሴዎችን በማዋሃድ መሪ ነው;

ለ ሁሉን አቀፍ ልማትበስልጠናው ይዘት ውስጥ ማሰብ ፣ በተማሪዎች በቀጥታ ከሚያዙት ቁሳቁሶች በተጨማሪ ፣ የንድፈ ሃሳባዊ እና የንድፈ ሀሳብ ችግሮችን እና ችግሮችን ማካተት ያስፈልጋል ። ተግባራዊ ተፈጥሮ, መፍትሄው የሚፈልገው ገለልተኛ አስተሳሰብእና ምናብ, በርካታ የአዕምሮ ስራዎች, የፈጠራ አቀራረብእና የማያቋርጥ ፍለጋዎች;

ለ ውጤታማ እድገትማሰብ የእውቀት (ኮግኒቲቭ) ሳይኮሎጂየ “ከባድ ፍላጎት” ውጤትን እንዲጠቀሙ ይመክራል።

የተማሪዎችን የስኬት ደረጃ ለመገምገም ዘዴዎች

በከፍተኛ የችግር ደረጃ መማር የመዋሃድ ጥራትን በመቆጣጠር የተገለጸውን የችግር መለኪያን ከማክበር ጋር አብሮ ይመጣል። የማረጋገጫ እና የቁጥጥር ስርዓት የተለያዩ የቁጥጥር ዘዴዎችን ያካትታል, ነገር ግን በማንኛውም ሁኔታ ስርዓቱ ከተማሪዎች ጋር በተገናኘ የእድገት ተግባር ሊኖረው ይገባል. ይህንን ለማድረግ የሚከተሉት ሁኔታዎች መሟላት አለባቸው.

መምህሩ ሳይፈተሽ እና ሳይገመገም ምንም አይነት ስራ መተው የለበትም;

የኦዲት ውጤቱ ወዲያውኑ ሪፖርት መደረግ አለበት;

ተማሪው የጨረሰውን ስራ በማጣራት ሂደት ውስጥ በተቻለ መጠን መሳተፍ አለበት።

በቁጥጥሩ ውስጥ ያለው ዋናው ነገር እውቀትን እና ክህሎቶችን በማርክ መገምገም አይደለም, ነገር ግን የተለየ እና ምናልባትም የበለጠ ትክክለኛ ትርጉምየመማር ጥራት, በአንድ የተወሰነ ክፍል ውስጥ ለተለያዩ ተማሪዎች ባህሪያቱ.

የመማር መርህን በፍጥነት መተግበሩ የተማሪዎችን እውቀት እና ክህሎት የማያቋርጥ ክትትልን ያሳያል ፣ ምክንያቱም ሁሉም ተማሪዎች የቁሳቁስን ሙሉ በሙሉ የመቆጣጠር እምነት ከሌለ ወደ ፊት መሄድ ምንም ፋይዳ የለውም።

ስነ-ጽሁፍ

የኮምፒተር ሳይንስ የሂሳብ መሠረቶች። የተመረጠ ኮርስ: ዘዴያዊ መመሪያ / E. V. Andreeva, L. L. Bosova, I. N. Falina - M.: BINOM. የእውቀት ላቦራቶሪ, 2007. - 312 pp.: የታመመ.

የኮምፒተር ሳይንስ የሂሳብ መሠረቶች። የተመረጠ ኮርስ: የመማሪያ መጽሐፍ / ኢ.ቪ. አንድሬቫ, ኤል.ኤል. ቦሶቫ, I. N. Falina - 2 ኛ እትም, ተሻሽሏል. - ኤም.: BINOM. የእውቀት ላቦራቶሪ, 2007. - 328 pp.: የታመመ.

የኮምፒውተር ሳይንስ. ፕሮግራሞች ለ የትምህርት ተቋማት. ከ2-11ኛ ክፍል፡ methodological manual/በM.N.Borodin የተጠናቀረ። - ኤም.: BINOM. የእውቀት ላብራቶሪ, 2010. - 584 pp.: የታመመ. - (ፕሮግራሞች እና እቅድ).

የቀን መቁጠሪያ - ጭብጥ እቅድ ማውጣት- 9 ኛ ክፍል

№ p/p

ቀን የ

የክፍሎች ርዕስ, ትምህርቶች

የሰዓታት ብዛት

ጨምሮ

ቀን

ሀላፊነትን መወጣት

ቀን

በእውነቱ

የንድፈ ሐሳብ ትምህርቶች

የላቦራቶሪ እና ተግባራዊ ትምህርቶች

የቁጥር ስርዓቶች- 15 ሰዓታት

ከአቀማመጥ ቁጥር ስርዓቶች ጋር የተያያዙ መሠረታዊ ትርጓሜዎች.

የመሠረት ጽንሰ-ሐሳብ. የአቀማመጥ መርህ

በ P-ary ቁጥር ስርዓቶች ውስጥ የቁጥሮች ውክልና ልዩነት.

የአቀማመጥ ቁጥር ስርዓት አሃዞች

የተስፋፉ እና የወደቁ የአጻጻፍ ቁጥሮች ዓይነቶች።

በአቀማመጥ ቁጥር ስርዓቶች ውስጥ የዘፈቀደ ቁጥሮች ውክልና

በ P-ary ቁጥር ስርዓቶች ውስጥ የሂሳብ ስራዎች

ቁጥሮችን ከ P-ary ቁጥር ስርዓት ወደ አስርዮሽ በመቀየር ላይ

ቁጥሮችን ከአስርዮሽ ቁጥር ስርዓት ወደ P-ary ቁጥር ስርዓት መለወጥ

በበርካታ መሠረቶች የቁጥር ስርዓቶች መካከል ያለው ግንኙነት፡ P™ = Q

የቁጥር ስርዓቶች እና የኮምፒተር አርክቴክቸር

በኮምፒተር ላይ መረጃን ማቅረብ- 16 ሰዓታት

ኢንቲጀሮች ውክልና. ቀጥተኛ ኮድ. ተጨማሪ ኮድ

ኢንቲጀር አርቲሜቲክ በተወሰኑ አሃዞች ብዛት

የእውነተኛ ቁጥሮች መደበኛ ምልክት። ተንሳፋፊ ነጥብ ውክልና

የእውነተኛ ኮምፒዩተር አርቲሜቲክ ትግበራ ባህሪዎች

የጽሑፍ መረጃ አቀራረብ. ተግባራዊ ሥራ № 1

የግራፊክ መረጃ አቀራረብ.

ተግባራዊ ሥራ ቁጥር 2

የድምጽ መረጃ አቀራረብ

ዲጂታል መረጃን ለመጨመቅ ዘዴዎች.

ተግባራዊ ስራ ቁጥር 3 (ፋይሎችን በማስቀመጥ ላይ)

የፕሮጀክት ሥራ

የሎጂክ አልጀብራ መግቢያ - 22 ሰዓታት

የሎጂክ አልጀብራ። የንግግር ጽንሰ-ሀሳብ

ምክንያታዊ ክንውኖች

አመክንዮአዊ ቀመሮች፣ የእውነት ሰንጠረዦች፣ የሎጂክ አልጀብራ ህጎች

የሎጂክ አልጀብራ አተገባበር (የፅሁፍ አመክንዮ ችግሮችን መፍታት ወይም የወረዳ አልጀብራ መቀየር)

ቡሊያን ተግባራት

የሎጂክ ቀመሮች ቀኖናዊ ቅርጾች። SDNF ንድፈ ሐሳብ

በተከፋፈሉ መደበኛ ቅርጾች ክፍል ውስጥ የቡሊያን ተግባራትን መቀነስ

ኤስዲኤንኤፍን በመገንባት እና በመቀነስ ላይ ተግባራዊ ስራ

የቡሊያን ተግባራት ሙሉ ስርዓቶች. የወረዳ አካላት

የአልጎሪዝም ንድፈ ሐሳብ አካላት - 21 ሰዓታት

የአልጎሪዝም ጽንሰ-ሐሳብ. የአልጎሪዝም ባህሪያት

የአልጎሪዝም ዓይነቶች, የአጻጻፍ ስልተ ቀመሮች መንገዶች.

ስልተ ቀመሮችን በማጠናቀር ላይ ችግሮችን መፍታት

የአልጎሪዝም ጽንሰ-ሐሳብ ማብራሪያ. የቱሪንግ ማሽን.

የቱሪንግ ማሽን ፕሮግራሚንግ ችግሮችን መፍታት

የፖስታ ማሽን እንደ የአልጎሪዝም ፅንሰ-ሀሳብ ማሻሻያ

በአልጎሪዝም ሊፈቱ የማይችሉ ችግሮች እና ሊሰሉ የሚችሉ ተግባራት

የአልጎሪዝም ውስብስብነት ጽንሰ-ሀሳብ

ስልተ ቀመሮችን ይፈልጉ

አልጎሪዝም መደርደር

በርዕሱ ላይ የፕሮጀክት ሥራ " ባህላዊ ጠቀሜታየአልጎሪዝም ጽንሰ-ሀሳብን መደበኛ ማድረግ"

የመረጃ ንድፈ ሐሳብ መሰረታዊ ነገሮች - 13 ሰዓታት

የመረጃ ጽንሰ-ሐሳብ. የመረጃ መጠን።

የመረጃ ክፍሎች

የሃርትሊ ቀመር

የሃርትሊ ቀመር አተገባበር

የመረጃ ተጨማሪነት ህግ

የሻነን ቀመር

ምርጥ የመረጃ ኮድ. የሃፍማን ኮድ

የስሌት ጂኦሜትሪ እና የኮምፒተር ግራፊክስ የሂሳብ መሰረቶች- 9 ሰዓታት

በአውሮፕላኑ ላይ መጋጠሚያዎች እና ቬክተሮች

በአውሮፕላን ላይ መስመሮችን የሚገልጹ ዘዴዎች

በነጥቦች እና በቁጥሮች አንጻራዊ አቀማመጥ ላይ የኮምፒተር ግራፊክስ ችግሮች

ፖሊጎኖች

በጠፈር ውስጥ ያሉ ጂኦሜትሪክ ነገሮች

መግቢያ 3

1 ግራፍ ቲዎሪ 5

1.1 የግራፍ ንድፈ ሐሳብ ጽንሰ-ሐሳብ እና ቃላት 5

1.2 አንዳንድ የግራፍ ቲዎሪ ችግሮች 6

2 የሂሳብ አመክንዮ እና ዓይነት ቲዎሪ 25

መደምደሚያ 27

ማጣቀሻ 30

መግቢያ

ውስጥ በሰፊው ስሜትየኮምፒዩተር ሳይንስ (ከጀርመን ኢንፎርማቲክ እና ከፈረንሳይ ኢንፎርማቲክ ጋር በማነፃፀር፣ በድምፅ እና በመነሻ ተመሳሳይነት ካለው፣ ከእንግሊዝኛው ባህላዊ የእንግሊዝኛ ቋንቋ ቃል በተቃራኒ። የኮምፒውተር ሳይንስ- የኮምፒውተር ሳይንስ - በአሜሪካ ወይም በእንግሊዝኛ። የኮምፒውተር ሳይንስ - በብሪታንያ ውስጥ መረጃን የማስላት ፣ የማከማቸት እና የማቀናበር ሳይንስ አለ። በአንድ ወይም በሌላ መንገድ ተዛማጅ ትምህርቶችን ያካትታል ኮምፒውተሮችሁለቱም ረቂቅ ፣ እንደ አልጎሪዝም ትንተና ፣ እና በጣም ልዩ ፣ ለምሳሌ የፕሮግራም ቋንቋዎች እድገት።

በቤተክርስቲያን-ቱሪንግ ተሲስ መሠረት ሁሉም ነገር የታወቁ ዓይነቶችኮምፒውተሮች በችሎታቸው በጥራት አቻ ናቸው፡ በአንዱ ላይ ሊደረግ የሚችል ማንኛውም ድርጊት ኮምፒውተር፣ በሌላ በኩል ደግሞ የሚቻል ነው። ተሲስ አንዳንድ ጊዜ የኮምፒውተር ሳይንስ መሠረታዊ መርህ ሆኖ ይቀርባል, ጥሪ ልዩ ትኩረትቱሪንግ ማሽን እና ቮን ኑማን ማሽን ከአብዛኛዎቹ የአሁኑ ኮምፒተሮች ጋር ግልጽ ተመሳሳይነት ስላላቸው። ውስጥ ዘመናዊ የኮምፒውተር ሳይንስሳይንቲስቶች ሌሎች የማሽን ዓይነቶችን በማጥናት ላይ ናቸው፣ በተግባር ሊተገበሩ የሚችሉትን ብቻ ሳይሆን (እንደ ትይዩ እና የመሳሰሉት) ኳንተም ኮምፒውተሮች), ግን ደግሞ ሙሉ በሙሉ ረቂቅ የሂሳብ ሞዴሎች(ለምሳሌ፣ ማለቂያ የሌለው ቁጥር ያለው የመመዝገቢያ ማሽን)።

በኮምፒዩተር ሳይንስ ውስጥ የምርምር ርዕሰ ጉዳዮች ጥያቄዎች ናቸው-በፕሮግራሞች ውስጥ ምን ሊተገበር እና ሊተገበር የማይችል (የኮምፒውተሬሽን ፅንሰ-ሀሳብ እና) ሰው ሰራሽ የማሰብ ችሎታልዩ ችግሮች በከፍተኛ ብቃት (አልጎሪዝም) እንዴት እንደሚፈቱ፣ መረጃ በምን ዓይነት መልክ መቀመጥ እና መመለስ እንዳለበት የተወሰነ ዓይነት(የውሂብ አወቃቀሮች)፣ ፕሮግራሞች እና ሰዎች እንዴት መስተጋብር እንደሚፈጥሩ (የተጠቃሚ በይነገጽ እና የፕሮግራም ቋንቋዎች)፣ ወዘተ.

የኮምፒውተር ሳይንስ እንደ የተለየ ሳይንስ እውቅና ያገኘው በ1970ዎቹ ብቻ ነው። ከዚያ በፊት እንደ ሂሳብ፣ ኤሌክትሮኒክስ እና ሌሎች አካል ሆኖ አዳብሯል። የቴክኒክ ሳይንሶች. አንዳንድ የኮምፒዩተር ሳይንስ ጅምር በቋንቋዎች ውስጥ እንኳን ሊገኙ ይችላሉ። እንደ የተለየ ሳይንስ እውቅና ከሰጠበት ጊዜ ጀምሮ የኮምፒዩተር ሳይንስ አዳብሯል። የራሱ ዘዴዎችእና ቃላት.

የመጀመሪያው የኮምፒውተር ሳይንስ ክፍል በፑርዱ ዩኒቨርሲቲ በ1962 ተመሠረተ። ዛሬ የኮምፒዩተር ሳይንስ ፋኩልቲዎች እና ክፍሎች በአለም ዙሪያ ባሉ አብዛኛዎቹ ዩኒቨርሲቲዎች ይገኛሉ።

በኮምፒዩተር ሳይንስ ዘርፍ ላስመዘገቡ ውጤቶች ከፍተኛው ሽልማት የቱሪንግ ሽልማት ነው።

1 ግራፍ ንድፈ ሐሳብ

የግራፍ ቲዎሪ የግራፍ ባሕሪያትን የሚያጠና የልዩ የሂሳብ ክፍል ነው። በጥቅሉ ሲታይ፣ ግራፍ በዳርቻዎች የተገናኙ የቋሚዎች ስብስብ (አንጓዎች) ሆኖ ቀርቧል። በጥብቅ ፍቺ, ግራፍ እንደዚህ አይነት ጥንድ ስብስቦች ነው

G=(አር፣ቪ)፣

V የማንኛውም ሊቆጠር የሚችል ስብስብ ንዑስ ክፍል ከሆነ ፣

እና R የV×V ንዑስ ስብስብ ነው።

ሩዝ. 1. ስድስት ጫፎች እና ሰባት ጠርዞች ያለው ግራፍ

የግራፍ ቲዎሪ መተግበሪያን ያገኛል፣ ለምሳሌ፣ በ የጂኦግራፊያዊ መረጃ ስርዓቶች(ጂአይኤስ) ነባር ወይም አዲስ የተነደፉ ቤቶች፣ አወቃቀሮች፣ ብሎኮች፣ወዘተ እንደ ጫፍ ተደርገው የሚወሰዱት መንገዶች፣ የመገልገያ ኔትወርኮች፣ የኤሌክትሪክ መስመሮች፣ ወዘተ የሚያገናኙት እንደ ጠርዝ ነው። በእንደዚህ ዓይነት ግራፍ ላይ የተከናወኑ የተለያዩ ስሌቶችን መጠቀም ለምሳሌ በጣም አጭሩን የመቀየሪያ መንገድ ወይም በአቅራቢያው የሚገኘውን የግሮሰሪ መደብር ለማግኘት ወይም ጥሩውን መንገድ ለማቀድ ያስችላል (ምሥል 1 ይመልከቱ)።

የግራፍ ንድፈ ሐሳብ ቃላቶች አሁንም በጥብቅ አልተገለጸም. በተለይ፣ በአንድ ነጠላ ግራፍ ጉድማን፣ Hidetniemi፣ 1981 “በፕሮግራሚንግ አለም ውስጥ የለም መግባባትከሁለቱ "ግራፍ" ወይም "አውታረ መረብ" ስለ የትኛው ነው. "አውታረ መረብ" የሚለውን ቃል የመረጥነው በመተግበሪያ ቦታዎች ላይ በጣም የተለመደ ስለሚመስል ነው።

* በ 1736 በኡለር የታተመው በግራፍ ንድፈ ሃሳብ ውስጥ ከመጀመሪያዎቹ ውጤቶች አንዱ የኮኒግስበርግ ሰባት ድልድዮች አንዱ ነው።

* የአራት ቀለማት ችግር በ1852 ተቀርጾ ነበር፣ ነገር ግን ማስረጃው የተገኘው በ1976 ብቻ ነው (በአውሮፕላኑ ላይ ላለው ካርታ 4 ቀለሞች በቂ ናቸው)።

* የተጓዥ ሻጭ ችግር በጣም ዝነኛ ከሆኑት NP-የተሟሉ ችግሮች አንዱ ነው።

* የክሊክ ችግር ሌላ NP-የተሟላ ችግር ነው።

* ዝቅተኛውን የተንጣለለ ዛፍ መፈለግ.

ተጓዥ ነጋዴ ችግርበተጠቀሱት ከተሞች ውስጥ ቢያንስ አንድ ጊዜ የሚያልፈውን በጣም ትርፋማ መንገድ ማግኘትን ያካትታል። የችግሩ ሁኔታዎች የመንገዱን ትርፋማነት መስፈርት (አጭር ፣ ርካሽ ፣ አጠቃላይ መስፈርት ፣ ወዘተ) እና ርቀቶችን ፣ ወጪዎችን ፣ ወዘተ ያሉትን ተዛማጅ ማትሪክስ ያመለክታሉ ። እንደ ደንቡ ፣ መንገዱ በእያንዳንዱ ማለፍ እንዳለበት ይጠቁማል ። ከተማ አንድ ጊዜ ብቻ ነው, በዚህ ሁኔታ ምርጫው በሃሚልቶኒያ ዑደቶች መካከል ነው.

ብዙ የአጠቃላይ የችግር አፈጣጠር ዓይነቶች አሉ, በተለይም የጂኦሜትሪክ ችግርተጓዥ ሻጭ (የርቀት ማትሪክስ በአውሮፕላኑ ላይ ባሉ ነጥቦች መካከል ያለውን ርቀት ሲያንፀባርቅ) የሶስት ማዕዘን ችግርተጓዥ ሻጭ (የሶስት ማዕዘኑ እኩልነት በወጪ ማትሪክስ ላይ ሲረካ) ፣ የተመጣጠነ እና ያልተመጣጠነ ተጓዥ ሻጭ ችግሮች።

የተጓዥ ሻጩን ችግር ለመፍታት በጣም ቀላሉ ዘዴዎች፡ አድካሚ የቃላት ፍተሻ፣ ስግብግብ ስልተ ቀመሮች (የቅርብ ጎረቤት ዘዴ፣ የቅርብ ከተማ የማካተት ዘዴ፣ በጣም ርካሹ የማካተት ዘዴ)፣ ዝቅተኛው የዛፍ መዘርጋት ዘዴ። በተግባር, የተለያዩ ማሻሻያዎች የበለጠ ጥቅም ላይ ይውላሉ ውጤታማ ዘዴዎች: የቅርንጫፍ እና የታሰረ ዘዴ እና ዘዴ የጄኔቲክ አልጎሪዝም, እንዲሁም የጉንዳን ቅኝ አልጎሪዝም.

የተጓዥ ሻጩን ችግር ለመፍታት ሁሉም ውጤታማ (የተሟላ ፍለጋን በመቀነስ) ዘዴዎች ሄሪስቲክ ዘዴዎች ናቸው። አብዛኛዎቹ የሂዩሪስቲክ ዘዴዎች በጣም ቀልጣፋ መንገድ አያገኙም, ግን ግምታዊ መፍትሄ. ብዙውን ጊዜ, በማንኛውም ጊዜ የሚባሉት ስልተ ቀመሮች በፍላጎት ላይ ናቸው, ማለትም, አንዳንድ ወቅታዊ ግምታዊ መፍትሄዎችን ቀስ በቀስ ያሻሽላሉ.

ተጓዥ ሻጭ ችግር NP-የተሟላ ችግር ነው። ብዙ ጊዜ አድካሚ ፍለጋን ለመቀነስ አዳዲስ አቀራረቦችን ለመሞከር ይጠቅማል።

በፊደል Σ የቃላት ስብስብ ቋንቋ እንበለው። እዚህ ያለው ተግዳሮት አለመሆኑን ለመወሰን ነው። የተሰጠ ቃልቋንቋ ወይም አይደለም. ቋንቋ ኤል 1 ሬዲሲብል ተብሎ ይጠራል (በካርፕ መሠረት) ለአንድ ቋንቋ ኤል 2 ተግባሩ ካለ ፣

, በብዙ ቁጥር የሚሰላ ጊዜ፣ የሚከተለው ንብረት ያለው፡ ረ(x)ንብረት ነው። ኤል 2 ከሆነ እና ከሆነ ብቻ xንብረት ነው። ኤል 111 1 . ቋንቋ ኤል 2 ከክፍል NP ማንኛውም ቋንቋ ወደ እሱ መቀነስ ከተቻለ NP-hard ይባላል። አንድ ቋንቋ NP-hard ከሆነ እና በተመሳሳይ ጊዜ በክፍል NP ውስጥ የሚገኝ ከሆነ NP-complete ይባላል። ስለዚህ፣ በፖሊኖሚል ጊዜ ውስጥ ቢያንስ አንድ NP የተሟላ ችግር የሚፈታ ስልተ-ቀመር ከተገኘ፣ ሁሉም የኤንፒ ችግሮች በክፍል ፒ ውስጥ ይሆናሉ።

ወደ ተጓዥ ሻጭ ችግር እንመለስ።

የሂሳብ ሞዴል.

የመጀመሪያ ሞዴል መለኪያዎች.

Let i = 0,1,2,...,m - የከተማ ቁጥሮች, i=0 - የተመረጠው ከተማ ቁጥር (የመንገዱ መጀመሪያ እና መጨረሻ). በ R= እንጥቀስ

r(i,j) - (m+1)(m+1) የርቀት ማትሪክስ፣ የዚያ አካል r(i,j) በከተማ ቁጥር i እና በከተማ ቁጥር j መካከል ያለው ርቀት ነው።

ተለዋዋጭ ሞዴል መለኪያዎች.

በ X = እንጥቀስ

x(i,j) - (m+1)(m+1) ያልታወቀ ማትሪክስ፣ የዚ አካል x(i,j) =1፣ ተጓዥ ሻጭ ከከተማ ቁጥር ወደ ከተማ ቁጥር j ከተዘዋወረ x() i,j) = 0, ኢን አለበለዚያ; u(i) ልዩ ተለዋዋጮች ናቸው፣ i=1፣2፣...m.

የሂሳብ ሞዴል ገደቦች.

x(i,j) =1, j=1,2,...,m, (1) x(i,j) =1, i=1,2,...,m, (2)

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, i

j.፣ (3) (0፣1)። (4)

እዚህ, ሁኔታዎች (1) ማለት ተጓዥ ሻጭ ወደ እያንዳንዱ ከተማ በትክክል አንድ ጊዜ ይገባል (ከከተማ ቁጥር 0 በስተቀር); ሁኔታዎች (2) ማለት ተጓዥ ሻጭ እያንዳንዱን ከተማ በትክክል አንድ ጊዜ ለቆ ይወጣል (ከከተማ ቁጥር 0 በስተቀር) ፣ ገደቦች (3) ማለት የአንድ ዑደት መኖር ብቻ ነው ፣ ከከተማ ቁጥር 0 ጀምሮ ፣ በሁሉም ከተሞች ውስጥ አልፎ በከተማ ቁጥር ያበቃል። 0; እገዳዎች (4) በተዋወቁት ተለዋዋጮች ላይ ተፈጥሯዊ ሁኔታዎች ናቸው.

ሁኔታዎች (3) አስፈላጊ መሆናቸውን እናሳይ በቂ ሁኔታዎችየአንድ ዑደት ብቻ መኖር.

በእርግጥ, ይህ እንደዚያ ባይሆንም, ከከተሞች ብዛት ጋር አንድ ንዑስ ዑደት አለ k

በሌላ በኩል በሁሉም ከተሞች ውስጥ ለሚያልፍ ዑደት በከተማ ቁጥር 0 ተጀምሮ የሚያልቅ፣ ሁኔታዎችን የሚያሟሉ (3) እሴቶች እንዳሉ እናሳያለን።

የከተማ ቁጥር ከሆነ በ pth ተጓዥ ሻጭ የምጎበኘው u(i)=p እናስቀምጥ በቅደም ተከተል፣ p=1፣2፣...፣m

x(i,j) = 0. ከዚያም ሁኔታዎች (3) ቅጹን እንውሰድ፡-

u(i) - u(j) m-1፣ እውነት ነው፣ ከገጽ 0.

መግቢያ 3

1 ግራፍ ቲዎሪ 5

1.1 የግራፍ ንድፈ ሐሳብ ጽንሰ-ሐሳብ እና ቃላት 5

1.2 አንዳንድ የግራፍ ቲዎሪ ችግሮች 6

2 የሂሳብ አመክንዮ እና ዓይነት ቲዎሪ 25

መደምደሚያ 27

ማጣቀሻ 30

መግቢያ

ሰፋ ባለ መልኩ የኮምፒዩተር ሳይንስ (ከጀርመን ኢንፎርማቲክ እና ከፈረንሳይ ኢንፎርማቲክ ጋር በማነፃፀር በድምፅ እና በመነሻ ተመሳሳይነት ካለው የእንግሊዘኛ ባህላዊ የኮምፒዩተር ሳይንስ - የኮምፒዩተር ሳይንስ - በአሜሪካ ወይም በእንግሊዘኛ ኮምፒዩቲንግ ሳይንስ - ኮምፒዩቲንግ) ሳይንስ - በብሪታንያ ውስጥ መረጃን ስለ ማስላት ፣ ማከማቸት እና ማቀናበር ሳይንስ አለ ። እሱ በአንድ ወይም በሌላ መንገድ ከኮምፒዩተር ጋር የተዛመዱ ትምህርቶችን ያጠቃልላል-ሁለቱም ረቂቅ ፣ እንደ አልጎሪዝም ትንተና እና በጣም ልዩ ፣ ለምሳሌ የ የፕሮግራም ቋንቋዎች.

በቸርች-ቱሪንግ ተሲስ መሠረት ሁሉም የሚታወቁ የኮምፒዩተሮች ዓይነቶች በችሎታዎቻቸው በጥራት እኩል ናቸው-በአንድ ኮምፒዩተር ላይ የሚደረግ ማንኛውም ተግባር በሌላኛው ላይም ሊከናወን ይችላል። ተሲስ አንዳንድ ጊዜ እንደ መሰረታዊ የኮምፒዩተር ሳይንስ መርሆ ነው የሚቀርበው፣ በተለይም የቱሪንግ ማሽን እና የ ቮን ኑማን ማሽንን በማጣቀስ ከአብዛኞቹ ኮምፒውተሮች ጋር ግልጽ የሆነ ተመሳሳይነት ስላላቸው ነው። በዘመናዊ የኮምፒዩተር ሳይንስ ማዕቀፍ ውስጥ ሳይንቲስቶች እንዲሁ ሌሎች የማሽን ዓይነቶችን ያጠናሉ ፣ በተግባር ሊተገበሩ የሚችሉትን (እንደ ትይዩ እና ኳንተም ኮምፒተሮች ያሉ) ብቻ ሳይሆን ሙሉ በሙሉ ረቂቅ የሂሳብ ሞዴሎችን (ለምሳሌ ፣ የዘፈቀደ መዳረሻ ማሽን ማለቂያ የሌለው ቁጥር ያለው ማሽን) መዝገቦች)።

በኮምፒዩተር ሳይንስ ውስጥ የምርምር ርዕሰ ጉዳዮች የሚከተሉትን ጥያቄዎች ያጠቃልላሉ-በፕሮግራሞች ውስጥ ምን ሊተገበር እና ሊተገበር የማይችል (የኮምፒዩቲቢሊቲ ቲዎሪ እና አርቴፊሻል ኢንተለጀንስ) ፣ ልዩ ችግሮች በከፍተኛ ብቃት (አልጎሪዝም) እንዴት እንደሚፈቱ ፣ የአንድ የተወሰነ ዓይነት መረጃ በምን ዓይነት መልክ መቀመጥ እንዳለበት። እና ወደነበረበት የተመለሰ (የውሂብ አወቃቀሮች))፣ ፕሮግራሞች እና ሰዎች እንዴት እርስበርስ መስተጋብር እንዳለባቸው (የተጠቃሚ በይነገጽ እና የፕሮግራም ቋንቋዎች)፣ ወዘተ.

የኮምፒውተር ሳይንስ እንደ የተለየ ሳይንስ እውቅና ያገኘው በ1970ዎቹ ብቻ ነው። ከዚያ በፊት የሒሳብ፣ የኤሌክትሮኒክስና ሌሎች ቴክኒካል ሳይንሶች አካል ሆኖ አዳብሯል። አንዳንድ የኮምፒዩተር ሳይንስ ጅምር በቋንቋዎች ውስጥ እንኳን ሊገኙ ይችላሉ። እንደ የተለየ ሳይንስ እውቅና ከሰጠበት ጊዜ ጀምሮ የኮምፒዩተር ሳይንስ የራሱን ዘዴዎች እና የቃላት አገባብ አዘጋጅቷል.

በኮምፒዩተር ሳይንስ ዘርፍ ላስመዘገቡ ውጤቶች ከፍተኛው ሽልማት የቱሪንግ ሽልማት ነው።

1 ግራፍ ንድፈ ሐሳብ

G=(አር፣ቪ)፣

V የማንኛውም ሊቆጠር የሚችል ስብስብ ንዑስ ክፍል ከሆነ ፣

እና R የV×V ንዑስ ስብስብ ነው።

ሩዝ. 1. ስድስት ጫፎች እና ሰባት ጠርዞች ያለው ግራፍ

የግራፍ ቲዎሪ መተግበሪያን ያገኛል፣ ለምሳሌ፣ በጂኦግራፊያዊ መረጃ ስርዓቶች (ጂአይኤስ)። ነባር ወይም አዲስ የተነደፉ ቤቶች፣ አወቃቀሮች፣ ብሎኮች፣ወዘተ እንደ ጫፍ ተደርገው የሚወሰዱት መንገዶች፣ የመገልገያ ኔትወርኮች፣ የኤሌክትሪክ መስመሮች፣ ወዘተ የሚያገናኙት እንደ ጠርዝ ነው። በእንደዚህ ዓይነት ግራፍ ላይ የተከናወኑ የተለያዩ ስሌቶችን መጠቀም ለምሳሌ በጣም አጭሩን የመቀየሪያ መንገድ ወይም በአቅራቢያው የሚገኘውን የግሮሰሪ መደብር ለማግኘት ወይም ጥሩውን መንገድ ለማቀድ ያስችላል (ምሥል 1 ይመልከቱ)።

የግራፍ ንድፈ ሐሳብ ቃላቶች አሁንም በጥብቅ አልተገለጸም. በተለይም በ monograph Goodman, Hidetniemi, 1981 "በፕሮግራሚንግ አለም ውስጥ "ግራፍ" ወይም "ኔትወርክ" ከሚሉት ሁለት ቃላት የትኛው ላይ መግባባት የለም. "አውታረ መረብ" የሚለውን ቃል የመረጥነው በመተግበሪያ ቦታዎች ላይ በጣም የተለመደ ስለሚመስል ነው።

* በ 1736 በኡለር የታተመው በግራፍ ንድፈ ሃሳብ ውስጥ ከመጀመሪያዎቹ ውጤቶች አንዱ የኮኒግስበርግ ሰባት ድልድዮች አንዱ ነው።

* የተጓዥ ሻጭ ችግር በጣም ዝነኛ ከሆኑት NP-የተሟሉ ችግሮች አንዱ ነው።

* የክሊክ ችግር ሌላ NP-የተሟላ ችግር ነው።

* ዝቅተኛውን የተንጣለለ ዛፍ መፈለግ.

የችግሩ አጠቃላይ አቀነባበር ብዙ ዓይነቶች አሉ ፣ በተለይም የጂኦሜትሪክ ተጓዥ ሻጭ ችግር (የርቀት ማትሪክስ በአውሮፕላኑ ላይ ባሉ ነጥቦች መካከል ያለውን ርቀት ሲያንፀባርቅ) ፣ የሶስት ጎንዮሽ ተጓዥ ሻጭ ችግር (የሦስት ማዕዘኑ አለመመጣጠን በወጪ ማትሪክስ ላይ ሲረካ) ፣ የተመጣጠነ እና ያልተመጣጠነ ተጓዥ ሻጭ ችግሮች።

የተጓዥ ሻጩን ችግር ለመፍታት በጣም ቀላሉ ዘዴዎች፡ አድካሚ የቃላት ፍተሻ፣ ስግብግብ ስልተ ቀመሮች (የቅርብ ጎረቤት ዘዴ፣ የቅርብ ከተማ የማካተት ዘዴ፣ በጣም ርካሹ የማካተት ዘዴ)፣ ዝቅተኛው የዛፍ መዘርጋት ዘዴ። በተግባር, የበለጠ ውጤታማ ዘዴዎች የተለያዩ ማሻሻያዎች ጥቅም ላይ ይውላሉ: የቅርንጫፍ እና የታሰረ ዘዴ እና የጄኔቲክ አልጎሪዝም ዘዴ, እንዲሁም የጉንዳን ቅኝ ስልተ-ቀመር.

ተጓዥ ሻጭ ችግር NP-የተሟላ ችግር ነው። ብዙ ጊዜ አድካሚ ፍለጋን ለመቀነስ አዳዲስ አቀራረቦችን ለመሞከር ይጠቅማል።

በፊደል Σ የቃላት ስብስብ ቋንቋ እንበለው። እዚህ ያለው ተግባር የተሰጠው ቃል የቋንቋው መሆኑን ወይም አለመሆኑን መወሰን ነው። ቋንቋ ኤል 1 ሬዲሲብል ተብሎ ይጠራል (በካርፕ መሠረት) ለአንድ ቋንቋ ኤል 2 ተግባሩ ካለ ፣ , በብዙ ቁጥር የሚሰላ ጊዜ፣ የሚከተለው ንብረት ያለው፡ ረ(x)ንብረት ነው። ኤል 2 ከሆነ እና ከሆነ ብቻ xንብረት ነው። ኤል 111 1 . ቋንቋ ኤል 2 ከክፍል NP ማንኛውም ቋንቋ ወደ እሱ መቀነስ ከተቻለ NP-hard ይባላል። አንድ ቋንቋ NP-hard ከሆነ እና በተመሳሳይ ጊዜ በክፍል NP ውስጥ የሚገኝ ከሆነ NP-complete ይባላል። ስለዚህ፣ በፖሊኖሚል ጊዜ ውስጥ ቢያንስ አንድ NP የተሟላ ችግር የሚፈታ ስልተ-ቀመር ከተገኘ፣ ሁሉም የኤንፒ ችግሮች በክፍል ፒ ውስጥ ይሆናሉ።

ወደ ተጓዥ ሻጭ ችግር እንመለስ።

የሂሳብ ሞዴል.

የመጀመሪያ ሞዴል መለኪያዎች.

Let i = 0,1,2,...,m - የከተማ ቁጥሮች, i=0 - የተመረጠው ከተማ ቁጥር (የመንገዱ መጀመሪያ እና መጨረሻ). በ R=r(i,j) - (m+1)(m+1) የርቀት ማትሪክስ እንጥቀስ፣ የዚያ አካል r(i,j) በከተማ ቁጥር i እና በከተማ ቁጥር j መካከል ያለው ርቀት ነው።

ተለዋዋጭ ሞዴል መለኪያዎች.

በ X=x(i,j) - (m+1)(m+1) ያልታወቁ ማትሪክስ፣ የዚያን አካል x(i,j) =1፣ ከከተማ ቁጥር የመጣ ተጓዥ ሻጭ ከተንቀሳቀሰ እናሳይ ወደ ከተማ ቁጥር j, x (i,j) = 0, አለበለዚያ; u(i) ልዩ ተለዋዋጮች ናቸው፣ i=1፣2፣...m.

የሂሳብ ሞዴል ገደቦች.

x (i,j) =1, j=1,2,...,m, (1)

x (i,j) =1, i=1,2,...,m, (2)

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, ij., (3)

x (i,j) (0,1) (4)

ሁኔታዎች (3) ለአንድ ዑደት ብቻ መኖር አስፈላጊ እና በቂ ሁኔታዎች መሆናቸውን እናሳይ።

በእርግጥ, ይህ እንደዚያ ባይሆንም, ከከተሞች ብዛት ጋር አንድ ንዑስ ዑደት አለ k

የከተማ ቁጥር ከሆነ በ pth ተጓዥ ሻጭ የምጎበኘው u(i)=p እናስቀምጥ በቅደም ተከተል፣ p=1፣2፣...፣m

x(i,j) = 0. ከዚያም ሁኔታዎች (3) ቅጹን እንውሰድ፡-

u(i) - u(j) m-1፣ እውነት ነው፣ ከገጽ 0.

እንበል x(i,j) = 1. ከዚያም u(i) = p ከሆነ, ከዚያም u(j)=p+1 (ይህም የከተማ ቁጥር j ከከተማ በኋላ በሚወስደው መንገድ ላይ በተጓዥ ሻጭ መስመር ላይ ስለሚገኝ ነው. ቁጥር i). እናገኛለን፡-

u (i) - u (j) + m x (i,j) = p - (p+1) +m = m - 1, ይህም በአምሳያው ውስጥ ገደቦች (3) መኖራቸውን ትክክለኛነት ያረጋግጣል.

የማመቻቸት ችግር መግለጫ.

ለተጓዥ ሻጭ ችግር የተመቻቸ መስፈርት የሚከተለው ቅፅ አለው።

F(X)= r(i,j) x(i,j) ደቂቃ . (5)

ችግር (1) - (5) የተጓዥ ሻጭ ችግር ወይም የተጓዥ ነጋዴ ችግር ይባላል።

የታሰበውን የሂሳብ ሞዴል በመጠቀም, የሚከተሉት የተተገበሩ ችግሮች ተገልጸዋል-የልዩ መሳሪያዎችን የመቀያየር ጊዜ የመቀነስ ችግር; የተጠናቀቁ ምርቶችን ለተጠቃሚዎች የማድረስ ተግባር; የበረዶ ማስወገጃ ማሽኖችን ሥራ የመቆጣጠር ተግባር, ወዘተ.

የቦሊያን ቀመሮች እርካታ ችግር። የቦሊያን ቀመሮች (SAT ወይም SAT) የእርካታ ችግር ለሂሳብ ውስብስብነት ፅንሰ-ሀሳብ አስፈላጊ እውቅና ያለው ችግር ነው።

የSAT ችግር ምሳሌ ተለዋዋጭ ስሞችን፣ ቅንፎችን እና ኦፕሬሽኖችን (ኦፕሬሽኖችን) ብቻ ያቀፈ የቦሊያን ቀመር ነው። እና), (ወይም) እና ( እሱ). ችግሩ: በቀመሩ ውስጥ ለሚታዩ ሁሉም ተለዋዋጮች እሴቶችን መመደብ ይቻላል? ውሸትእና እውነትቀመሩ እውነት ይሆን ዘንድ።

በ1971 በእስጢፋኖስ ኩክ የተረጋገጠው የኩክ ቲዎረም መሰረት፣ የ SAT ችግር NP-ሙሉ ነው።

የመለየት ችግርን በግልፅ ለመቅረጽ በየትኛው የቋንቋ አጋጣሚዎች በተገለጹት ፊደሎች ላይ መስማማት አስፈላጊ ነው. ይህ ፊደል ቋሚ እና የተወሰነ መሆን አለበት። ሆፕክሮፍት፣ ሞትዋኒ እና ኡልማን በመጽሐፋቸው ላይ የሚከተሉትን ፊደላት መጠቀምን ይጠቁማሉ፡- (""""""""(",")"" x", "0", "1").

እንደዚህ አይነት ፊደላትን ሲጠቀሙ ቅንፍ እና ኦፕሬተሮች በተፈጥሮ የተፃፉ ሲሆን ተለዋዋጮችም እንደሚከተለው ይሰየማሉ-x1, x10, x11, x100, ወዘተ., በቁጥር ሁለትዮሽ ስርዓት ውስጥ በተፃፉት ቁጥሮች መሰረት.

አንዳንድ የቡሊያን ፎርሙላ፣ በተለመደው የሒሳብ ኖት የተፃፈ፣ ረጅም ይሁን ኤንቁምፊዎች. በእሱ ውስጥ, የእያንዳንዱ ተለዋዋጭ እያንዳንዱ ክስተት ቢያንስ በአንድ ምልክት ተብራርቷል, ስለዚህ, በጠቅላላው ከዚህ በላይ የለም ኤንተለዋዋጮች. ይህ ማለት ከላይ በቀረበው ማስታወሻ ላይ እያንዳንዱ ተለዋዋጭ ምልክቶችን በመጠቀም ይጻፋል ማለት ነው። በዚህ ሁኔታ ፣ በአዲሱ ማስታወሻ ውስጥ ያለው አጠቃላይ ቀመር የቁምፊዎች ርዝመት ይኖረዋል ፣ ማለትም ፣ የሕብረቁምፊው ርዝመት በፖሊኖሚል ብዛት ይጨምራል።

ለምሳሌ, ቀመር ቅጹን ይወስዳል.

የኮኒግስበርግ ሰባት ድልድዮች።የኮኒግስበርግ ሰባት ድልድዮች በ 16 ኛው -20 ኛው ክፍለ ዘመን በኮንጊስበርግ (በአሁኑ ጊዜ ካሊኒንግራድ) ነበሩ (ምስል 2 ይመልከቱ)። የድልድዮቹ አንጻራዊ አቀማመጥ የሒሳብ ሊቅ ሊዮንሃርድ ኡለር እንዲያስብ አነሳስቶታል፣ ይህም የግራፍ ንድፈ ሐሳብ እንዲፈጠር ምክንያት ሆኗል።

ሩዝ. 2. የኮኒግስበርግ የድሮ ካርታ. ፊደሎቹ የከተማውን ክፍሎች ያመለክታሉ-A - Altstadt, B - Kneiphof, C - Lomse, D - Forstadt. ቁጥሮቹ ድልድዮችን ያመለክታሉ (በግንባታ ቅደም ተከተል): 1 - ላቮችኒ, 2 - አረንጓዴ, 3 - ሰራተኛ, 4 - ኩዝኒችኒ, 5 - የእንጨት, 6 - ከፍተኛ, 7 - ማር.

የሚከተለው እንቆቅልሽ በኮንጊስበርግ ነዋሪዎች መካከል ለረጅም ጊዜ የተለመደ ነበር-ሁሉንም ድልድዮች ሁለት ጊዜ ሳያቋርጡ እንዴት እንደሚሻገሩ? ብዙ Königsbergers በእግር በሚጓዙበት ጊዜ ይህንን ችግር በንድፈ ሀሳብ እና በተግባር ለመፍታት ሞክረዋል ። ነገር ግን ማንም ይህን ማድረግ አልቻለም, ነገር ግን በንድፈ ሀሳብ እንኳን የማይቻል መሆኑን አረጋግጠዋል.

እ.ኤ.አ. በ 1736 የሰባት ድልድዮች ችግር በማርች 13 ቀን 1736 ለጣሊያን የሒሳብ ሊቅ እና መሐንዲስ ማሪዮኒ በጻፈው ደብዳቤ የጻፈውን የላቀውን የሂሳብ ሊቅ ፣ የሴንት ፒተርስበርግ የሳይንስ አካዳሚ አባል ሊዮናርድ ኡለርን ፍላጎት አሳይቷል። በዚህ ደብዳቤ ላይ ዩለር አንድን ደንብ ሁለት ጊዜ ሳያልፉ በሁሉም ድልድዮች ላይ መራመድ ይቻል እንደሆነ ለመወሰን ቀላል የሆነውን ደንብ ማግኘት እንደቻለ ጽፏል (በኮኒግስበርግ ሰባት ድልድዮች ላይ ይህ የማይቻል ነው).

የአንድ ከተማ ክፍሎች ቀለል ባለ ሥዕል (ግራፍ) ፣ ድልድዮች ከመስመሮች (የግራፉ ጠርዞች) ጋር ይዛመዳሉ ፣ እና የከተማው ክፍሎች ከነጥቦች መገናኛ መስመሮች (የግራፍ ጫፎች) ጋር ይዛመዳሉ። በምክንያቱ ወቅት ዩለር ወደሚከተለው መደምደሚያ ደርሷል።

የግራፍ ያልተለመዱ ጫፎች ብዛት (ያልተለመደ የጠርዞች ብዛት የሚመራባቸው ጫፎች) ሁልጊዜም እኩል ነው። ያልተለመደ ቁጥር ያለው ግራፍ መሳል አይቻልም።

ሁሉም የግራፉ ጫፎች እኩል ከሆኑ እርሳስዎን ከወረቀት ላይ ሳያነሱ ግራፍ መሳል ይችላሉ እና ከየትኛውም የግራፍ ጫፍ ይጀምሩ እና በተመሳሳይ ጫፍ ላይ ይጨርሱት።

ከሁለት በላይ ጎዶሎ ጫፎች ያለው ግራፍ በአንድ ምት መሳል አይቻልም።

የኮንጊስበርግ ድልድዮች ግራፍ አራት ጎዶሎ ጫፎች ስለነበሯቸው ከሁለቱ አንዱን ሁለት ጊዜ ሳያልፉ በሁሉም ድልድዮች ላይ መሄድ አይቻልም።

ሩዝ. 3. የኮኒግስበርግ ድልድዮች ቀለል ያለ ንድፍ። የፊደላት እና የቁጥሮች ትርጉም - ምስል 2 ይመልከቱ - ስለ ጥንታዊው የኮንጊስበርግ ካርታ አስተያየት

ሩዝ. 4. የኮኒግስበርግ ድልድዮች ብዛት

በኡለር የተፈጠረው የግራፍ ንድፈ ሀሳብ በጣም ሰፊ መተግበሪያን አግኝቷል-ለምሳሌ ፣ በትራንስፖርት እና የግንኙነት ስርዓቶች ጥናት ውስጥ በተለይም በበይነመረብ ላይ መረጃን ለማዛወር ጥቅም ላይ ይውላል።

ባለአራት ቀለም ችግር- በ 1852 በ F. Gosri (በእንግሊዘኛ ፍራንሲስ ጉትሪ) የቀረበው የሂሳብ ችግር።

በአራት ቀለም ሉል ላይ የሚገኘውን ማንኛውንም ካርታ ቀለም መቀባት ይቻል እንደሆነ ይወቁ ስለዚህ የድንበሩ የጋራ ክፍል በቅስት መልክ ያላቸው ሁለት ክልሎች በተለያየ ቀለም ይሳሉ።

K. Appel እና W. Haken በ1976 ማንኛውም ካርታ በዚህ መንገድ መቀባት እንደሚቻል አረጋግጠዋል። ይህ በኮምፒውተር በመጠቀም የተረጋገጠ የመጀመሪያው ዋና የሂሳብ ቲዎሬ ነው። ምንም እንኳን ተከታይ ማቃለያዎች ቢኖሩም, ኮምፒዩተር ሳይጠቀሙ ማረጋገጫው ማረጋገጥ ፈጽሞ የማይቻል ነው.

የጂኦግራፊያዊ ካርታን ቀለም በሚቀቡበት ጊዜ በተቻለ መጠን ጥቂት ቀለሞችን መጠቀም ተፈጥሯዊ ነው, ነገር ግን የድንበሩ የጋራ ክፍል ያላቸው ሁለት አገሮች (የጋራ ነጥብ ብቻ ሳይሆን) የተለያየ ቀለም ያላቸው ናቸው. እ.ኤ.አ. በ 1852 ፍራንሲስ ጉትሪ የእንግሊዝ አውራጃዎችን ካርታ በሚስልበት ጊዜ ለዚህ ዓላማ አራት ቀለሞች በቂ መሆናቸውን አስተዋሉ ። ወንድሙ ፍሬድሪክ ይህንን ምልከታ ለታዋቂው የሒሳብ ሊቅ ኦ ዴሞርጋን ዘግቦ ለሂሳብ ማህበረሰብ ዘግቦታል። የመላምቱ ትክክለኛ አጻጻፍ የታተመው በኤ. ካይሊ (ኬይሊ፣ 1878) ነው።

የመጀመሪያው ማስረጃ ከአንድ አመት በኋላ ታየ እና የ V. Kempe ነው። ከአስራ አንድ አመት በኋላ ፒ.ሄውዉድ በውስጡ ስህተት አወቀ። የመጀመሪያው የተሳሳቱ ማስረጃዎች ብዙ ሌሎች ተከትለዋል. ከዚህ አንፃር የአራት ቀለም ችግር ከፌርማት ዝነኛ ችግር ቀጥሎ ሁለተኛ ነበር። እስከ 20ኛው መቶ ክፍለ ዘመን አጋማሽ ድረስ ምንም እንኳን ብዙ ድንቅ የሂሳብ ሊቃውንት በአራት ቀለማት ችግር ላይ ቢሰሩም የማስረጃው ሁኔታ ግን ቀላል በሆነ መልኩ ተቀየረ፡ የጄዲ ቢርክሆፍ ሃሳቦች ፒ. ፍራንክሊንን በ1913 ዓ.ም ፒ. 25 አገሮች. ይህ ቁጥር በኋላ ወደ 38 ከፍ ብሏል።

እ.ኤ.አ. በ 1977 የአራት ቀለም ግምታዊ ማረጋገጫ በመጨረሻ በ K. Appel እና U. Haken (አፕል, ሀከን) የተገኘ እና በሁለት ወረቀቶች ታትሟል. አብዛኛው የዕለት ተዕለት ሙከራ የተካሄደው በኮምፒዩተር ነው፣ እና ይህ አብዮታዊ ፈጠራ በተቋቋመው የዲዱክቲቭ ማመዛዘን በንጹህ ሒሳብ ልምምድ ውስጥ እስከ ዛሬ ድረስ ለዚህ ማረጋገጫ አንዳንድ ተፈጥሯዊ ጥርጣሬዎችን መሠረት ያደርገዋል። በመጀመሪያ ትክክለኛዎቹን ቀመሮች እንሰጣለን, ባለ አምስት ቀለም ንድፈ ሃሳብን እናረጋግጣለን እና አንዳንድ ተመሳሳይ ችግሮችን እንጠቁማለን.

በአለም እና በአውሮፕላን ላይ ካርታ ቀለም የመቀባት ችግሮች እኩል ናቸው. በእርግጥም, በአንድ ሉል ላይ ባለው ካርታ ላይ, የአገር ውስጥ የውስጥ ክፍል ቁራጭ ሊቆረጥ ይችላል; የተቦረቦረ ሉል ወደ ጠፍጣፋ ቦታ ሊበላሽ (ተዘረጋ) - ካርዱ ከቀጭን ጎማ የተሰራ እንደሆነ አስቡት። በጠፍጣፋ ካርታ ላይ, ጉድጓዱ ወደ "ውቅያኖስ" ይለወጣል, በሁሉም ጎኖች አንድ ሀገርን ያጥባል. እርግጥ ነው, የድንበሩ ርዝመት, ቅርጻቸው, የአገሮች መጠን ሲዘረጉ ከፍተኛ ለውጦችን ያደርጋሉ, ነገር ግን የድንበሩ ፍርግርግ ይቀራል, የተቆረጠው ጉድጓድ የተዘረጋው የተዘረጋው ድንበር ብቻ ነው, የውቅያኖስ ውጫዊ ድንበር ይሆናል. ታክሏል. ሊወገድ ይችላል, ማለትም, ውቅያኖስ በአካባቢው እንደ ሀገር በተመሳሳይ መልኩ ቀለም ሊኖረው ይችላል. እንደነዚህ ያሉት የአገሮች ለውጦች እና ድንበሮቻቸው የማቅለም ሥራን አይለውጡም። ከታች ጠፍጣፋ ካርታ ነው.

የፕላን ካርታ ቀለም ችግርን በፕላን ግራፎች ላይ በተመጣጣኝ ችግር በመተካት እንጀምራለን. የእያንዳንዱን ሀገር ዋና ከተማ እንመርጥ (ይህም በእያንዳንዱ ሀገር ውስጥ አንድ የውስጥ ነጥብ እንመርጣለን) እና የጋራ የድንበር ክፍል ያላቸውን የአገሮች ዋና ከተማዎች ከአርከስ ጋር እናገናኘዋለን። ውጤቱ ፕላነር ግራፍ ተብሎ የሚጠራው ነው.

ፍቺ 1. ግራፍ G ውሱን የቁመቶች ስብስብ V (G) እና የተወሰነ የጠርዝ ስብስብ R (G) ሲሆን እያንዳንዱ ጠርዝ በጫፎቹ ላይ ሁለት የተለያዩ ጫፎች አሉት። ግራፍ ጠፍጣፋ ተብሎ የሚጠራው ጫፎቹ የአውሮፕላን ነጥቦች ከሆኑ እና ጠርዞቹ የተሰበሩ መስመሮች (በክፍሎች የተዋቀሩ) በተመሳሳይ አውሮፕላን ውስጥ ከሆነ ነው ፣ ጫፎቻቸው ላይ የማይጣበቁ እና ከጫፎቻቸው በስተቀር ሌሎች ጫፎችን የማያካትቱ ከሆነ። .

በእቅድ ግራፍ ውስጥ loops (በተመሳሳይ ጫፍ የሚጀምሩ እና የሚጨርሱ ጠርዞች) እንደማይፈቀዱ ልብ ይበሉ።

የፕላነር ግራፍ አውሮፕላኑን ወደ ስብስብ D (G) ያልተደራረቡ ባለብዙ ጎንዮሽ ክልሎች ይቆርጠዋል, የግድ የተወሰነ አይደለም (ምስል 5).

ሩዝ. 5. 4-የፕላነር ግራፍ ቀለም

1, 2, ..., n ጥቅም ላይ የዋሉትን ቀለሞች እንደገና ከቆጠርን, በተዛማጅ ጠፍጣፋ ግራፍ ላይ ጫፎች / ካፒታል በእነዚህ ቁጥሮች ይቆጠራሉ.

ፍቺ 2. ትክክለኛ የፕላነር ግራፍ G n-coloring ካርታ ነው f: V(G) ® (1, 2, ..., n), f(u1) # f(u2) እንደዚህ ያለ ካለ ጠርዝ r k R (ጂ) ድንበሩ r u1 እና u2 ያካተተ ነው።

በመጨረሻም, ባለ አራት ቀለም ችግርን እንደ የሚከተለው መግለጫ ማዘጋጀት እንችላለን.

ቲዎረም 1. ማንኛውም የፕላነር ግራፍ መደበኛ ባለ 4-ቀለም ይቀበላል.

ለዚህ ችግር መፍትሄው ከመቶ አመት በላይ ፈጅቷል. ሆኖም ፣ በአንደኛው እይታ ፣ ስለ መደበኛ ባለ 5-ቀለም ትንሽ ደካማ መግለጫ ማረጋገጥ በጣም ቀላል ነው። ለማረጋገጥ የኡለር ፎርሙላ የቁመቶችን፣ ጠርዞችን እና ክልሎችን ቁጥር የሚያገናኝ ያስፈልግዎታል። እናድርግ | መ | የአንድ የተወሰነ ስብስብ አባላትን ብዛት ያሳያል M.

የኡለር ቲዎሪ. ለማንኛውም ፕላነር ግራፍ | ቪ(ጂ) | – | አር(ጂ) | + | ዲ(ጂ) | = 2.

ልብ በሉ የውጪውን ወሰን የሌለውን ክልል ግምት ውስጥ ካላስገባን የኡለር ቀመር የውሱን ፕላን ግራፍ ትሪያንግል ቅርፅ አለው | ቪ(ጂ) | – | አር(ጂ) | ++ | ዲ(ጂ) | = 1.

ቲዎረም 2. ማንኛውም የፕላነር ግራፍ መደበኛ ባለ 5-ቀለም ይቀበላል.

ማረጋገጫ። መጀመሪያ ግራፉን እናቀላል። የተወሰኑ ጥንድ ጫፎችን የሚያገናኙ ብዙ ጠርዞች ካሉ (ይህ ሁኔታ ሁለት አገሮች ብዙ ያልተገናኙ የድንበር ቁርጥራጮች ካሉ ፣ ለምሳሌ እንደ ሩሲያ እና ቻይና ያሉ) ካሉ ፣ ከዚያ አንድ ጠርዝ ብቻ እንተዋለን-የእንደዚህ ዓይነቱ የቀነሰ ትክክለኛ ቀለም። ግራፍ አሁንም ትክክለኛውን ቀለም ኦሪጅናል ዋስትና ይሰጣል።

አሁን በግራፉ ጫፎች ቁጥር ላይ ማነሳሳትን እናካሂድ. ሶስት ጫፎች ላለው ግራፍ፣ ቲዎሪው ግልጽ ነው። ከ n - 1 ጫፎች ጋር ለሁሉም ግራፎች እውነት ይሁን።

D1, D2, ..., Dm የግራፉ ሁሉ m = D (G) ክልሎች የተሟላ ይሁን እና N (ዲ) የ i-th ክልል ወሰን የሚይዙት የጠርዝ ብዛት ይሁኑ. ግራፍ. ከዚህም በላይ N(ዲ) ³ 3 ለማንኛውም i. ማንኛውም ጠርዝ በትክክል ሁለት ክልሎች ወሰን ውስጥ ነው, ስለዚህ

N(D1) + N(D2)+ ... +ኤን(ዲም) = 2R(ጂ)።

በN(Di) ³ 3 እኩል አለመመጣጠን ምክንያት

2R(G) = N(D1) + N(D2) + ... + N(ዲም) ³ 3ሜ = 3ዲ(ጂ)፣

ከዚያ 2R(ጂ) ³ 3D(ጂ)።

በኡለር ቀመር | ቪ(ጂ) | - 2 + | ዲ(ጂ) | = | አር(G) |፣ ከየት

3 | አር(ጂ) | = 3 | ቪ(ጂ) | - 6 + 3 | ዲ(ጂ) | £3 | ቪ(ጂ) | - 6 + 2 | አር(ጂ) |

እና ስለዚህ

| አር(ጂ) | £3 | ቪ(ጂ) | - 6.

በእጥፍ የተጨመሩት ጠርዞች ከሌላው የግራፍ ባህሪ ጋር ሊታወቁ እንደሚችሉ ልብ ይበሉ. a1፣ a2፣ ... ...፣ አንድ ሙሉ የግራፍ ቁመቶች n = V(G) ይሁን እና M(aj) በቬርቴክስ ቁጥር j ላይ የሚገናኙት የጠርዝ ብዛት ይሁኑ። ግን እያንዳንዱ ጠርዝ በሁለት ጫፎች ያበቃል, ስለዚህ

2R(G) = M(a1) + M(a2) + ... + M(an)።

በተጨማሪም ፣ ከእኩልነት (1) ፣ 2 | አር(ጂ) | £6 | ቪ(ጂ) | - 12. ስለዚህ.

M(a1) + M(a2) + ... + M(an) £ 6 | ቪ(ጂ) | - 12.

ከመጨረሻው እኩልነት አንፃር ከአምስት የማይበልጡ ጠርዞች የሚገጣጠሙበት ቢያንስ አንድ ጫፍ መኖሩን ማወቅ እንችላለን. በእርግጥ፣ ተቃራኒውን፣ ማለትም፣ “j M(aj) ³ 6. ከዚያም

M(a1) + M(a2) +... + M(an) ³ 6n = 6V(ጂ)፣

(2) የሚቃረን።

ከአምስት የማይበልጡ ጠርዞች በአንድ ቬርቴክስ a = an እንዳይሰበሰቡ ጫፎቹን እንደገና እንቆጥራቸው።

በ vertex a ላይ ከአራት የማይበልጡ ጠርዞች ካልተጣመሩ ግራፍ G \ aን ያስቡ ፣ ይህም ከጂ የሚገኘውን ወርድ aን በማስወገድ እና በውስጡ የሚያልቁ ጠርዞችን ያስቡ። ግራፉ G\a በማነሳሳት መላምት መደበኛ ባለ 5-ቀለም ይቀበላል። እና ጠርዞቹ የዚህን ትንሽ ግራፍ ቢበዛ አራት ጫፎች ያሉት ቬርቴክስን ስለሚያገናኙ፣ ለትክክለኛው ቀለም ቢያንስ አንድ ቀለም (ከአምስት) ይቀራል።

አሁን በትክክል አምስት ጠርዞች በ a. ከ ሀ የሚመጡትን ጫፎቹ እና የሚያገናኙት ጠርዞቹ (በG) የሚደርሱባቸውን አምስት ጫፎች ያቀፈውን ግራፍ H É Gን አስቡበት። በግራፍ H ውስጥ በጠርዝ ያልተገናኙ ሁለት ጫፎች መኖራቸውን እርግጠኛ ይሁኑ. በእርግጥ, አለበለዚያ ፒንታጎን H C 5 2 = 10 ጠርዞች ይኖረዋል (ይህ በቀጥታ ለማስላት አስቸጋሪ አይደለም). ሆኖም፣ በ (1) ምክንያት

| አር(ኤች) | £3| ቪ(ኤች) | - 6 = 3 " 5 - 6 = 9,

እና ወደ ተቃርኖ ደርሰናል።

B እና g እርስ በርሳቸው ያልተገናኙ የ H ጫፎች ይሁኑ። በG\a ውስጥም አልተገናኙም። ግራፍ G "ን አስቡበት, እሱም ከ G \ a የተገኘ ለውጥን በመጠቀም (አጣምሮ) b እና g. ግራፍ G "የእቅድ ግራፍ ነው, በዚህ ሁኔታ ውስጥ ጫፎችን ሲለዩ, loops ሊነሱ አይችሉም. ግን ለጂ "የኢንደክሽን መላምት ትክክለኛ ነው ፣ እና በውስጡ አንዳንድ መደበኛ ባለ 5-ቀለም j አለ ። በዚህ ባለ ቀለም ግራፍ ውስጥ ያሉትን ጫፎች b እና g እንለይ ። ከዚያ ግራፉ G \ a እንዲሁ መደበኛ ባለ 5-ቀለም ይቀበላል ፣ ያ j(b) = j (g) በሌላ አገላለጽ፣ b እና g በተመሳሳይ ቀለም የተቀቡ ናቸው እና፣ ስለዚህ፣ የግራፍ H አምስቱ ጫፎች ቀለም ቢበዛ አራት ቀለሞች ናቸው።

የተረፈውን ቀለም ቬርቴክስ aን ለማቅለም እና ትክክለኛ ባለ 5-ቀለም G ለማግኘት እንጠቀማለን።

የአራት ቀለሞች ችግር በመጀመሪያ እይታ ገለልተኛ ችግር ይመስላል, ከሌሎች የሂሳብ ቅርንጫፎች እና ተግባራዊ ችግሮች ጋር ብዙም ግንኙነት የለውም. በእውነቱ ይህ እውነት አይደለም. ይህን ችግር ከአልጀብራ፣ ከስታቲስቲክስ ሜካኒክስ እና ከዕቅድ ችግሮች ጋር የሚያገናኙት ከ20 በላይ ማሻሻያዎቹ ይታወቃሉ። እና ይህ ደግሞ የሒሳብ ባህሪ ነው፡ ከንጹህ የማወቅ ጉጉት የተነሳ ለተጠና ችግር መፍትሄው በተፈጥሮ ውስጥ ፍጹም የተለዩ እውነተኛ ነገሮችን እና ሂደቶችን በመግለጽ ጠቃሚ ይሆናል። እዚህ ከአራት-ቀለም ችግር ጋር የሚመጣጠን አንድ ችግርን እንመለከታለን.

እኔ፣ j እና k የ x፣ y እና z አስተባባሪ መጥረቢያዎች መደበኛ አሃድ አቅጣጫ ቬክተር ይሁኑ። ባለ ሶስት አቅጣጫዊ ቦታ፣ የቬክተር የቬክተር ምርት ይገለጻል፣ በምልክት i ይገለጻል። u, u k R3 ሁለት ቬክተሮች ከሆኑ የእነርሱ የቬክተር ምርት u i u ርዝመት አለው እና አቅጣጫው በጂምሌት ወይም በቀኝ እጅ ደንብ ይወሰናል. ይህ ምርት ተጓዳኝ አለመሆኑን ማረጋገጥ ቀላል ነው ፣ ማለትም ፣ ምርቱ u1 i u2 i ... i un በአጠቃላይ አነጋገር ፣ በውስጡ ምንም ቅንፎች ከሌሉ አልተገለጸም። በእርግጥ, ለምሳሌ, 0 = i i (j i j) (i i j) i j = - i. u1 i u2 i ... i un የሚለው አገላለጽ የተወሰነ ትርጉም እንዲኖረው፣ n - 2 ጥንድ ቅንፎች በትክክለኛው መንገድ መቀመጥ አለባቸው። በቅንፍ ያለው ይህ አገላለጽ ማህበር ይባላል።

ቲዎረም 3. u1 i u2 i ... i un ከሚለው አገላለጽ ጋር ለተያያዙ ለእያንዳንዱ ጥንድ ማህበራት እንደዚህ ያለ ምትክ (u1, u2, ..., un) (i, j, k) (ማለትም, (ማለትም) አለ. i, j, k) በሁሉም የዩኬ ምትክ በሆነ መንገድ ይተካሉ), ስለዚህ የማህበሩ እሴቶች እርስ በርስ እኩል እንዲሆኑ እና ከዜሮ የተለዩ ይሆናሉ.

መግለጫው የሚመለከተው ባለ ሶስት አቅጣጫዊ ቦታ ላይ ያሉ ቬክተሮችን ብቻ ነው እና ቀላል ይመስላል ነገር ግን እንደ ባለ 4-ቀለም ቲዎሪ ማረጋገጥ አስቸጋሪ ነው። የመጨረሻው ቲዎሪ ከአራት-ቀለም ችግር ጋር እኩልነት ያለው ማረጋገጫ በኤል.ኮፍማን ተሰጥቷል እና በቀላሉ ተብራርቷል. እዚህ በእነዚህ ተግባራት መካከል ያለውን ግንኙነት በአጭሩ ብቻ እናብራራለን.

በመጀመሪያ ፣ ግራፎች ከእሱ ጋር ምን ግንኙነት አላቸው? በግራፊክ, አንድ ማህበር እንደ ዛፍ ሊወከል ይችላል, ማለትም, እንደሚከተለው የተደረደሩ ልዩ የግራፍ አይነት. የማንኛውንም ጥንድ u i u ምርት ከቅርንጫፎቹ ጫፎች ጋር ተያያዥነት ያላቸው እና የምርቱ ጅምር ያላቸው ጥንድ ጫፎች (ቅርንጫፎች) ጋር ይዛመዳል። ደረጃ በደረጃ በማህበሩ ውስጥ የተደነገጉትን ድርጊቶች በቅንፍ በማካሄድ, በዚህ ዛፍ ሥር ላይ እንደርሳለን, ይህም በተሰጠው ማህበር ውስጥ ያሉትን ሁሉንም ብዜቶች ከማከናወን ውጤት ጋር ይዛመዳል. የበለስ አናት ላይ. ምስል 2 በማህበራቱ የተገለጹ ዛፎችን ያሳያል (u1 i u2) i (u3 i u4) (ታች, ቅርንጫፎች ወደ ላይ) እና (((u1 i u2) i u3) i u4) (ከላይ, ቅርንጫፎች ወደታች).

አሁን ሁለቱንም እነዚህን ዛፎች በቅርንጫፎቹ ጫፍ ላይ በማጣበቅ (ጫፎቹ ከማህበሩ ሁሉም ክፍሎች ጋር ይዛመዳሉ u1, u2, u3, u4) እና በመቀጠል የሁለቱም ዛፎች ሥሮች ከተጨማሪ ጠርዝ ጋር እናገናኛለን. ውጤቱ በስእል ግርጌ ላይ የሚታየው ጠፍጣፋ ግራፍ ነው. 6. የእንደዚህ አይነት ግራፍ ሁለት ልዩ ባህሪያትን እናስተውል-በትክክል ሶስት ጠርዞች በማናቸውም ጫፎች ላይ ይሰበሰባሉ (ይህ ንብረቱ የግራፍ ኩብ ይባላል). ማንኛውንም ጠርዝ ማስወገድ የግራፉን ወደ ሁለት የማይዛመዱ ክፍሎች መከፋፈልን አያመጣም (ይህን ንብረት የመለየት ጠርዝ አለመኖር ብለን እንጠራዋለን).

ሩዝ. 6. የፕላነር ግራፍ

ይህ ግንባታ ተመሳሳይ ቁጥር ያላቸውን ማኅበራት ጥንዶችን ያጠቃልላል።

በሁለተኛ ደረጃ, ማቅለም ከእሱ ጋር ምን ግንኙነት አለው? ቬክተሮች i፣ j እና k ለሁሉም የማህበሩ አካላት የተመደቡ ወይም ተመሳሳይ የሆነው ለዛፎች ተርሚናል ቅርንጫፎች የተሰጡ ሶስት ቀለሞች እንደሆኑ እንቆጥረዋለን። የቬክተር ምርትን ለማስላት በሚወጣው ደንብ መሰረት እስከ ሥሩ ድረስ የቀሩት ቅርንጫፎች ቀለም ይኖራቸዋል. ከስሌቶቹ በኋላ ዜሮ ያልሆነ ውጤት ለማግኘት ከፈለግን, ለመፈተሽ ቀላል እንደሆነ, በማንኛውም ጫፍ ላይ የሚገጣጠሙ ሶስት ጠርዞች በተለያየ ቀለም መቀባት አለባቸው.

ስለዚህ ሁለት የተለያዩ ዛፎችን በማጣመር የተገኘ ኪዩቢክ ፕላነር ግራፍ በማንኛውም ጫፍ ላይ ሶስት የተለያየ ቀለም ያላቸው ጠርዞች እንዲገጣጠሙ የጠርዝ ቀለም ይቀበላሉ. ይህ መደበኛ ባለ 3-ጫፍ ቀለም ተብሎ የሚጠራው ነው.

በሶስተኛ ደረጃ, የአራት ቀለሞች ችግር ከእሱ ጋር ምን ግንኙነት አለው? ነጥቡ ትክክለኛ ባለ 4-የጫፍ ቀለም እና ትክክለኛ ባለ 3-የጠርዝ ቀለም ችግሮች እኩል ናቸው። የበለጠ በትክክል ፣ ፍትሃዊ ነው።

ቲዎሬም 4. እያንዳንዱ ኪዩቢክ ግራፍ ጠርዞቹን ሳይለያዩ መደበኛ ባለ 3-የጠርዝ ቀለም ይቀበላል።

ይህ ቲዎሬም በመደበኛ ባለ 4-ቀለም ካርዶች ላይ ከቲዎረም 1 ጋር እኩል ነው። የእኩልነት ማረጋገጫው በጣም አስቸጋሪ አይደለም እና በአብዛኛዎቹ የግራፍ ቲዎሪ የመማሪያ መጽሐፍት ውስጥ ይገኛል።

የአንድ ኪዩቢክ ግራፍ ባለ 4 ቀለም እንዴት የጠርዙን ባለ 3 ቀለም እንደሚያመነጭ ብቻ እናብራራ። የአንድ ኪዩቢክ ግራፍ ክልሎች በአራት ቀለሞች ቀለም ይሁኑ. ቀለሞቹን እንደ 1፣ 2፣ 3 እና 4 ከመቁጠር ይልቅ በጥንድ (0፣ 0) (0፣ 1)፣ (1፣ 0) እና (1፣ 1) እንቆጥራቸው። የሚለያዩ ጠርዞች በሌሉበት, እያንዳንዱ ጠርዝ ከእሱ አጠገብ ሁለት የተለያዩ ክልሎች አሉት. በቀመር (i + k, j + l) (mod 2) መሰረት በ (i, j) እና (k, l) ቀለም ያላቸውን ቦታዎች የሚለየው ጠርዝ ላይ አንድ ቀለም እንመድበው. እዚህ n (mod 2) ማለት የ n ቀሪው በ 2 ይከፈላል. የተለያዩ ጥንድ የክልል ቀለሞች ሶስት ጥንድ (0, 1), (1, 0) እና (1, 1) ለጫፍ ማቅለሚያ ብቻ ያመነጫሉ.

የአፕል እና የሃከን ማረጋገጫ ምንም እንኳን በአጠቃላይ በሂሳብ ማህበረሰብ ዘንድ ተቀባይነት ያለው ቢሆንም አሁንም የተወሰነ ጥርጣሬን ይፈጥራል። ላይ ላዩን የሂሳብ እውቀት ላለው አንባቢ፣ የቀደመው ሀረግ መደነቅ አለበት፡- የተገለለው መካከለኛ መርህስ፣ ለሂሳብ ግዳጅ የሆነው፣ መግለጫው እውነት ነው ወይስ አይደለም? ይህን ያህል ቀላል አይደለም። የማስረጃው አዘጋጆች ራሳቸው የጻፉት የሚከተለው ነው፡- “አንባቢው 50 ገፆች የጽሑፍ እና የሥዕላዊ መግለጫዎች፣ 85 ገፆች ወደ 2,500 የሚጠጉ ተጨማሪ ሥዕላዊ መግለጫዎች፣ 400 ገፆች የማይክሮ ፋይች ተጨማሪ ሥዕላዊ መግለጫዎችን እና በሺዎች የሚቆጠሩ የተለያዩ መግለጫዎችን መፈተሽ አለባቸው። የዋናው ጽሑፍ 24 ሌማዎች በተጨማሪም አንባቢው "አንዳንድ እውነታዎችን መፈተሽ 1,200 ሰአታት የኮምፒዩተር ጊዜ እንደሚያስፈልግ ይማራል፣ በእጅ መፈተሽ ግን ብዙ የሚጠይቅ ነበር። በማንኛውም ዝርዝር ውስጥ አንብቤአቸዋል."

በግልጽ ለመናገር የኮምፒዩተር የማረጋገጫው ክፍል በእጅ ሊረጋገጥ አይችልም, እና ባህላዊው የማስረጃው ክፍል በጣም ረጅም እና ውስብስብ ስለሆነ ማንም ሙሉ በሙሉ ፈትሾ አያውቅም. ይህ በእንዲህ እንዳለ, የማይረጋገጥ ማስረጃ ከንቱ ነው. ከእንደዚህ ዓይነት ማስረጃዎች ጋር መስማማት ማለት ደራሲያንን በቀላሉ ማመን ማለት ነው። ግን እዚህም, ሁሉም ነገር የበለጠ የተወሳሰበ ነው.

በመጀመሪያ ወደ የኡለር ቀመር እና ባለ 5-ቀለም ቲዎሪ ማረጋገጫዎች እንመለስ። አንድ ወረቀት እና እርሳስ በመውሰድ ለማጣራት ቀላል ይመስላል. ነገር ግን ምክንያቱ ግልጽ በሆኑ ጉዳዮች ላይ የተመሰረተ ነው፡- “የእቅድ ግራፍ አውሮፕላኑን ወደ አንድ ስብስብ D(G) ያልተደራረቡ ባለብዙ ጎን ክልሎች። ይህ በእንዲህ እንዳለ፣ ይህ መግለጫ የአውሮፕላን ጂኦሜትሪ የአክሲዮሞች ቁጥር ወይም የት/ቤት ንድፈ ሃሳቦች አይደሉም፣ እና መረጋገጥ አለበት። በኬ ዮርዳኖስ የተቀመረው ተጓዳኝ ቲዎሪ ለማረጋገጥ በጣም ከባድ ነው ነገር ግን ዋናዎቹ ችግሮች እንደ “መቁረጥ” ያሉ ቃላትን እንዴት መረዳት እንዳለባቸው ጋር የተገናኙ ናቸው ፣ እነሱ በእውቀት በጣም ግልፅ ናቸው ፣ ግን መደበኛ ለማድረግ አስቸጋሪ። ከዚህ አስተያየት አንጻር፣ ባለ አምስት ቀለም ንድፈ ሃሳብ መረጋገጡን ወይም ስለ ጂኦሜትሪክ አኃዞች ባህሪያት በሚረዱ ሐሳቦች ላይ የተመሠረተ አሳማኝ ምክንያትን ማመን አለመሆኑ ሙሉ በሙሉ ግልጽ አይደለም።

ለረጂም ጊዜ የሒሳብ ጥብቅነት ተመራጭ የሆነው የዩክሊድ ቀመሮች እና ማረጋገጫዎች በተወሰኑ ሕጎች መሠረት ንድፈ ሃሳቦችን ከአክሲዮሞች ለማውጣት የሚያስችል መርሃ ግብር ተካሂዶ ነበር (አንድ ሰው ግልጽ ያልሆኑ መግለጫዎችን ከግልጽ መረጃ እንዲያገኝ የሚያስችል የመቀነስ ዘዴ በግልጽ የቀረቡት አንደኛ ደረጃ፣ በግልጽ ህጋዊ፣ ግምቶች)። ይህ የጥንካሬ ምሳሌ በት / ቤት ሒሳብ ውስጥ ዛሬም ሊደረስበት የማይችል ነው, ነገር ግን ለዘመናዊ ንጹህ ሂሳብ, የዩክሊድ ደረጃዎች በቂ አይደሉም. ኤውክሊድ፣ ቀጥተኛ መስመር ለምን አውሮፕላኑን ለሁለት እንደሚከፍለው አላሰበም (ይህ ምን ማለት ነው)፣ “በመካከል” የሚለውን ጽንሰ-ሐሳብ አልገለጸም ፣ ይህንን ፅንሰ-ሀሳብ ግልፅ አድርጎ ፣ ወዘተ. አብዛኛዎቹ ተጓዳኝ መግለጫዎች የተረጋገጡት ወይም የተካተቱት በጂኦሜትሪ axiomatics ውስጥ ባለፉት መቶ ዓመታት ብቻ ነው። ከአዲሱ የአክሲየም ስርዓት መደበኛ ተቀናሾች ከጥንት ጊዜ በጣም ረጅም ሆነዋል።

በዘመናዊ የሂሳብ አመክንዮ ደረጃዎች እና በጂኦሜትሪ አክሲየም ስርዓት መሠረት ባለ አምስት ቀለም ቲዎሬም ሙሉ በሙሉ የተገኘበትን ርዝመት መገመት እንኳን ከባድ ነው። ነገር ግን ማንም ሰው በዚህ መልመጃ ከንቱነት የተነሳ እንዲህ ዓይነቱን ምክንያት እንዳላደረገ በእርግጠኝነት እርግጠኛ ነው-መደበኛ መደምደሚያዎች በሰው ልጅ የስነ-ልቦና ባህሪዎች ምክንያት በትክክል ሊረጋገጡ የማይችሉ ናቸው-ከእነሱ በጣም ትልቅ ርዝመት በተጨማሪ (ከተለመደው አመክንዮ ጋር ሲነፃፀር) የንቃተ ህሊና ውህደት በጣም ቀርፋፋ ነው። ስለዚህ, በመደበኛነት በመርህ ደረጃ አንድ መደበኛ አመጣጥ ይቻላል በሚለው እምነት ረክተዋል.

ለምሳሌ የሂሳብ ሊቃውንት ስለ ኡለር ቀመር ጥርጣሬ የላቸውም። በአጠቃላይ ማስረጃን መቀበል የማህበራዊ ድርጊት አይነት ነው። የላቀ የአልጀብራስት ዩ.አይ. ማኒን "የተረጋገጠ እና ሊታወቅ የማይችል" በሚለው መጽሃፉ ውስጥ ስለዚህ ጉዳይ እንዲህ ሲል ጽፏል: "... በሂሳብ ስራዎች ውስጥ ስህተቶች አለመኖር (ያልተገኙ ከሆነ), እንደ ሌሎች የተፈጥሮ ሳይንሶች, ብዙውን ጊዜ በተዘዋዋሪ መረጃዎች የተመሰረቱ ናቸው: ዋናው ነገር መሟላት ነው. አጠቃላይ ግምቶች፣ በሌሎች ሥራዎች ላይ ተመሳሳይ ክርክሮችን መጠቀም፣ በአጉሊ መነጽር የተወሰኑ የማስረጃ ክፍሎችን መመልከት፣ የጸሐፊውን ስም እንኳን ሳይቀር፣ በአንድ ቃል፣ እንደገና መባዛት ሰፋ ባለ መልኩ።“ ግልጽ ያልሆነ” ማስረጃ በጣም ጠቃሚ ሚና ሊጫወት ይችላል። ለበለጠ ተደራሽ ምክንያት ፍለጋን በማነሳሳት"

የአራት-ቀለም ቲዎሬም ማረጋገጫ የሆነው ይህ በትክክል ነው. ብዙም ሳይቆይ, አዲስ ማረጋገጫ ታየ, እና በኮምፒዩተር ላይ ያልተሰራው ክፍል ቀድሞውኑ የተረጋገጠ ነው. ሆኖም የኮምፒዩተሩ ክፍል አሁንም የበለጠ የእምነት ጉዳይ ነው። ከሁሉም በላይ የሁሉም ፕሮግራሞች ህትመቶችን መፈተሽ እና ሁሉም የግብዓት መረጃዎች በዘፈቀደ ውድቀቶች ወይም በኤሌክትሮኒክስ ውስጥ የተደበቁ ጉድለቶች እንኳን ዋስትና ሊሰጡ አይችሉም (በመጀመሪያው የፔንቲየም ፕሮሰሰር ስሪት ውስጥ መከፋፈል ሲሰሩ ስህተቶች ንግዱ ከጀመረ ከስድስት ወራት በኋላ በድንገት እንደተገኙ ያስታውሱ። ሽያጮች - በነገራችን ላይ, በቁጥር ንድፈ ሃሳብ የሂሳብ ባለሙያ). የኮምፒዩተር ውጤቶችን ለመፈተሽ ብቸኛው መንገድ ለተለየ የኮምፒዩተር አይነት የተለየ ፕሮግራም መፃፍ ነው። ይህ እርግጥ ነው፣ ከመደበኛው የመቀነስ ምክንያታዊነት ፈጽሞ የተለየ ነው፣ ነገር ግን መግለጫዎች በሁሉም የሙከራ ሳይንሶች ውስጥ የሚሞከሩት በዚህ መንገድ ነው።

ከየትኛው ሒሳብ ነበር ስለዚህም በከንቱ የተገለለ።

2 ሒሳባዊ አመክንዮ እና ዓይነት ቲዎሪ

የሂሳብ ሎጂክ- ማስረጃዎችን የሚያጠና የሂሳብ ክፍል። እንደ P.S. Poretsky ፍቺ “የሒሳብ አመክንዮ እንደ ርዕሰ ጉዳዩ ሎጂክ ነው፣ ሂሳብ እንደ ዘዴው ነው።

የሒሳብ ዘዴዎችን በአመክንዮ መጠቀም የሚቻል የሚሆነው ፍርዶች በአንዳንድ ትክክለኛ ቋንቋ ሲቀረጹ ነው። እንደነዚህ ያሉት ትክክለኛ ቋንቋዎች ሁለት ገጽታዎች አሏቸው-አገባብ እና ትርጓሜ። አገባብ የቋንቋ ዕቃዎችን (ብዙውን ጊዜ ቀመሮች ተብለው የሚጠሩት) የሕጎች ስብስብ ነው። ሴማኒቲክስ ስለ ቀመሮች (ወይም አንዳንዶቹን) ግንዛቤያችንን የሚገልጽ እና አንዳንድ ቀመሮችን እውነት እና ሌሎችን እንድንመለከት የሚያስችለን የውል ስምምነቶች ስብስብ ነው።

የካልኩለስ ጽንሰ-ሐሳብ በሂሳብ ሎጂክ ውስጥ ትልቅ ሚና ይጫወታል. ካልኩለስ አንዳንድ ቀመሮች ሊመነጩ የሚችሉ ተደርገው እንዲቆጠሩ የሚያስችል የአስተሳሰብ ደንቦች ስብስብ ነው። የመግቢያ ደንቦች በሁለት ክፍሎች ይከፈላሉ. አንዳንዶቹ በቀጥታ አንዳንድ ቀመሮችን እንደ ተቀጣጣይ ያሟሉታል. እንደነዚህ ያሉት የማጣቀሻ ደንቦች አብዛኛውን ጊዜ አሲዮሞች ይባላሉ. ሌሎች ደግሞ ቀመሮቹን ሊመነጩ እንደሚችሉ እንድንገምት ያስችሉናል። ሀ, የውጽአት ቀመሮችን ስብስቦችን ለመጨረስ በአንዳንድ አስቀድሞ በተወሰነ መንገድ በአገባብ ይዛመዳል። በሰፊው ጥቅም ላይ የዋለው የሁለተኛው ዓይነት ህግ የሞዱስ ፖነንስ ህግ ነው፡ ቀመሮቹ ሊመነጩ የሚችሉ ከሆኑ ሀእና ፣ ከዚያ ቀመሩ እንዲሁ ሊቀንስ ይችላል። ለ .

የካልኩለስ ከትርጉም ጋር ያለው ግንኙነት የሚገለጸው በካልኩለስ የፍቺ ተስማሚነት እና የፍቺ ሙላት ጽንሰ-ሀሳቦች ነው። I ካልኩለስ I ለቋንቋው በትርጉም ደረጃ ተስማሚ ነው ተብሏል በ I ውስጥ ልወጣ የምችለው የቋንቋ ቀመር ትክክል ከሆነ። በተመሳሳይ፣ I ካልኩለስ እኔ በቋንቋ I ውስጥ ትክክለኛ ቀመር ካለ እኔ በቋንቋ በትርጉም የተሟላ ነው ተብሏል።

በሂሳብ አመክንዮ የሚታሰቡ ብዙዎቹ ቋንቋዎች በትርጉም የተሟሉ እና በትርጓሜ ጥቅም ላይ የሚውሉ ካልኩሊዎች አሏቸው። በተለይም የK.Gödel ውጤት ክላሲካል ተሳቢ ካልኩለስ ተብሎ የሚጠራው በትርጉም የተሟላ እና በትርጉም ደረጃ ለጥንታዊ የመጀመሪያ ደረጃ ተሳቢ አመክንዮ ቋንቋ ተስማሚ እንደሆነ ይታወቃል። በሌላ በኩል በትርጉም የተሟላ እና በትርጉም ተስማሚ የሆነ ስሌት መገንባት የማይቻልባቸው ብዙ ቋንቋዎች አሉ። በዚህ መስክ፣ ክላሲክ ውጤቱ የጎደል ያልተሟላ ንድፈ ሃሳብ ነው፣ እሱም በትርጉም የተሟላ እና በትርጉም ደረጃ ጥቅም ላይ የሚውል ካልኩለስ ለመደበኛ የሂሳብ ቋንቋ የማይቻል መሆኑን ያረጋግጣል።

ቲዎሪ ይተይቡ- በፕሮግራሚንግ ቋንቋዎች ፅንሰ-ሀሳብ (የኮምፒዩተር ሳይንስ ክፍል) ውስጥ የውሂብ አይነት ስርዓቶችን ለመንደፍ ፣ ለመተንተን እና ለማጥናት በሂሳብ መደበኛ መሠረት። ብዙ የፕሮግራም አድራጊዎች ይህንን ጽንሰ-ሐሳብ በፕሮግራሚንግ ቋንቋዎች ውስጥ ያሉትን ሥርዓቶች የሚተይቡበትን ማንኛውንም የትንታኔ ሥራ ለማመልከት ይጠቀማሉ። በሳይንሳዊ ክበቦች ውስጥ ንድፈ ሐሳብ ይተይቡብዙውን ጊዜ ጠባብ የሆነ ልዩ የሂሳብ ክፍልን በተለይም λ-calculusን ይረዱ።

የዘመናዊው ዓይነት ቲዎሪ በከፊል የራሰልን አያዎ (ፓራዶክስ) በመፍታት ሂደት ውስጥ የዳበረ ሲሆን በአብዛኛው በበርትራንድ ራስል እና በአልፍሬድ ኋይትሄድ "ፕሪንቺፒያ ማቲማቲካ" ስራ ላይ የተመሰረተ ነው (ይህ መሰረታዊ የሶስት-ጥራዝ የሂሳብ ሎጂክ ስራ በሩሲያኛ ገና አልታተመም)።

መደምደሚያ

የኮምፒዩተር ሳይንስ ቅድመ አያት ሳይበርኔቲክስ ነው፣ በአሜሪካዊው የሂሳብ ሊቅ ኖርበርት ዊነር የተመሰረተ፣ ተመሳሳይ ስም ያለው መጽሐፍ በ1948 ያሳተመ። የሞስኮ ስቴት ዩኒቨርሲቲ ፕሮፌሰር አሌክሲ አንድሬቪች ሊያፑኖቭ የሶቪየት የሳይበርኔትስ እና የኮምፒተር ሳይንስ ትምህርት ቤት መስራች በመባል ይታወቃሉ።

የኮምፒዩተር ሳይንስን ውስብስብነት ለማመልከት "ኢንፎርማቲክስ" የሚለው ቃል በ 1976 በአካዳሚክ አንድሬ ፔትሮቪች ኤርሾቭ ወደ ሩሲያ ቋንቋ መዝገበ ቃላት ገባ።

ምንም እንኳን "የኮምፒዩተር ሳይንስ" የሚለው ቃል በሰፊው ጥቅም ላይ ቢውልም, ባለሙያዎች አሁንም በትርጉሙ ላይ መግባባት የላቸውም. ሶስት መንገዶች አሉ፡-

እጅግ በጣም ሰፊ ፣ በኮምፒዩተር ሳይንስ ውስጥ ከማንኛውም መረጃ የመቀበል ፣ የመቀየር እና የማስተላለፍ ሂደቶች ጋር የተቆራኙትን ሁሉንም ነገሮች ጨምሮ ፣

ሰፊ, በኮምፒዩተር ሳይንስ ውስጥ ከኮምፒዩተር ጋር የተያያዙ ሁሉንም ነገሮች ጨምሮ, የኮምፒተር መሳሪያዎችን የመንደፍ ጉዳዮችን ጨምሮ;

ጠባብ ፣ የኮምፒዩተር ሳይንስን እንደ ኮምፒዩተሮች አጠቃቀም ሳይንስ ፣ ማለትም ፣ እንደ ኮምፒዩተር ቴክኖሎጂ ሳይንስ ብቻ ይገልፃል።

ስለዚህ, እስከዛሬ ድረስ "የኮምፒውተር ሳይንስ" የሚለው ቃል ሦስት ትርጓሜዎች አሉ.

የመጀመሪያው እጅግ በጣም ሰፊ ሲሆን በውስጡም የኮምፒዩተር አጠቃቀም ምንም ይሁን ምን የግዛቱ ወሰን አጠቃላይ የሳይንስ ውስብስብ የሆነውን አንድ መንገድ ወይም ሌላ መረጃን ከማግኘት እና ከማቀናበር ጋር የተያያዘ ነው። በዚህ ትርጉም፣ ቃሉ ብዙ ጊዜ በፍልስፍና እና ዘዴያዊ ህትመቶች፣ እንዲሁም ሙያዊ ባልሆኑ ክበቦች (ጋዜጠኞች፣ ፖለቲከኞች) ውስጥ ጥቅም ላይ ይውላል።

ሁለተኛው የኮምፒዩተር ሳይንስ እንደ ሙሉ የኮምፒዩተር ሳይንስ ስብስብ ነው, ትክክለኛው የኮምፒዩተር ሳይንስ እኩል ነው. በዚህ ትርጉም ውስጥ፣ ቃሉ የተለያዩ የፕሮግራም አወጣጥን እና ኮምፒውተሮችን በመጠቀም፣ የንድፍ እና የሶፍትዌር እድገታቸው ዘዴዎችን ያጣምራል። ይህ አተረጓጎም ብዙውን ጊዜ በተለመደው ሙያዊ ቋንቋ እና ወደ እንግሊዘኛ ተተርጉሟል። ለምሳሌ “የኮምፒዩተር ሳይንስ ፋኩልቲ” በጣም በትክክል እንደ “የኮምፒዩተር ሳይንስ ፋኩልቲ” ወይም “የኮምፒዩተር ሳይንስ ክፍል” ተብሎ ተተርጉሟል፣ ይህም ለትርጉሙ እንደታሰበው ታዳሚዎች ላይ በመመስረት (በብሪቲሽ እንግሊዝኛ “ፋኩልቲ” የሚለው ቃል የበለጠ የተለመደ ነው እና በአሜሪካ እንግሊዝኛ “ክፍል”) .

ሦስተኛው የኮምፒዩተር ሳይንስ በጠባቡ አነጋገር የኮምፒዩተር (ሃርድዌር) ዝርዝር ጉዳዮች ከኮምፒዩተር ሳይንስ ወሰን በላይ ሲወሰዱ እና የመተግበሪያቸው ችግሮች በሳይንስ ውስጥ ይቀራሉ። በዚህ ትርጉም ቃሉ ብዙውን ጊዜ በከፍተኛ ሙያዊ የፕሮግራም አውጪዎች አካባቢ እንዲሁም በትምህርት ፕሮግራሞች ውስጥ ጥቅም ላይ ይውላል። በአጠቃላይ በትምህርት አካባቢ "ኢንፎርማቲክስ እና የኮምፒተር ቴክኖሎጂ" በሚለው ሐረግ ውስጥ በትክክል መረዳት ያለበት ይህ ነው, አለበለዚያ ውጤቱ አመክንዮአዊ ስህተት ነው.

እንደምታውቁት, ማንኛውም ምደባ ሁኔታዊ እና የተወሰነ ዓላማ አለው. ከላይ ከተዘረዘሩት ሁሉ አንፃር እኛ በኮምፒዩተር ሳይንስ መስክ ልዩ ባለሙያዎችን ማሰልጠን ግምት ውስጥ በማስገባት የቅርብ ጊዜውን ፣ ጠባብ ትርጓሜን እንጠቀማለን እና የኮምፒተር ሳይንስን እንደ ሳይንሳዊ ዲሲፕሊን እንገልፃለን ፣ ርዕሰ ጉዳዩ የኮምፒዩተር ቴክኖሎጂ ነው። “ኮምፒዩተር” ከሚለው ቃል ይልቅ “አዲስ መረጃ” ወይም በቀላሉ “መረጃ” ከሚለው ትርጉም ጋር ተመሳሳይ የሆኑ ፍቺዎች ብዙውን ጊዜ ጥቅም ላይ ይውላሉ ፣ ስለሆነም በልዩ ሥነ ጽሑፍ ውስጥ “የአይቲ አገልግሎት” ፣ “የአይቲ ስፔሻሊስት” ፣ “የአይቲ ፋኩልቲ” የሚሉትን ቃላት ማግኘት ይችላሉ ። ወዘተ.

በሳይበርኔትስ፣ በኮምፒውተር ቴክኖሎጂ እና በኮምፒውተር ሳይንስ መካከል ያለውን ድንበር ለማሳየት የሚከተለውን ምሳሌያዊ ንጽጽር መጠቀም እንችላለን። አልጎሪዝም የሚያዘጋጀውን ሳይበርኔቲሺያን ሙዚቃን ከሚሰራ የሙዚቃ አቀናባሪ፣ የኮምፒዩተር ዲዛይነርን ከቫዮሊን ሰሪ ጋር ብናነፃፅር የኮምፒዩተር ሳይንቲስት የአቀናባሪውን እቅድ ከተገነዘበ እና በችሎታው እና በችሎታው ከበለፀገ ቫዮሊስት ጋር ሊወዳደር ይችላል። ስለዚህ የኮምፒዩተር ሳይንስ የእውቀት ዘርፍ ብቻ ሳይሆን የማይከፋፈል የእጅ ጥበብ፣ ሳይንስ እና ጥበብ ውህደት ነው።

በ 20 ኛው ክፍለ ዘመን ሁለተኛ አጋማሽ ላይ የኮምፒዩተር ሳይንስ ብቅ ማለት ድንገተኛ አይደለም. ኮምፒተር እና ቴሌኮሙኒኬሽን በሰው ልጅ ታሪክ ውስጥ ከኢንዱስትሪ ወደ ድህረ-ኢንዱስትሪ (መረጃ) ዘመን ሽግግርን የሚያመለክቱ የመረጃ አብዮት ሁለት አመክንዮአዊ ምርቶች እና መሳሪያዎች ናቸው።

ያገለገሉ ጽሑፎች ዝርዝር

1. አፖኪን I. A., Maistrov L. E. የኮምፒዩተር ቴክኖሎጂ ታሪክ: በጣም ቀላል ከሆኑ የመቁጠሪያ መሳሪያዎች እስከ ውስብስብ ቅብብሎሽ ስርዓቶች. መ: ኑካ, 2000.

2. ግላድኪህ ቢ.ኤ. ከአባከስ ወደ ኮምፒዩተር። Tomsk: NTL ማተሚያ ቤት, 2005.

3. ጉተር አር.ኤስ., ፖሉኖቭ ዩ.ኤል. ከአባከስ ወደ ኮምፒተር. ኤም: እውቀት, 2001.

4. Cook D., Baze G. የኮምፒውተር ሒሳብ. ኤም. ፣ ናውካ ፣ 2000

5. ማርኮቭ ኤ.ኤ. የሂሳብ ሎጂክ አካላት። ኤም.: የሞስኮ ስቴት ዩኒቨርሲቲ ማተሚያ ቤት, 2004.

6. ፖሊያ ዲ. የሂሳብ ግኝት. መ: ኑካ, 2000.

7. ፕሪሉትስኪ ኤም.ኬ. የኮምፒተር ሳይንስ የሂሳብ መሠረቶች። ኒዝሂ ኖቭጎሮድ፡ ኒዝሂ ኖቭጎሮድ ስቴት ዩኒቨርሲቲ፣ 2000 ዓ.ም.

8. ሲሞኖቪች ኤስ., ኤቭሴቭ ጂ., አሌክሼቭ ኤ. አጠቃላይ ኢንፎርማቲክስ. ኤም.፡ ዴሎ፣ 1999

9. Turetsky V.Ya. የሂሳብ እና የኮምፒውተር ሳይንስ. ኢካተሪንበርግ፡ ፕሮፓጋንዳ፣ 2002

10. Faure R., Kofman A., Denis-Papin M. ዘመናዊ ሂሳብ. መ: ሚር, 2006.

11. Chastikov A. የኮምፒዩተር ዓለም አርክቴክቶች. ሴንት ፒተርስበርግ፡ BHV-Petersburg, 2002.

12. Shenfield J. የሂሳብ ሎጂክ. ኤም: ናኡካ, 2005.

ፕሪሉትስኪ ኤም.ኬ. የኮምፒተር ሳይንስ የሂሳብ መሠረቶች። ኒዝሂ ኖቭጎሮድ፡ ኒዝሂ ኖቭጎሮድ ስቴት ዩኒቨርሲቲ፣ 2000. ፒ. 21.

በአልጎሪዝም ፅንሰ-ሀሳብ ፣ NP-የተሟሉ ችግሮች በ NP ክፍል ውስጥ ያሉ የችግሮች ክፍል ናቸው (ይህም ፈጣን የመፍትሄ ስልተ ቀመሮች ገና አልተገኙም ፣ ግን የተሰጠው መፍትሄ ትክክል መሆኑን ማረጋገጥ ፈጣን ነው) ፣ ሁሉም የ NP ክፍል ችግሮች ይቀንሳሉ. ይህ ማለት ማንኛውንም የ NP-የተሟሉ ችግሮችን ለመፍታት ፈጣን ስልተ-ቀመር ከተገኘ, በ NP ክፍል ውስጥ ያለ ማንኛውም ችግር በፍጥነት ሊፈታ ይችላል.

ወደ ማታለል ካልወሰዱ, ወደ ውሃው ይዝለሉ እና ወደ ተቃራኒው የባህር ዳርቻ ይዋኙ, ይህም ችግሩን በድልድዮች ለመፍታት ያስችልዎታል, ግን በሚያሳዝን ሁኔታ, የችግሩን ሁኔታ በግራፍ ይለውጠዋል ...

ይሁን እንጂ ሄውዉድ አምስት ቀለሞች በእርግጥ በቂ መሆናቸውን ከማስረጃው ተረድቷል። ሆኖም ግን, ለማንኛውም ካርድ አራት ቀለሞች በቂ ነበሩ!

ማርኮቭ ኤ.ኤ. የሂሳብ ሎጂክ አካላት። ኤም.: የሞስኮ ስቴት ዩኒቨርሲቲ ማተሚያ ቤት, 2004. ፒ. 211.

ኩክ D.፣ Baze G. የኮምፒውተር ሂሳብ። M., Nauka, 2000. P. 156.

Turetsky V.Ya. የሂሳብ እና የኮምፒውተር ሳይንስ. Ekaterinburg: ፕሮፓጋንዳ, 2002. P. 109.

ሲሞኖቪች ኤስ., ኤቭሴቭ ጂ., አሌክሼቭ ኤ. አጠቃላይ ኢንፎርማቲክስ. ኤም: ዴሎ, 1999. ፒ. 231.

ግላድኪክ ቢ.ኤ. ከአባከስ ወደ ኮምፒውተር። Tomsk: NTL ማተሚያ ቤት, 2005. P. 87.