«алгоритмдер жшне деректер љ°рылымы» пшнін ољыту-шдістемелік кешен

Келесі ›асиеттері бар графтарды а“аштар дейді:

- Бас›а ешбір элемент сілтемейтін жал“ыз элементі (тЇйін, тйбе) бар болса жЩне ол тЇбір деп аталады.

- ТЇбірден бастап элементтерде бар белгілі бір кйрсеткіштер тізбегі бойымен структураныЈ бас›а кез келген элементіне ›атынас жасау“а болса.

- ТЇбірден бас›а Щрбір элементке тек бір “ана сілтеме жасалса, я“ни Щрбір элементтіЈ жал“ыз адресі болса.

Ба“дарлы а“аш деп тЇбір деп аталатын бір тйбесі бар, кіріс жартыдЩрежесі нйлге теЈ, бас›а кіріс жартыдЩрежелері 1-ге теЈ болатын циклдік графты айтады. Б±л а“аштардыЈ еЈ болма“анда бір тйбесі бар болады. Аластатыл“ан, дара тйбе де ба“дарлы а“аш деп аталады.

Шы“ыс жартыдЩрежесі нйлге теЈ ба“дарлы а“аштыЈ тйбесі ілінген, соЈ“ы тйбе деп аталады. Одан бас›а тйбелері тарма›талу тйбелері деп аталады. ТЇбірден Щлдебір тйбеге дейінгі жолдыЈ ±зынды“ы осы тйбеніЈ деЈгейі - немесе ярус номері деп аталады. ТЇбір деЈгейі нйлге теЈ болады, ал бас›а тйбелердіЈ деЈгейлері тЇбір мен тйбелердіЈ арасында“ы ±зынды›пен аны›талады, немесе тйбелер деЈгейлерініЈ номерлерініЈ модулі бойынша айырмасына теЈ.

Бинарлы а“аштар.

m - арлы а“аштар бар, олар Щрбір тйбелердіЈ шы“ыс жартыдЩрежесі m-нен кіші не теЈ болатын а“аштар. m=0,1,2,3,... Егер Щрбір тйбеніЈ“ шы“ыс жартыдЩрежесі m-ге немесе нйлге теЈ болса, оны толы› а“аш немесе m - арлы а“аш дейді.

m=2 бол“анда а“аштарды бинарлы немесе толы› бинарлы дейді.

Кез келген а“ашты, то“айларды бинарлы а“ашпен кйрсету.

1. Шрбір тЇйінде Їлкен ±л“а (вертикальды жал“ау) тек бір “ана б±та› ›алдыру.

2. Горизонтальды ›абыр“алармен бір Щкелі барлы› бауырларды жал“астыру.

3. Сонда мына ережемен а“аш ›айта ›±рылады: сол жа›та“ы ±л - берілген тйбеніЈ астында орналас›ан тйбе, оЈ жа› ±л - берілген тйбеніЈ оЈ жа“ында орналас›ан тйбе, я“ни яруста орналас›ан тйбе.

4. А“ашты вертикальды б±та›тары сол жа›та“ы ±лдарды, горизонтальды б±та›тары оЈ жа›та“ы ±лдарды кйрсететіндей етіп тйЈкеру.

НЩтижесінде кез келген а“ашты бинарлы а“аш›а алмастыр“анда тЇбірлі тйбеге ілінген сол жа›та“ы ішкі а“аш тЇріндегі а“аш алынады.

Баланстал“ан а“аш. Бинарлы а“ашта іздеу операциясын жылдамдату“а кймектеседі. Балансты а“аш деп Щрбір тЇйін Їшін оныЈ екі ішкі а“ашыныЈ биіктігініЈ айырмашылы“ы біреу болса “ана айтады.

изін тексеру с±ра›тары

1. 
   Графтар ›айда ›олданылады?
   
2. 
   Б±та› деген не?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

Дискілік жадыныЈ физикалы› структурасы

Тізбекті файлдар

Сырт›ы с±рыптау

Бйлімдермен ±йымдастырыл“ан файлдар
Дискілік жадыныЈ оперативті жады“а ›ара“анда ›±рылысы да, а›паратты ›олдануы да бас›аша. љатты магнитті дискілерде жина›та“ыш екі жа“ынан да ферромагнитті материалмен ›аптал“ан, бірнеше ішкі дискілердіЈ жиынты“ынан т±рады.Жазу-о›у механизмі дискілер арасынна кірістірілетін тісше, тара›ша сия›ты.

Тізбектелген файлдар.

Сырт›ы жадыда“ы файлды› структураныЈ ›арапайым тЇрініЈ бірі реттелмеген тізбектелген файлдар. М±нда іздеу операциясы сызы›ты тЇрде жЇргізіледі.

Сырт›ы с±рыптау. Сырт›ы жадыда деректерді с±рыптау 2 этаптан т±рады:

1. бйлшектеп с±рыптау

2. жымдастыру

Бірінші этапта с±рыпталатын тізбек бірнеше кішкене бйлшектерге бйлініп барып, Щр›айсысы с±рыпталады, ал екінші этапта Щрбір с±рыптал“ан бйлшектер бір бірімен жымдастырылады.

Бйлімдермен ±йымдастырыл“ан файлдар. Кез келген ретпен файл“а бйлінген жадыда орналастырыл“ан бірнеше ішкі файлдар“а бйлінген тізбекті айтады. Шрбір ішкі файлдыЈ йзініЈ атауы, Щр бйлігініЈ атауы болады, бЩра› операциялы› жЇйе бір бйлімге жататын ішкі файлдарды бір файл тЇрінде ›арастырады.

Структуралы-кітапханалы› файл 3 бйліктен т±рады: аны›тама бйлімі, та›ырып, деректер бйлімі. Аны›тама бйлігінде файл параметрлері жазылады: та›ырыптыЈ йлшемі, деректер бйліміндегі бос кеЈістіктіЈ басталу адресі. Та›ырып Щр жолы бір бйлімнен т±ратын таблица іспеттес. Шр бйлім Їшін бйлім атауы, деректер облысында“ы бйлім адресі, бйлім ±зынды“ы беріледі.

изін тексеру с±ра›тары

2. Тізбекті файлдар деген не?

3. Сырт›ы с±рыптауды ›алай ±“асыз?

°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   Программа. Программа тЇрлері.
   
2. 
   Программалау тілдері.
   
3. 
   Программалау Щдістері.
   

1. 
   аппаратты› жабды›ты бас›ару
   
2. 
   компьютердіЈ ›олданушымен байланысын орнату
   
3. 
   ›олданушыныЈ мЩселелерін шешу
   
4. 
   а›паратты йЈдеу
   

1. 
   базалы› деЈгейдегі программалар тобы –БИОС деп аталатын компьютердіЈ ішкі кЇйлерін бас›аруды ›ада“алайтын программалар.
   
2. 
   системалы› деЈгейдегі программалар тобы – программалар арасында“ы байланысты орнатып, посредник ›ызметін ат›аратын программалар, олар 1-ші жЩне 3-ші программалар тобын біріктіреді, олар“а сЇйеу болады жЩне сЇйеніш бола алады.
   
3. 
   ›ызметшілік деЈгейдегі программалар тобы – компьютер жЇйесін автоматтандыру, тексеру, белгілі бір кЇйге келтіруді орындайтын программалар.
   
4. 
   ›олданбалы деЈгейдегі программалар тобы – белгілі бір сала“а байланысты мЩселелерді шешуге ›олданылатын программалар.
   

Интерфейс типтері:

1. 
   ›олданушы интерфейсі – графикалы›, графикалы› емес деп бйлінеді. (толы› экранды, кйрнекі, диалогты, т.б.)
   
2. 
   аппараты – программалы› интерфейс – арасында байланыс орнатушы программа
   
3. 
   программалы› интерфейс - ЩртЇрлі программалар арасында“ы байланыс орнатушы программа
   

Системалы› программалар. ОлардыЈ тЇрлері.

1. 
   Драйверлер
   
2. 
   љабы›ша – программалар
   
3. 
   Операциялы› ›абы›шалар
   
4. 
   Утилиттар
   
5. 
   Желілік программалар
   

1. 
   Архиваторлар (rar, zip, arj)
   
2. 
   антивирустік программалар (Kaspersky antivirus, Drweb, Antiviral)
   
3. 
   коммуникациялы› программалар (BlookLin Bridge, DeskLink, Laplink, Telemate, BitFax, FaxIT)
   
4. 
   диагностикалаушы программалар (Norton Utilites, CheckIT, Calibrate, ControlRoom)
   
5. 
   жадыны бас›ару програмалары (SmartDrive, Ncashe, SuperPC)
   
6. 
   дискіні динамикалы› ›ысу программалары (Stacker, DoubleSpace, SuperStar)
   

Жазыл“ан программаны тЇсінуі жЩне орындауы Їшін программист те компьютер де келесі тілдерді білуі ›ажет:

1. 
   Машиналы› код тілі - компьютерге тЇсінікті екідік, жЩне 16-› кодтал“ан символдардан ›±рал“ан кодтар тізбегі;
   
2. 
   Программалау тілі – программистке тЇсінікті бірлігі – командалар тізбегі, тіл табысу деЈгейі – мЩтін болатын тіл.
   
3. 
   Бейнелер тілі – ›олданушы“а тЇсінікті мЩтін, графика тЇріндегі тіл.
   

Програмалау тілдері машиналы› командалар“а жа›ынды“ы мен алысты“ына ›арай екі топ›а бйлінеді:

1. 
   Тйменгі деЈгейлі тілдер;
   
2. 
   Жо“ар“ы деЈгейдегі тілдер;
   

Жо“ар“ы деЈгейдегі тілдер 7 тЇрге бйлінеді:

1. 
   Сызы›ты – б±л тілдерде жазыл“ан командалар тізбектеліп орындалады, процедура, функция деген тЇсініктер жо›. Олар элементарлы математикалы› есептеулер жЇргізуге арнал“ан. Олар 1949 жылдары ›олданыл“ан «Краткий код» тілі деп атал“ан.
   
2. 
   Процедуралы› – модульдік программалау принципіне негізделіп ›±рал“ан тіл, б±л тілде берілген мЩселе бірнеше модульдар“а бйлініп, сол модульдарды ›ажетті кезінде “ана ша›ырып ›олдану Їшін жасал“ан. О“ан 1954 жылдары пайда бол“ан Фортран тілін жат›ызу“а болады. Кейіннен 1957 жылы – Cobol, Lisp(1958), Algol(1958), APL(1960), Basic(1964), Pascal(1967), C(1972) тілдері пайда болды. Б±л тілдердіЈ жетістіктері:
   

1. 
   кішкентай модульді жазу оЈай;
   
2. 
   жалпы жа“дайлар“а ›±рыл“ан модульдарды бірнеше рет ›олдану“а болады, сол ар›ылы жаЈа программаны ›±ру“а уа›ыт аз кетеді;
   
3. 
   модульдыЈ ж±мысын негізгі программа“а тЩуелсіз тексеруге, орындау“а болады.
   

1. 
   Логикалы› – формальды логика мен буль алгебрасы жЇйелерін ›±ру принципіне негізделген. Б±л тілдер жасанды интеллект жасау“а ›атысады. О“ан жататындар Prolog(1970), KLO, Mandala, Mercury тілдері.
   
2. 
   Нысанды ба“ыттал“ан – объектілер тЇріндегі берілген кодты тарататын айнымалыларды, процедураларды, функцияларды класстар“а біріктіру негізінде ›±рыл“ан. Б±л тілдерді де модульды программалау“а жат›ызу“а болады. Б±л тілдерді барлы› салаларды автоматтандыру ж±мысына араластыру“а болады. О“ан жататындар (1986) С++, Lava, C#, Delphi, Visual Basic тілдері.
   
3. 
   Деректер базасына с±раныстар ›±ру тілі – белгілі бір таблица тЇрінде жина›тал“ан деректер базасынан бас›а, жаЈа, ›ажетті жазуларды топтайтын таблица ›±руды орындау“а арнал“ан. О“ан жататындар SQL тілі немесе Pl/SQL тілдері.
   
4. 
   Сценарийлер тілі – Web-сайттар, ›осымшалар жасау“а, HTML-›±жат›а орнатыл“ан программалар ›±ру“а арнал“ан. Олар“а жататындар Visual Basic Script, Visual Studio Net, Asp.net, JavaScript, Perl, PHP тілдері.
   
5. 
   Макростар тілі – жиі ›олданылатын операцияларды автоматтандыру“а арнал“ан тілдер. Макрос дегеніміз бір команда сия›ты орындалатын н±с›аулар жиынты“ы. ОлардыЈ негізгі ›ызметі:
   

1. 
   жиі ›олданылатын командаларды жылдамдатуды ›амтамасыз ету;
   
2. 
   бірнеше жиі ›олданылатын командаларды біріктіру;
   
3. 
   ЩртЇрлі мЩселелерде тізбектеліп орындалатын кЇрделі Щрекеттерді автоматтандыру.
   

изін тексеру с±ра›тары

1. 
   Программа деген не?
   
2. 
   ПрограмманыЈ ›андай тЇрлері бар?
   
3. 
   Программалау тілдерініЈ ›андай тЇрлері бар?
   

°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

• 
  Структуралы программалау
  
• 
  Модульдік программалау
  

1. 
   Экран ›алпы
   
2. 
   Программалы› модуль
   
3. 
   Программалы› жобалау
   

љолданушы программамен ж±мыс істеу барысында элементтер та›тасы кйрініп т±рады. Visual Basic –тіЈ негізгі экранды› меню жолы мыналардан т±рады:

1. 
   ЖЇйелік меню белгісі
   
2. 
   Саймандар панелі
   
3. 
   Меню жолы
   
4. 
   Form (›алып)терезесі
   
5. 
   Form терезесініЈ йлшемдері
   

1. 
   Структуралы программалау деген не?
   
2. 
   Модульдік программалау деген не?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

• 
  КЇрделі есептеулер алгоритмдері.
  
• 
  КйпмЇшеліктерді есептеу
  
• 
  Аргументті сызы›ты алмастыру ар›ылы кйпмЇшелікті есептеу
  

Горнер схемасы б±л кйпмЇшеліктегі кйбейту жЩне ›осу амалдарыныЈ санын максималды азайтады.

n=2 болсын, сонда кйпмЇшелік былай жазылады:

y= a₀x²₊a₁x¹+a₂ -> 3кйбейту, 2 ›осу амалдары бар б±л йрнекті былай жазу“а болады:

y= (a₀x²₊a₁)x+a₂ -> 2 кйбейту, 2 ›осу амалы болды.

n=3 болсын:

y= a₀x³₊a₁x²+a₂x+a₃ – 9 амал бар

y= ((a₀x₊a₁)x+a₂)x+a₃ – 6 амал бар. Сонда б±л Щдіс алгоритмі 2 операциядан т±рады:

1. 
   x-ке кйбейту
   
2. 
   келесі коэффициентті ›осу
   

арг n, x, a

нет y

басы бЇт i

i:=0

Щзір i

›. б.

i:=i+1

Мысалы:

т/к

Мысалы: 10 депутаттыЈ 5 – уін таЈдау Щдісі ›анша?

i=10-5+1=6 дан i=10 дейін i – ді кйбейту.

1.a,b,c[i] енгіз

2. d₀ – ді табамыз:

I-этап

3. d_1,d₂ – ні табамыз:

Шйтпесе ц.с

1. Есептеудегі тиімділікті ›алай ±“асыз? Мысалдар келтіріЈіз.

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

Тапсырмалар:

1. 
   КонустыЈ бЇйір бетініЈ ауданын есептеу формуласыныЈ алгоритмін ›±ру. Есепте конустыЈ табаныныЈ диаметрі, жасаушысы берілген.
   
2. 
   жЩне арифметикалы› йрнектерді шы“ару алгоритмін ›±ру.
   
3. 
   Y=1+xcos²(x)+sin³(x) функциясыныЈ мЩнін есептеу, м±нда“ы x=2.346. Алын“ан нЩтижені квадраттау жЩне абсолют шамасын аны›тау.
   
4. 
   М(-0,8; 0,9)координатты нЇкте берілген. Осы нЇктеніЈ координаттарынан тЩуелді, егер нЇкте штрихтал“ан облыста жататын болса а›и›ат мЩнін, бас›а жа“дайда жал“ан мЩнін ›абылдайтын йрнек жазу.
   

№2 Машы›тану саба“ы. ТеЈдеулер мен теЈсіздіктерді шешу.

1. 
   Бір сан ойла, о“ан 1500-ді ›ос, егер шы››ан сан 1550-ден арты› болса одан 150-ді ал, егер – кем болса, онда 150-ді ›ос. Сонда ›андай сан шы›ты? Осы есептіЈ алгоритмін жазу.
   
2. 
   ax=b теЈдеуін шешу алгоритмін ›±ру.
   
3. 
   ах³+bx²+cx+d=0 теЈдеуін шы“ару алгоритмін ›±ру.
   

№3 Машы›тану саба“ы. Функция кестесін ›±ру.

љайталану, таЈдау операторларын меЈгерту. Цикл тЇрлеріне то›талу.

Тапсырмалар:

1. 
   функциясыныЈ мЩндерін х-тіЈ 1 мен 5 аралы“ында“ы 0,5 ›адаммен ал“анда“ы мЩндері Їшін есептеу алгоритмін ›±ру.
   
2. 
   Y=f(x) функциясыныЈ [a,b] аралы“ында“ы мЩндерін h=(b-a)/n ›адаммен есептеу. М±нда“ы x_i=a+ih;i=0,1,2,3,...,m
   

№4 Машы›тану саба“ы. Программада циклды ±йымдастыру.

Циклдік операторларды ›олданып есеп шы“арту. Кірістірілген, кЇрделі циклдарды программалау.

Тапсырмалар:

1. 
   ›атар ›осындысын аны›тау.
   
2. 
   ›атар ›осындысын аны›тау.
   
3. 
   ›атар ›осындысын аны›тау.
   
4. 
   ›атар ›осындысын аны›тау.
   

№5 Машы›тану саба“ы. Сандар массивімен ж±мыс.

Массивте𠱓ымымен таныстыру. Массив тЇрлері, оларды есептерде ›олдану. Бірйлшемді массивтерді ›олдану.

Тапсырмалар:

1. 
   Бір йлшемді 30 элементтен т±ратын массивтіЈ оЈ элементтерініЈ санын аны›тау
   
2. 
   Бір йлшемді 30 элементтен т±ратын массивтіЈ теріс элементтерініЈ санын аны›тау
   
3. 
   Екі йлшемді 30 элементтен т±ратын массивтіЈ оЈ элементтерініЈ санын аны›тау
   
4. 
   Екі йлшемді 30 элементтен т±ратын массивтіЈ теріс элементтерініЈ санын аны›тау
   
5. 
   Бір йлшемді 15 элементтен т±ратын массивтіЈ 1-ші жолыныЈ оЈ элементтерініЈ ›осындысын аны›тау
   
6. 
   Екі йлшемді 20 элементтен т±ратын массивтіЈ 1-ші ба“аныныЈ оЈ элементтерініЈ ›осындысын аны›тау
   
7. 
   Бір йлшемді 15 элементтен т±ратын массивтіЈ n-ші жолыныЈ элементтерініЈ кйбейтіндісін аны›тау
   
8. 
   Екі йлшемді 15 элементтен т±ратын массивтіЈ n-ші ба“аныныЈ элементтерініЈ ›осындысын аны›тау аны›тау
   
9. 
   Екі йлшемді 20 элементтен т±ратын массивтіЈ n-ші жолыныЈ элементтерін нйлге айналдыру
   
10. 
    Екі йлшемді кездейсо› элементтерден т±ратын массивтіЈ n-ші ба“аныныЈ элементтерін бірге айналдыру
    

№6 Машы›тану саба“ы. Екі йлшемді массивтер, оларды сипаттау, ›олдану.