Информатика пәнінен лекциялық сабақтардың тезистері
Лекция 1. Тақырыбы: Ақпарат ұғымы. Ақпараттық үрдістер.
Лекция 2. Тақырып: Ақпаратты көрсету пішімдері.
3.лекция Тақырып: Алгоритмдер теориясына кіріспе.
4.лекция Тақырып: Алгоритмді беру тәсілдері және алгортмдерді құру әдістері
5.лекция Тақырып: Бағдарлама құру технологиялары және оларды жүзеге асыру
6.лекция Тақырып: Бағдарламалау әдістемелері.
7.лекция Тақырып: Алгоритмдер күрделілігін талдау және бағалау.
8.лекция Тақырып: Мәліметтер құрылымдары және олардың ұйымдастырылуы.
9.лекция Тақырып: Арифметика алгоритмдері, көпмүшеліктерді есептеу.
10.лекция Тақырып: Сұрыптау алгоритмдері. Массивтерді сұрыптау (ішкі сұрыптау).
11.лекция Тақырып: Сұрыптау алгоритмдері. Файлдарды сұрыптау (сыртқы сұрыптау).
12.лекция Тақырып: Іздеу алгоритмдері.
13.лекция Тақырып: Рекурсиялар, рекурренттіктер және итерациялар.
14.лекция Тақырып: Динамикалық бағдарламалау.
15.лекция Тақырып: Торда және графта тиімдеу есептері.
Лекция 2. Тақырып: Ақпаратты көрсету пішімдері.
3.лекция Тақырып: Алгоритмдер теориясына кіріспе.
4.лекция Тақырып: Алгоритмді беру тәсілдері және алгортмдерді құру әдістері
5.лекция Тақырып: Бағдарлама құру технологиялары және оларды жүзеге асыру
6.лекция Тақырып: Бағдарламалау әдістемелері.
7.лекция Тақырып: Алгоритмдер күрделілігін талдау және бағалау.
8.лекция Тақырып: Мәліметтер құрылымдары және олардың ұйымдастырылуы.
9.лекция Тақырып: Арифметика алгоритмдері, көпмүшеліктерді есептеу.
10.лекция Тақырып: Сұрыптау алгоритмдері. Массивтерді сұрыптау (ішкі сұрыптау).
11.лекция Тақырып: Сұрыптау алгоритмдері. Файлдарды сұрыптау (сыртқы сұрыптау).
12.лекция Тақырып: Іздеу алгоритмдері.
13.лекция Тақырып: Рекурсиялар, рекурренттіктер және итерациялар.
14.лекция Тақырып: Динамикалық бағдарламалау.
15.лекция Тақырып: Торда және графта тиімдеу есептері.
Ақпарат — бұл қажетті әртүрлі деректердің, мағлұматтардың, білімдердің, хабарлардың, дағдылар мен тәжірибелердің жиынтығы. Кез келген ақпарат дұрыс интерпретирлену, ақиқаттылық, өзектілік, толықтылық, бағалылық, анықтылық және түсініктілік қасиеттеріне ие.
Ақпарат ақиқат, егер ол жұмыстың ақиқат жағын көрсететін болса. Ақиқат емес ақпарат дұрыс түсінбеушілікке немесе дұрыс шешімнің қабылданбауына әкеліп соғуы мүмкін.
Ақпарат толық, егер түсінуге және шешімдер қабылдауға жеткілікті болса. Ақпараттың толық еместігі қабылданған шешімдердің кешігуіне, тіпті қателердің болуына әкеліп соғады.
Ақпараттың бағалығы ақпараттың көмегімен қандай мәселелерді шешуге болатындығында. Өзекті ақпаратты өзгерген жағдайда жұмыс істеу барысында алуға болады.
Информатика – адам өмірінің әртүрлі салаларында ақпараттың құрылымы мен жалпы қасиеттерін, оны іздеу, жинау, сақтау, түрлендіру және қолдану мәселелерін зерттейтін жас ғылыми пән.
Ақпарат ақиқат, егер ол жұмыстың ақиқат жағын көрсететін болса. Ақиқат емес ақпарат дұрыс түсінбеушілікке немесе дұрыс шешімнің қабылданбауына әкеліп соғуы мүмкін.
Ақпарат толық, егер түсінуге және шешімдер қабылдауға жеткілікті болса. Ақпараттың толық еместігі қабылданған шешімдердің кешігуіне, тіпті қателердің болуына әкеліп соғады.
Ақпараттың бағалығы ақпараттың көмегімен қандай мәселелерді шешуге болатындығында. Өзекті ақпаратты өзгерген жағдайда жұмыс істеу барысында алуға болады.
Информатика – адам өмірінің әртүрлі салаларында ақпараттың құрылымы мен жалпы қасиеттерін, оны іздеу, жинау, сақтау, түрлендіру және қолдану мәселелерін зерттейтін жас ғылыми пән.
Негізгі әдебиеттер:
1. Қаленова Б.С. Практикалық информатика курсы: Оқу құралы/Б.С.Қаленова.-Өскемен:ШҚМУ баспасы,2003.–126 б.
2. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учебное пособие для студентов пед. Вузов.-М., 1999.- 816 с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы./ Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
4. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск./ Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
5. Вирт Н. Алгоритмы + структуры данных = программа./ Н.Вирт. – М.: Мир, 1985.
6. Вирт Н. Алгоритмы и структуры данных./ Н.Вирт. – М.: Мир, 1989. – 360 с.
7. Лекции по Теории Вычислительных Процессов и Структур. http://lib.khsu.ru/245/int0.html (zip)
8. Каленова Б.С. Тестовые задания по информатике/ Каленова Б.С., Апышева Х.К., Жантасова Ж.З., Попова Г.В., Мухамедиева С.М., Сабыржанова А.Т., Сыздыкпаева А.Р., Уалханова А.Т., Шарапова М.М., Зарубин Н.П. – Усть-Каменогорск: Издательство ВКГУ им. Аманжолова, 2004.- 94 с.
9. Светозарова Г. В.. «Практикум по программированию на языке Бейсик». – М.: Инфра, 1997г.
Қосымша әдебиеттер:
10. Информатика: Учебник/ Под ред. Проф. Н.В. Макаровой. 2-е изд. – М.: Финансы и статистика, 2001.- 768 с.
11. Каймин, В.А. Информатика: Учеб.для вузов В.А Каймин; М-во образования РФ.-3-е изд.-М.:ИНФРА-М, 2003.-272 с.
12. Степанов А.Н. Информатика: Учеб.пособие для вузов./ А. Н.Степанов. - 3-е изд.- СПб.: Питер, 2003.- 608 с
13. Козырев А.А. Информатика: Учеб.для вузов/ А.А.Козырев. – СПб.: Изд-во Михайлова В.А., 2002. – 511 с.
14. Альфред В. Ахо. Структуры данных и алгоритмы.: Пер. с англ./ Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Изд. Дом «Вильямс», 2001. – 384 с.: ил.
15. Могилев А.В., Пак Н.И., Хеннер Е.К. Практикум по информатике: Учебное пособие для студентов вузов.-М., 2002.- 608 с.
16. Брукшир Дж. Информатика и выислительная техника. 7-ое изд./ Дж.Брукшир. – СПб.: Питер, 2004. – 620 с.: ил.
17. Брой М. Информатика. Основополагающее введение: В 4 ч. –М.: Диалог; МИФИ, 1996. –Ч.1.
18. Э.З. Любимский. Программирование. Учеб. Пособие для вузов./ Любимский Э.З., Мартынюк В.В., Трифонов Н.П. – М.: Наука, 1980. – 603 с.
19. Альфред В. Ахо. Построение и анализ вычислительных алгоритмов.: Пер. с англ./ Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Мир, 1979. – 519 с.: ил.
20. Фролов Г.Д. Элементы информатики.: Учеб. Пособие для пед. ин-тов./ Г.Д. Фролов, Э.И. Кузнецов. – М.: Высш.шк., 1989. – 304 с.: ил.
1. Қаленова Б.С. Практикалық информатика курсы: Оқу құралы/Б.С.Қаленова.-Өскемен:ШҚМУ баспасы,2003.–126 б.
2. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учебное пособие для студентов пед. Вузов.-М., 1999.- 816 с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы./ Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
4. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск./ Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
5. Вирт Н. Алгоритмы + структуры данных = программа./ Н.Вирт. – М.: Мир, 1985.
6. Вирт Н. Алгоритмы и структуры данных./ Н.Вирт. – М.: Мир, 1989. – 360 с.
7. Лекции по Теории Вычислительных Процессов и Структур. http://lib.khsu.ru/245/int0.html (zip)
8. Каленова Б.С. Тестовые задания по информатике/ Каленова Б.С., Апышева Х.К., Жантасова Ж.З., Попова Г.В., Мухамедиева С.М., Сабыржанова А.Т., Сыздыкпаева А.Р., Уалханова А.Т., Шарапова М.М., Зарубин Н.П. – Усть-Каменогорск: Издательство ВКГУ им. Аманжолова, 2004.- 94 с.
9. Светозарова Г. В.. «Практикум по программированию на языке Бейсик». – М.: Инфра, 1997г.
Қосымша әдебиеттер:
10. Информатика: Учебник/ Под ред. Проф. Н.В. Макаровой. 2-е изд. – М.: Финансы и статистика, 2001.- 768 с.
11. Каймин, В.А. Информатика: Учеб.для вузов В.А Каймин; М-во образования РФ.-3-е изд.-М.:ИНФРА-М, 2003.-272 с.
12. Степанов А.Н. Информатика: Учеб.пособие для вузов./ А. Н.Степанов. - 3-е изд.- СПб.: Питер, 2003.- 608 с
13. Козырев А.А. Информатика: Учеб.для вузов/ А.А.Козырев. – СПб.: Изд-во Михайлова В.А., 2002. – 511 с.
14. Альфред В. Ахо. Структуры данных и алгоритмы.: Пер. с англ./ Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Изд. Дом «Вильямс», 2001. – 384 с.: ил.
15. Могилев А.В., Пак Н.И., Хеннер Е.К. Практикум по информатике: Учебное пособие для студентов вузов.-М., 2002.- 608 с.
16. Брукшир Дж. Информатика и выислительная техника. 7-ое изд./ Дж.Брукшир. – СПб.: Питер, 2004. – 620 с.: ил.
17. Брой М. Информатика. Основополагающее введение: В 4 ч. –М.: Диалог; МИФИ, 1996. –Ч.1.
18. Э.З. Любимский. Программирование. Учеб. Пособие для вузов./ Любимский Э.З., Мартынюк В.В., Трифонов Н.П. – М.: Наука, 1980. – 603 с.
19. Альфред В. Ахо. Построение и анализ вычислительных алгоритмов.: Пер. с англ./ Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Мир, 1979. – 519 с.: ил.
20. Фролов Г.Д. Элементы информатики.: Учеб. Пособие для пед. ин-тов./ Г.Д. Фролов, Э.И. Кузнецов. – М.: Высш.шк., 1989. – 304 с.: ил.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 30 бет
Таңдаулыға:
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 30 бет
Таңдаулыға:
3.6 Список литературы
Негізгі әдебиеттер:
1. Қаленова Б.С. Практикалық информатика курсы: Оқу құралыБ.С.Қаленова.-
Өскемен:ШҚМУ баспасы,2003.–126 б.
2. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учебное пособие для
студентов пед. Вузов.-М., 1999.- 816 с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные
алгоритмы. Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
4. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и
поиск. Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
5. Вирт Н. Алгоритмы + структуры данных = программа. Н.Вирт. – М.: Мир,
1985.
6. Вирт Н. Алгоритмы и структуры данных. Н.Вирт. – М.: Мир, 1989. – 360
с.
7. Лекции по Теории Вычислительных Процессов и Структур.
http:lib.khsu.ru245int0.html (zip)
8. Каленова Б.С. Тестовые задания по информатике Каленова Б.С., Апышева
Х.К., Жантасова Ж.З., Попова Г.В., Мухамедиева С.М., Сабыржанова А.Т.,
Сыздыкпаева А.Р., Уалханова А.Т., Шарапова М.М., Зарубин Н.П. – Усть-
Каменогорск: Издательство ВКГУ им. Аманжолова, 2004.- 94 с.
9. Светозарова Г. В.. Практикум по программированию на языке Бейсик. –
М.: Инфра, 1997г.
Қосымша әдебиеттер:
10. Информатика: Учебник Под ред. Проф. Н.В. Макаровой. 2-е изд. – М.:
Финансы и статистика, 2001.- 768 с.
11. Каймин, В.А. Информатика: Учеб.для вузов В.А Каймин; М-во образования
РФ.-3-е изд.-М.:ИНФРА-М, 2003.-272 с.
12. Степанов А.Н. Информатика: Учеб.пособие для вузов. А. Н.Степанов. -
3-е изд.- СПб.: Питер, 2003.- 608 с
13. Козырев А.А. Информатика: Учеб.для вузов А.А.Козырев. – СПб.: Изд-во
Михайлова В.А., 2002. – 511 с.
14. Альфред В. Ахо. Структуры данных и алгоритмы.: Пер. с англ. Ахо
Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Изд. Дом
Вильямс, 2001. – 384 с.: ил.
15. Могилев А.В., Пак Н.И., Хеннер Е.К. Практикум по информатике: Учебное
пособие для студентов вузов.-М., 2002.- 608 с.
16. Брукшир Дж. Информатика и выислительная техника. 7-ое изд.
Дж.Брукшир. – СПб.: Питер, 2004. – 620 с.: ил.
17. Брой М. Информатика. Основополагающее введение: В 4 ч. –М.: Диалог;
МИФИ, 1996. –Ч.1.
18. Э.З. Любимский. Программирование. Учеб. Пособие для вузов. Любимский
Э.З., Мартынюк В.В., Трифонов Н.П. – М.: Наука, 1980. – 603 с.
19. Альфред В. Ахо. Построение и анализ вычислительных алгоритмов.: Пер. с
англ. Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Мир,
1979. – 519 с.: ил.
20. Фролов Г.Д. Элементы информатики.: Учеб. Пособие для пед. ин-тов.
Г.Д. Фролов, Э.И. Кузнецов. – М.: Высш.шк., 1989. – 304 с.: ил.
2.2 Лекциялық сабақтардың тезистері:
Лекция 1. Тақырыбы: Ақпарат ұғымы. Ақпараттық үрдістер.
Ақпарат — бұл қажетті әртүрлі деректердің, мағлұматтардың, білімдердің,
хабарлардың, дағдылар мен тәжірибелердің жиынтығы. Кез келген ақпарат дұрыс
интерпретирлену, ақиқаттылық, өзектілік, толықтылық, бағалылық, анықтылық
және түсініктілік қасиеттеріне ие.
Ақпарат ақиқат, егер ол жұмыстың ақиқат жағын көрсететін болса. Ақиқат
емес ақпарат дұрыс түсінбеушілікке немесе дұрыс шешімнің қабылданбауына
әкеліп соғуы мүмкін.
Ақпарат толық, егер түсінуге және шешімдер қабылдауға жеткілікті болса.
Ақпараттың толық еместігі қабылданған шешімдердің кешігуіне, тіпті
қателердің болуына әкеліп соғады.
Ақпараттың бағалығы ақпараттың көмегімен қандай мәселелерді шешуге
болатындығында. Өзекті ақпаратты өзгерген жағдайда жұмыс істеу барысында
алуға болады.
Информатика – адам өмірінің әртүрлі салаларында ақпараттың құрылымы мен
жалпы қасиеттерін, оны іздеу, жинау, сақтау, түрлендіру және қолдану
мәселелерін зерттейтін жас ғылыми пән.
Информатиканы оқудың маңыздылығы ЭЕМ-ді қолдану мүмкіндіктері мен жұмыс
істеу принциптерін түсінуге мүмкіндік беріп қана қоймай, қоғам өмірінің
және адамдардың қатынасу кезінде ақпараттың берілу әдістері және
заңдарымен танысуға мүмкіндік береді. Оқудың күрделілігі техникалық
құрылғылардың жылдам прогресстерімен және бағдарламалық
қамтамасыздандырулармен байланысты.
Негізгі әдебиеттер: 1, 2, 3, 4.
Қосымша әдебиеттер: 11, 12
Лекция 2. Тақырып: Ақпаратты көрсету пішімдері.
Сигнал – уақыт ішінде өзгеретін физикалық үрдіс (мысалы, тізбекте
жүретін электр тогы, жарықтың таралу үрдісі). Ақпарат физикалық үрдістің,
яғни сигналдың бір немесе бірнеше параметрлерінің мәнімен беріледі.
Егер сигнал параметрі берілген аралықта кез келген аралық мән қабылдай
алатын болса (уақытқа байланысты үздіксіз функциямен анықталса), онда
сигнал үздіксіз ал мұндай сигналмен анықталған хабар да үздіксіз деп
аталады. Бұл жағдайда таратқышпен берілген ақпарат үздіксіз түріне ие
болады.
Егер сигнал параметрі берілген аралықта жеке бекітілген мәндерді
қабылдаса, онда сигнал дискретті, ал мұндай сигналмен анықталған хабар да
дискретті деп аталады. Бұл жағдайда таратқышпен берілген ақпарат дискретті
түріне ие болады. Сонымен біз ақпарат берілуінің екі негізгі түрін
(пішімін) - үздіксіз және дискретті ақпаратты анықтадық.
Санау жүйесі – сандық мәліметтерді көрсету тәсілдері мен ережелерінің
келісілген жиынтығы. Санау жүйелерінің екі түрі бар: позициялық және
позициялық емес (бейпозициялық).
Позициялық емес санау жүйелерінде беру және жазу ережелері күрделі болып
табылады. Мұндай санау жүйелерінің бірі – римдік сан жүйесі. Мысалы,
MCMXCVIII – 1998 деген сөз, мұнда M – мыңдық, C – жүздік, X – ондық, V –
бес, I – бір, т.с.с.
Позициялық санау жүйелерінде санның мәні тек қана оның құрамына кіретін
цифрлармен ғана емес, сонымен қатар цифрлардың тізбектегі орнымен
анықталады. Позициялық сан жүйесінде қолданылатын таңбалардың саны оның
негізі деп аталады, оны q әрпімен белгілейік (мысалы ондық сан жүйесінде он
таңба(цифр): 0,1,2,...,9). Санау жүйесінің таңбаларының жиынтығын оның
алфавиті деп атайды.
Негізгі әдебиеттер: 1, 2, 3, 4, 8
Қосымша әдебиеттер: 11, 12
3-лекция Тақырып: Алгоритмдер теориясына кіріспе.
Алгоритм ұғымы информатиканың ақпарат сияқты негізгі ұғымдарының бірі
болып табылады. Сондықтан алгоритм ұғымын талқылау ең қажетті болып
саналады.
Алгоpитм — кез келген алғашқы мәліметтен ( берілген алгоритм үшін мүмкін
алғашқы мәліметтердің қандай да бір жиынтығынан) басталатын және осы
алғашқы мәліметпен толық анықталатын нәтиже алуға бағытталған алгортмдік
үрдісті беретін дәл нұсқаулар тізбегі.
Бұл - алгоритм ұғымының интуитивті сипатталуы болып табылады.
Алгоритмдік үрдіс – коснтруктивті объектілерді (сөз, сан, сөз жұбы, сан
жұбы, сөйлемдер және т.б.) дискретті қадаммен түрлендіру үрдісі.
Алгоритмнің негізгі қасиеттері: дискреттілік, түсініктілік, анықтылық,
нәтижелік, көпшілік.
Алгоритмді орындаушы — бұл алгоритммен тағайындалатын әрекеттерді
орындай алатын абстрактілі немесе нақты жүйе (техникалық, биологиялық
немесе биотехникалық).
Орындаушыны орта; элементарлық әрекеттер; командалар жүйесі;
әрекеттерінің формальдығы сипаттайды. Информатикада әмбебап алгоритм
орындаушысы компьютер болып табылады.
Орындаушының командалар жүйесі – орындаушы орындай алатын барлық
командалар жиынтығы. Әрбір команда үшін қолдану шарттары берілуі (ортаның
қандай жағдайында команда орындалуы мүмкін) және команданың орындалу
нәтижелері жазылған болуы тиіс. Команданы шақырғаннан кейін орындаушы
сәйкес элементарлық әрекеттерді орындайды.
Орындаушы формальды түрде әрекет етеді, яғни есептің мазмұнына
үңілмейді, тек қана қажетті нәтиже алу үшін қатаң түрде әрекеттерді
(командаларды) орындайды. Енді алгоритм орындаушысы ұғымын қолдана отырып
алгоритм ұғымын анықтауға болады.
Алгоpитм — алдыға қойылған есептің шешіміне ақырлы қадаммен жету үшін
қажетті қимылдар тізбегінің орындаушыға түсінікті және дәл нұсқаулары.
Алгоритм іргелі ғылыми ұғым ретінде қатаң сипаттауды талап етеді, яғни
формальдауды. Алгоритм ұғымы формальдаудың келесі бағыттары белгілі:
– шекті және шексіз автоматтар теориясы (Пост, Тьюринг машиналары,
Марковтың қалыпты алгоритмдері және т.б.);
– есептелетін (рекурсивті) функциялар теориясы;
– Черчтің (-есептеуі (LISP бағдарламалау тілі).
Алгоритм ұғымын формальдаудың негізгі мақсаты: әртүрлі математикалық
есептердің алгоритмдік шешілу мәселелерін қарастыру, яғни есептің шешілуіне
әкеп соғатын алгоритм тұрғызуға бола ма деген сұраққа жауап беру.
Негізгі әдебиеттер: 1, 5
Қосымша әдебиеттер: 12, 20
4-лекция Тақырып: Алгоритмді беру тәсілдері және алгортмдерді құру
әдістері.
Практикада алгоритмдерді берудің (жазбалар) келесі тәсілдері кең
тараған:
– сөздік (табиғи тілдегі жазба);
– графикалық (графикалық символдардан тұратын бейнелер);
– псевдокодтық (шартты алгоритмдік тілде алгоритмдерді жартылай
формальданған түрде сипаттау.);
– бағдарламалық (бағдарламалау тілдеріндегі мәтіндер).
Алгоритмді берудің сөздік тәсілі мәліметтерді өңдеу кезеңдерінің
тізбегін табиғи тілде сипаттауды ұсынады.
Сөздік тәсіл кеңінен таралмаған, өйткені мұндай сипаттамалар қатаң
формальданбаған, жазбалардың көпсөзділігі кері әсер тигізеді,
көпмағыналылыққа жол береді.
Графикалық тәсілде алгоритм әрқайсысы бір немесе бірнеше әрекеттерге
сәйкес келетін, бір-бірімен байланысқан функционалдық блоктар тізбегі
түрінде бейнеленеді. Мұндай графикалық берілу алгоритм сызбасы немесе блок-
сызба деп аталады.
Псевдокод алгоритмдерді біркелкі жазуға арналған белгілеу лер және
ережелер жүйелерін ұсынады, табиғи және формальды тілдер арасында аралық
орынға ие. Псевдокодтың ортақ немесе формальды анықтамасы жоқ, сондықтан
қызметтік сөздер жиынымен және негізгі (базалық) конструкциялармен
ерекшеленетін әртүрлі псевдокодтар болуы мүмкін.
Практикада алгоритмдерді орындаушы ретінде арнайы автоматтар —
компьютерлер қолданылады. Сондықтан, компьютерде орындауға арналған
алгоритмдер оған түсінікті тілде жазылуы тиіс. Алгоритмді жазу тілі
бұйрықтарды (командаларды) талқылаусыз дәл беруі тиіс. Мұндай тіл -
бағдарламалау тілі, ал осы тілде алгортимнің жазылуы — компьютерге арналған
бағдарлама деп аталады.
Кез келген алгоритмнің логикалық құрылымы үш базалық құрылым
комбинациясы түрінде берілуі мүмкін:
тізбектік, тармақталу, цикл. Базалық құрылымдардың негізгі ерекшеліктері -
оларда бір ғана кіру мен шығудың болуы. Алгоритмдерді жеке базалық (яғни,
негізгі) элементтерден құралған құрылым ретінде беруге болады. Сондықтан
алгоритмдерді құрастыру ұстанымдарын зерттеуді осы базалық элементтерді
қарастырудан бастау қажет.
"Тізбектік" базалық құрылымы. Бірінен соң бірі жалғасып отыратын
әрекеттер тізбегінен құрылады.
"Тармақталу" базалық құрылымы. Шартты тексеру нәтижесіне (иә немесе жоқ)
байланысты алгоритм жұмысының альтернативті жолдарының бірін таңдауды
қамтамасыз етеді. Жолдардың әрқайсысы ортақ шығуға әкеледі, сондықтан
алгоритм жұмысы қандай жолдың таңдалуына қарамастан ары қарай жалғаса
береді. Тармақталу құрылымы төрт негізгі нұсқалардан тұрады: егер - онда;
егер – онда - әйтпесе; таңдау; таңдау - әйтпесе.
"Цикл" базалық құрылымы. Цикл денесі деп аталатын кейбір әрекеттер
жиынтығының бірнеше мәрте орындалуын қамтамасыз етеді.
Күрделі есептер үшін алгоритм құру кезінде декомпозициялар (жоғарыдан
төменге қарай жобалау) және синтездің (төменнен жоғарыға қарай жобалау)
қатысуымен жүйелік бағыт қолданылады. Күрделі жүйе құрылымын құру кезінде
де, алгоритмді қалыптастыру кезінде де дедуктивті және индуктивті әдістер
қолданылады. Алгоритмдерді құрудың көптеген әдістері бар, бірақ келесі
негізгілерді атап өту қажет: жеке мақсаттар әдісі (декомпозициялар); өрлеу
әдістері; шекара және тармақ әдістері; кері өңдеу әдістері; мәліметтер
құрылымына негізделген әдістер, динамикалық бағдарламалау және т.б.
әдістер.
Негізгі әдебиеттер: 1, 4, 5
Қосымша әдебиеттер: 12, 14
5-лекция Тақырып: Бағдарлама құру технологиялары және оларды жүзеге
асыру.
Есептерді компьютердің көмегімен шешу қандай да бір бөлігі компьютердің
қатысынсыз жүзеге асырылатын келесі негізгі кезеңдерден тұрады.
1. Есептің қойылуы: есеп туралы ақпараттарды жинау; есеп шартын
фоpмальдау; есепті шешудің соңғы мақсаттарын анықтау; нәтижелерді беру
пішімдерін анықтау; мәліметтерді сипаттау (олардың типін, диапазонын,
құрылымын және т.б.).
2. Есепті, моделді зерттау және талдау: бар аналогтарды талдау;
техникалық және бағдарламалық құралдарды талдау; математикалық моделді
құру; мәліметтер құрылымын құру.
3. Алгоритм құру: алгоритмді жобалау әдісін таңдау; алгоритмді беру
тәсілін таңдау (блок-сызбалар, псевдокод және т.б.); тестер және
тестілеу әдістерін таңдау; алгоритмді жобалау.
4. Бағдарламалау: бағдарламалау тілін таңдау; мәліметтерді ұйымдастыру
тәсілдерін анықтау; бағдарламалаудың таңдалған тілінде алгоритмді
жазу.
5. Тестілеу және жөндеу: синтаксистік жөндеу; семантиканы және логикалық
құрылымды жөндеу; тестілік есептеулер және тестілеу нәтижесін талдау;
бағдарламаның жетілуі.
6. Есепті шешу нәтижелерін талдау және қажет жағдайда 2-5 кезеңдерді
қайталай отырып математикалық моделді дәлдеу.
7. Бағдарламаны сүйемелдеу: нақты есептер шешу үшін бағдарламаны аяқтау;
шешілген есепке, алгоритмге, бағдарламаға, тестер жинағына, қолдануға
құжаттаманың құрастырылуы.
Бағдарламаның верификациялануы (verification) – бағдарлама жұмысының
дәлдігі және оның басқа да есептер шешу инструменті ретінде мүмкіндіктері.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 19
6-лекция Тақырып: Бағдарламалау әдістемелері.
Бағдарламалаудың келесі парадигмалары бар: процедуралық немесе
императивтік; декларативтік; функционалдық; объектілі-бағытталған.
Бағдарламалау әдістемелеріне дұрыстық, сенімділік, түсініктілік, тиімділік
және т.б. қасиеттерге ие жақсы бағдарламаларды құру әдістеріне байланысты
сұрақтар жиыны жатады. Бағдарламалау әдістемелері: операциальды-
бағытталған; процедуралы-бағытталған; құрылымды; объектілі-бағытталған;
декларативті (функциональды және логикалы); параллельді.
Құрылымды бағдарламалау негізінде кез келген есепті шешу үшін тек
тізбектік, тармақталу, цикл құрылымдарын ғана қолдануға болады деген
теорема (бағдарламалау теориясында дәлелденген) жатыр. Құрылымдық бағыттың
маңызды ерекшеліктері: нақты есеп шарттарына сәйкес базалық құрылымдардың
суперпозицияларын құрастыру мүмкіндіктері; модульдік; декомпозициялау
мүмкіндіктері, яғни бағдарламаны жоғарыдан төмен жобалау.
Модуль – бұл бағдарламаның жеке бөлігі ретінде құралған логикалық
байланысты операциялар тізбегі.
Бағдарламалық жасақтамалар құру әдістемелерін жасау БЖ жобалау
мәселелерінің негізгі міндеттерінің бірі болып табылады. Бағдарламаны
жобалаудың белгілі әдістемелері төменнен жоғары қарай және жоғарыдан төмен
қарай жобалау болып табыладыя. Төменнен жоғары қарай жобалау – күрделі
есептерді шешу үшін әрқайсысы негізгі есепке бағынатын және жеке модульдік
процедуралармен жүзеге асатын қарапайым бағыныңқы есептер иерархиясы арқылы
құрастырылатын жобалау. Жоғарыдан төменге қарай жобалану – жүйені құрудың
жобалануы жүйенің жеке есептерін анықтаудан басталады және осы есептердің
шешілуі абстрактілі құралдар ретінде күрделі есептерде қалай қолданылуы
талқыланады.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 19
7-лекция Тақырып: Алгоритмдер күрделілігін талдау және бағалау.
Алгоритмді құрған кезде екі ұғымды ескерген жөн: ол – алгоритмнің
тиімділігі мен дұрыстығы. Жалпы алып қарағанда, тиімділік ұғымы алгоритм
жұмысына қажетті барлық есептеу ресурстарвмен байланысты. Тиімділік
алгоритмнің шекті уақытта ғана емес, мүмкін шекті уақытта орындалатындығын
көрсетеді. Алгоритм мен сәйкес бағдарламаның дұрыстығын тексеру өте
маңызды, ал тексерудің тиімді әдістерін іздеу есептеу техникасында өзекті
мәселелер болып табылады. Алгоритмнің дұрыстығын тексерудегі ізденістердің
бір бағыты – формальды логиканың әдістерін қолдану. Бұл жолдың негізгі
ұстанымы: дұрыстықты тексеру үрдісін формальдау процедурасына әкелу
интуитивті болжауларға сүйенген қателіктерден құтқарады.
Алгоритмнің тағы бір негізгі мінездемелерінің бірі – оның күрделілігі.
Әдетте алгоритмдер күрделілігінің дәрежесі оперативті жады және
процессорлық уақыт сияқты қолданылатын компьютер ресурстарының көлемімен
бағаланады. Осыған байланысты алгоритмнің уақыт бойынша күрделілігі және
көлем бойынша күрделілігі анықталады. Көп жағдайда уақыт бойынша шектеулер
басым рөл атқаратындықтан уақыт бойынша күрделілік маңызды болып
есептеледі. Уақыт бойынша күрделілік орындалатын операциялар санымен
анықталады, алғашқы мәліметтерге тәуелді (олардың көлеміне және шамасына)
Алгоритмнің уақыт бойынша күрделілігі – алгоритмнің есепті шешуіне
жұмсаған уақыты, ол есептің өлшемі n-ге тәуелді функция. Бұл күрделіліктің
есептің өлшемі өсудегі шектік мінездемесі асимптотикалық уақыт бойынша
күрделілік деп аталады. Көлем бойынша күрделілік және асимптотикалық көлем
бойынша күрделіліктер де осыған сәйкес анықталады Мысалы, егер алгоритм n
өлшемді енгізулерді cn2 уақытында, мұнда c – қандай да бір тұрақты, өңдесе,
онда уақыт бойынша күрделілік ((n2) деп айтады. Алгоритмдерді талдауда ең
жақсы, ең жаман және орта жағдайлар қарастырылады, сәйкес бағалаулар
беріледі. Алгоритмдерді құру мен талдауда олардың тиімділігін салыстыру
үшін теоретиктермен қарапайым жол ұсынылған: полиномиалдық және
экспоненциалдық алгоритмдер арасындағы айырмашылық.
Егер алгоритмнің уақыт бойынша күрделілігі есеп өлшемі n-нің
полиномиалдық функциясы түрінде өрнектелсе, онда алгоритм полномиалдық деп
аталады. Алгоритмнің уақыт бойынша күрделілігі мұндай бағалуға бағынбаса,
онда ол экспоненциалдық деп аталады. Есепті шешудің қарапайым алгоритмінің
күрделілігі осы есептің күрделілігі деп аталады. Егер есепті шешудің уақыт
бойынша күрделілігі ((f(n))-ге тең алгоритмі бар болса, онда есептің
күрделілігі ((f(n))-ға тең, мұнда f(n) – қандай да бір n-ге тәулді
функция,. Сондай-ақ бұл есепті O(f(n)) класының есебі деп атайды. Егер есеп
O(f(n)) класында жататын болса, мұнда f(n) –полином, немесе бұл өрнек
полиноммен шектелген, онда ол полиномиалдық деп аталады,. Барлық
полиномиалдық есептердің жиынтығы P (тізімде ізду, сұрыптау есептері және
т.б.) деп белгіленеді. Егер есеп үшін полиномиалдық алгоритм құру мүмкін
емес болса, яғни P-ға тиісті емес, онда ол қиын шешілетін есеп деп аталады.
Детерминделмеген алгоритмнің көмегімен полиномиалдық уақыт көлемінде
шешілетін есепті детерминделмеген полиномиалдық есеп немесе NP-есеп (
коммивояжер есебі және т.б.) деп атайды. NP-есептер класы NP деп
белгіленеді. Барлық P есептері NP-да жатады, ал кері тұжырым жоқ. NP класы
P класымен сәйкес пе деген сұрақты зерттеу NP класында жаңа есептер класын
- NP-толық есептер деп аталатын класты ашты. Сөйтіп есептер шешілетін
(алгоритмдік шешімі бар) и шешілмейтін (алгоритмдік шешімдері жоқ)
болатындығы анықталды. Сонымен қатар шешілетін есептер класында екі ішкі
класстар: –полиномиалдық есептер және полиномиалдық емес есептер бар.
Жіктелмейтін жұмбақ NP-есептер де (шифрлеу есептері және т.б.) бар.
Негізгі әдебиеттер: 1, 4, 5
Қосымша әдебиеттер: 12
8-лекция Тақырып: Мәліметтер құрылымдары және олардың ұйымдастырылуы.
Мәліметтер – бұл белгілі бір пішімде берілген және ары қарай
пайдалануға арналған қандайда бір жүйені, құбылысты, үрдісті немесе объекті
сипаттайтын мағлұматтар. Ақпарат және мәліметтер ұғымдарының арасындағы
арақатынас тұрғысынан алып қарағанда: мәліметтер – бұл ақпараттың мазмұнын
көрсететін нақты пішім; мәліметтер – бұл пайдаланушы үшін маңызды және
онымен қандай да бір есептерді шешуге қолданылады. Мәліметтерге бірнеше
классификациялық мінездемелер меншіктеледі. Олардың ішіндегі ең маңыздысы
мәліметтер типі болып табылады. Мәліметтер типі мүмкін мәндер жиынын;
олардың өңделу ережелерін (түрлендіру); сақтау кезінде ОСҚ және ССҚ-да
олардың орналасу ретін; оларға қатынау ретін анықтайды. Негізгі мәліметтер
типтері: стандарттық, қарапайым, шектелген, күрделі құрылымдық және т.б.
Мәліметтер типтерінің концепциясы пайдаланушыға мәліметтерді беру, сақтау,
қолдану есептерін тиімді шешуде көп мүмкіндіктер береді; мәліметтердің
жинақтылығына әсер етеді. Сонымен қатар мәліметтер элементарлық (қарапайым)
құрылымданбаған және құрылымданған (күрделі) болып жіктеледі. Элементарлық
мәліметтерге символдар, сандар және логикалық мәліметтер жатады, олардың
әрқайсысы бір мәнмен және атпен анықталады. Мәліметтерді және олардың
арасындағы байланыстарды біріктіретін ақпараттық массивті құрылымданған
мәліметтер деп атайды. Біріктірілетін қарапайым мәліметтердің тізімі,
олардың мінездемелері, сонымен қатар арасындағы байланыстардың
ерекшеліктері мәліметтер құрылымын анықтайды. Күрделі мәліметтер де мәнімен
және атымен анықталады. Өңдеу үрдісінде мәндерінің өзгеруіне байланысты
(қарапайым және құрылымдық мәліметтер үшін) мәліметтерді айнымалы және
тұрақты деп бөледі. Өңдеудің қай кезеңінде қолданылуына байланысты
мәліметтерді алғашқы(енетін), аралық, қорытынды(шығатын) мәліметтер деп
бөледі.
Сақтауда және өңдеуде мәліметтерді беру үш негізгі есепті шешуді қажет
етеді: элементарлық мәліметтерді беру әдістерін анықтау; мәліметтердің
құрылымға бірігу әдістерін анықтау; мәліметтердің материалдық тасуышта
орналасуын анықтау. Мәліметтерді берудің үш деңгейін анықтайды:
концептуалдық, логикалық және физикалық. Концептуалдық деңгейде ақпараттық
массивтің жалпы құрылымы анықталады, ол мәліметтер моделі деп аталады.
Мәліметтер моделдерінің негізгілері: иерархиялық, желілік, реляциялық,
объектілі-бағытталған.
Қатынастарының мінездемелеріне байланысты мәліметтер құрылымдарының
бірнеше жіктелу белгілерін анықтауға болады: мәліметтердің реттері бойынша
– реттелген және реттелмеген, қатынастарының мінездемелері бойынша –
сызықтық және сызықтық емес, құрылымдағы мәліметтер типтеріне байланысты –
біртекті және біртексіз, мәліметтерге қатынау әдістеріне байланысты – тура
жететін және тізбектік жететін, ақпараттық массивтің өлшемінің өзгеру
мүмкіндігіне байланысты – статикалық және динамикалық.
Негізгі күрделі құрылымдар: массив, жиын, кезек, стек, ағаш (екілік
ағаш), граф, тізімдер (логикалық жазба). Мәліметтерді ұйымдастыруда үш
типті қолданады: сызықтық(тізбектік), кестелік, иерархиялық.
Негізгі әдебиеттер: 1, 4, 5,
Қосымша әдебиеттер: 12, 20
9-лекция Тақырып: Арифметика алгоритмдері, көпмүшеліктерді есептеу.
Сандық есептеулер бүтін сандар жиынында немесе нақты сандар жиынында
жүргізілуі мүмкін. ЭЕМ-де бүтін сандық арифметика нақты сандармен
арифметкамен салыстырғанда үш маңызды артықшылыққа ие: бүтін сандар әрқашан
да өздерінің дәл мәндерімен беріледі; бүтін сандық арифметиканың
операциялары дәл нәтижелер береді; бүтін сандық арифметиканың операциялары
жылдамырақ орындалады. Бүтін санды мәліметтердің кемшілігі олардың мүмкін
мәндері диапазонының тарлығы.
Нақты сандар жадта жуық мәндерімен сақталады, яғни өздерінде қателіктер
сақтайды, бұл қателіктер машиналық жуықтау қателіктері деп аталады.
Реккуренттік тізбектерді есептеулерді бағдарламалау келесі есептер
түрлерімен байланысты: тізбектің берілген (n-ші) элементін есептеу,
тізбектің белгілі бір бөлігін математикалық өңдеу (мысалы, қосындыны
есептеу); тізбектің берілген аралығында белгілі шарттарды қанағаттандыратын
элементтер санын есептеу; тізбек элементтерінің берілген санын есептеп
және жадта сақтау; белгілі шартты қанағаттандыратын тізбектің алғашқы
элементін анықтау.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 14, 13, 20
10-лекция Тақырып: Сұрыптау алгоритмдері. Массивтерді сұрыптау (ішкі
сұрыптау).
Алгоритмдерді әдетте сандық (есептеу) және сандық емес (есептеусіз) деп
бөледі. Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге
арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен
жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау
және іздеу табылады. Объектілердің берілген тізбегін қандай да бір
анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды.
Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді
жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді,
сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау
алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау
алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар
массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен
анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті
элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі
орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы
мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив.
Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды
пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды
жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері
бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау (көбікше
әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі
кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау
(пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау).
Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,..., ai-1
және кіретін тізбекке ai,..., an бөлінеді, содан кейін әрбір қадамда, i=2
бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін
алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең
кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын
ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше
сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең
жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең
жақсысы болып табылады.
Негізгі әдебиеттер: 1, 2-6.
Қосымша әдебиеттер: 13-15, 18.
11-лекция Тақырып: Сұрыптау алгоритмдері. Файлдарды сұрыптау (сыртқы
сұрыптау).
Сыртқы сұрыптау алгоритмдері – бұл сыртқы жадтағы мәліметтерді сұрыптау
алгоритмдері, мұнда қолайлы құрылым - файл . Негізгі ерекшелігі - өңдеудің
әрбір уақыт мезетінде тек бір ғана элементі(компонента) жетімді. Файлдарды
сұрыптау әдістерінің көпшілігі (доступных в данный момент) тоғыстыру
процедурасына негізделеді. Тоғыстыру – екі (немесе одан да көп) тізбектерді
бір тізбекке біріктіру, ол тізбек элементтері қайталанатын таңдау арқылы
реттелген . Қарапайым тоғыстыру келесі қадамдардан тұрады:
1. a тізбегі b және c екі жартыға бөлінеді;
2. b және c тізбектері жеке элементтерді реттелген жұптарға біріктіру
арқылы тоғыстырылады;
3. Алынған тізбек a деп аталады, содан кейін 1 және 2 қадамдар
қайталанады; бұл жолы реттелген жұптар реттелген төрттіктерге
тоғыстырылады;
4. Алдыңғы қадамдар қайталады; төрттіктер сегіздіктерге тоғыстырылады,
барлық үрдіс бүкіл тізбек реттелгенше жалғасады; тоғыстырылатын жарты
тізбектер ұзындықтары екі еселеніп отырады.
Табиғи тоғыстыру – бұл әр тоғыстыруда мүмкін ең ұзын ішкі тізбектер
біріктірілетін тоғыстыру..
Негізгі ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Негізгі әдебиеттер:
1. Қаленова Б.С. Практикалық информатика курсы: Оқу құралыБ.С.Қаленова.-
Өскемен:ШҚМУ баспасы,2003.–126 б.
2. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учебное пособие для
студентов пед. Вузов.-М., 1999.- 816 с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные
алгоритмы. Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
4. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и
поиск. Д. Кнут. – Москва, Санкт-Петербург, Киев, 2000.
5. Вирт Н. Алгоритмы + структуры данных = программа. Н.Вирт. – М.: Мир,
1985.
6. Вирт Н. Алгоритмы и структуры данных. Н.Вирт. – М.: Мир, 1989. – 360
с.
7. Лекции по Теории Вычислительных Процессов и Структур.
http:lib.khsu.ru245int0.html (zip)
8. Каленова Б.С. Тестовые задания по информатике Каленова Б.С., Апышева
Х.К., Жантасова Ж.З., Попова Г.В., Мухамедиева С.М., Сабыржанова А.Т.,
Сыздыкпаева А.Р., Уалханова А.Т., Шарапова М.М., Зарубин Н.П. – Усть-
Каменогорск: Издательство ВКГУ им. Аманжолова, 2004.- 94 с.
9. Светозарова Г. В.. Практикум по программированию на языке Бейсик. –
М.: Инфра, 1997г.
Қосымша әдебиеттер:
10. Информатика: Учебник Под ред. Проф. Н.В. Макаровой. 2-е изд. – М.:
Финансы и статистика, 2001.- 768 с.
11. Каймин, В.А. Информатика: Учеб.для вузов В.А Каймин; М-во образования
РФ.-3-е изд.-М.:ИНФРА-М, 2003.-272 с.
12. Степанов А.Н. Информатика: Учеб.пособие для вузов. А. Н.Степанов. -
3-е изд.- СПб.: Питер, 2003.- 608 с
13. Козырев А.А. Информатика: Учеб.для вузов А.А.Козырев. – СПб.: Изд-во
Михайлова В.А., 2002. – 511 с.
14. Альфред В. Ахо. Структуры данных и алгоритмы.: Пер. с англ. Ахо
Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Изд. Дом
Вильямс, 2001. – 384 с.: ил.
15. Могилев А.В., Пак Н.И., Хеннер Е.К. Практикум по информатике: Учебное
пособие для студентов вузов.-М., 2002.- 608 с.
16. Брукшир Дж. Информатика и выислительная техника. 7-ое изд.
Дж.Брукшир. – СПб.: Питер, 2004. – 620 с.: ил.
17. Брой М. Информатика. Основополагающее введение: В 4 ч. –М.: Диалог;
МИФИ, 1996. –Ч.1.
18. Э.З. Любимский. Программирование. Учеб. Пособие для вузов. Любимский
Э.З., Мартынюк В.В., Трифонов Н.П. – М.: Наука, 1980. – 603 с.
19. Альфред В. Ахо. Построение и анализ вычислительных алгоритмов.: Пер. с
англ. Ахо Альфред В., Джон Хопкрофт Э., Джефри Ульман Д. – М.: Мир,
1979. – 519 с.: ил.
20. Фролов Г.Д. Элементы информатики.: Учеб. Пособие для пед. ин-тов.
Г.Д. Фролов, Э.И. Кузнецов. – М.: Высш.шк., 1989. – 304 с.: ил.
2.2 Лекциялық сабақтардың тезистері:
Лекция 1. Тақырыбы: Ақпарат ұғымы. Ақпараттық үрдістер.
Ақпарат — бұл қажетті әртүрлі деректердің, мағлұматтардың, білімдердің,
хабарлардың, дағдылар мен тәжірибелердің жиынтығы. Кез келген ақпарат дұрыс
интерпретирлену, ақиқаттылық, өзектілік, толықтылық, бағалылық, анықтылық
және түсініктілік қасиеттеріне ие.
Ақпарат ақиқат, егер ол жұмыстың ақиқат жағын көрсететін болса. Ақиқат
емес ақпарат дұрыс түсінбеушілікке немесе дұрыс шешімнің қабылданбауына
әкеліп соғуы мүмкін.
Ақпарат толық, егер түсінуге және шешімдер қабылдауға жеткілікті болса.
Ақпараттың толық еместігі қабылданған шешімдердің кешігуіне, тіпті
қателердің болуына әкеліп соғады.
Ақпараттың бағалығы ақпараттың көмегімен қандай мәселелерді шешуге
болатындығында. Өзекті ақпаратты өзгерген жағдайда жұмыс істеу барысында
алуға болады.
Информатика – адам өмірінің әртүрлі салаларында ақпараттың құрылымы мен
жалпы қасиеттерін, оны іздеу, жинау, сақтау, түрлендіру және қолдану
мәселелерін зерттейтін жас ғылыми пән.
Информатиканы оқудың маңыздылығы ЭЕМ-ді қолдану мүмкіндіктері мен жұмыс
істеу принциптерін түсінуге мүмкіндік беріп қана қоймай, қоғам өмірінің
және адамдардың қатынасу кезінде ақпараттың берілу әдістері және
заңдарымен танысуға мүмкіндік береді. Оқудың күрделілігі техникалық
құрылғылардың жылдам прогресстерімен және бағдарламалық
қамтамасыздандырулармен байланысты.
Негізгі әдебиеттер: 1, 2, 3, 4.
Қосымша әдебиеттер: 11, 12
Лекция 2. Тақырып: Ақпаратты көрсету пішімдері.
Сигнал – уақыт ішінде өзгеретін физикалық үрдіс (мысалы, тізбекте
жүретін электр тогы, жарықтың таралу үрдісі). Ақпарат физикалық үрдістің,
яғни сигналдың бір немесе бірнеше параметрлерінің мәнімен беріледі.
Егер сигнал параметрі берілген аралықта кез келген аралық мән қабылдай
алатын болса (уақытқа байланысты үздіксіз функциямен анықталса), онда
сигнал үздіксіз ал мұндай сигналмен анықталған хабар да үздіксіз деп
аталады. Бұл жағдайда таратқышпен берілген ақпарат үздіксіз түріне ие
болады.
Егер сигнал параметрі берілген аралықта жеке бекітілген мәндерді
қабылдаса, онда сигнал дискретті, ал мұндай сигналмен анықталған хабар да
дискретті деп аталады. Бұл жағдайда таратқышпен берілген ақпарат дискретті
түріне ие болады. Сонымен біз ақпарат берілуінің екі негізгі түрін
(пішімін) - үздіксіз және дискретті ақпаратты анықтадық.
Санау жүйесі – сандық мәліметтерді көрсету тәсілдері мен ережелерінің
келісілген жиынтығы. Санау жүйелерінің екі түрі бар: позициялық және
позициялық емес (бейпозициялық).
Позициялық емес санау жүйелерінде беру және жазу ережелері күрделі болып
табылады. Мұндай санау жүйелерінің бірі – римдік сан жүйесі. Мысалы,
MCMXCVIII – 1998 деген сөз, мұнда M – мыңдық, C – жүздік, X – ондық, V –
бес, I – бір, т.с.с.
Позициялық санау жүйелерінде санның мәні тек қана оның құрамына кіретін
цифрлармен ғана емес, сонымен қатар цифрлардың тізбектегі орнымен
анықталады. Позициялық сан жүйесінде қолданылатын таңбалардың саны оның
негізі деп аталады, оны q әрпімен белгілейік (мысалы ондық сан жүйесінде он
таңба(цифр): 0,1,2,...,9). Санау жүйесінің таңбаларының жиынтығын оның
алфавиті деп атайды.
Негізгі әдебиеттер: 1, 2, 3, 4, 8
Қосымша әдебиеттер: 11, 12
3-лекция Тақырып: Алгоритмдер теориясына кіріспе.
Алгоритм ұғымы информатиканың ақпарат сияқты негізгі ұғымдарының бірі
болып табылады. Сондықтан алгоритм ұғымын талқылау ең қажетті болып
саналады.
Алгоpитм — кез келген алғашқы мәліметтен ( берілген алгоритм үшін мүмкін
алғашқы мәліметтердің қандай да бір жиынтығынан) басталатын және осы
алғашқы мәліметпен толық анықталатын нәтиже алуға бағытталған алгортмдік
үрдісті беретін дәл нұсқаулар тізбегі.
Бұл - алгоритм ұғымының интуитивті сипатталуы болып табылады.
Алгоритмдік үрдіс – коснтруктивті объектілерді (сөз, сан, сөз жұбы, сан
жұбы, сөйлемдер және т.б.) дискретті қадаммен түрлендіру үрдісі.
Алгоритмнің негізгі қасиеттері: дискреттілік, түсініктілік, анықтылық,
нәтижелік, көпшілік.
Алгоритмді орындаушы — бұл алгоритммен тағайындалатын әрекеттерді
орындай алатын абстрактілі немесе нақты жүйе (техникалық, биологиялық
немесе биотехникалық).
Орындаушыны орта; элементарлық әрекеттер; командалар жүйесі;
әрекеттерінің формальдығы сипаттайды. Информатикада әмбебап алгоритм
орындаушысы компьютер болып табылады.
Орындаушының командалар жүйесі – орындаушы орындай алатын барлық
командалар жиынтығы. Әрбір команда үшін қолдану шарттары берілуі (ортаның
қандай жағдайында команда орындалуы мүмкін) және команданың орындалу
нәтижелері жазылған болуы тиіс. Команданы шақырғаннан кейін орындаушы
сәйкес элементарлық әрекеттерді орындайды.
Орындаушы формальды түрде әрекет етеді, яғни есептің мазмұнына
үңілмейді, тек қана қажетті нәтиже алу үшін қатаң түрде әрекеттерді
(командаларды) орындайды. Енді алгоритм орындаушысы ұғымын қолдана отырып
алгоритм ұғымын анықтауға болады.
Алгоpитм — алдыға қойылған есептің шешіміне ақырлы қадаммен жету үшін
қажетті қимылдар тізбегінің орындаушыға түсінікті және дәл нұсқаулары.
Алгоритм іргелі ғылыми ұғым ретінде қатаң сипаттауды талап етеді, яғни
формальдауды. Алгоритм ұғымы формальдаудың келесі бағыттары белгілі:
– шекті және шексіз автоматтар теориясы (Пост, Тьюринг машиналары,
Марковтың қалыпты алгоритмдері және т.б.);
– есептелетін (рекурсивті) функциялар теориясы;
– Черчтің (-есептеуі (LISP бағдарламалау тілі).
Алгоритм ұғымын формальдаудың негізгі мақсаты: әртүрлі математикалық
есептердің алгоритмдік шешілу мәселелерін қарастыру, яғни есептің шешілуіне
әкеп соғатын алгоритм тұрғызуға бола ма деген сұраққа жауап беру.
Негізгі әдебиеттер: 1, 5
Қосымша әдебиеттер: 12, 20
4-лекция Тақырып: Алгоритмді беру тәсілдері және алгортмдерді құру
әдістері.
Практикада алгоритмдерді берудің (жазбалар) келесі тәсілдері кең
тараған:
– сөздік (табиғи тілдегі жазба);
– графикалық (графикалық символдардан тұратын бейнелер);
– псевдокодтық (шартты алгоритмдік тілде алгоритмдерді жартылай
формальданған түрде сипаттау.);
– бағдарламалық (бағдарламалау тілдеріндегі мәтіндер).
Алгоритмді берудің сөздік тәсілі мәліметтерді өңдеу кезеңдерінің
тізбегін табиғи тілде сипаттауды ұсынады.
Сөздік тәсіл кеңінен таралмаған, өйткені мұндай сипаттамалар қатаң
формальданбаған, жазбалардың көпсөзділігі кері әсер тигізеді,
көпмағыналылыққа жол береді.
Графикалық тәсілде алгоритм әрқайсысы бір немесе бірнеше әрекеттерге
сәйкес келетін, бір-бірімен байланысқан функционалдық блоктар тізбегі
түрінде бейнеленеді. Мұндай графикалық берілу алгоритм сызбасы немесе блок-
сызба деп аталады.
Псевдокод алгоритмдерді біркелкі жазуға арналған белгілеу лер және
ережелер жүйелерін ұсынады, табиғи және формальды тілдер арасында аралық
орынға ие. Псевдокодтың ортақ немесе формальды анықтамасы жоқ, сондықтан
қызметтік сөздер жиынымен және негізгі (базалық) конструкциялармен
ерекшеленетін әртүрлі псевдокодтар болуы мүмкін.
Практикада алгоритмдерді орындаушы ретінде арнайы автоматтар —
компьютерлер қолданылады. Сондықтан, компьютерде орындауға арналған
алгоритмдер оған түсінікті тілде жазылуы тиіс. Алгоритмді жазу тілі
бұйрықтарды (командаларды) талқылаусыз дәл беруі тиіс. Мұндай тіл -
бағдарламалау тілі, ал осы тілде алгортимнің жазылуы — компьютерге арналған
бағдарлама деп аталады.
Кез келген алгоритмнің логикалық құрылымы үш базалық құрылым
комбинациясы түрінде берілуі мүмкін:
тізбектік, тармақталу, цикл. Базалық құрылымдардың негізгі ерекшеліктері -
оларда бір ғана кіру мен шығудың болуы. Алгоритмдерді жеке базалық (яғни,
негізгі) элементтерден құралған құрылым ретінде беруге болады. Сондықтан
алгоритмдерді құрастыру ұстанымдарын зерттеуді осы базалық элементтерді
қарастырудан бастау қажет.
"Тізбектік" базалық құрылымы. Бірінен соң бірі жалғасып отыратын
әрекеттер тізбегінен құрылады.
"Тармақталу" базалық құрылымы. Шартты тексеру нәтижесіне (иә немесе жоқ)
байланысты алгоритм жұмысының альтернативті жолдарының бірін таңдауды
қамтамасыз етеді. Жолдардың әрқайсысы ортақ шығуға әкеледі, сондықтан
алгоритм жұмысы қандай жолдың таңдалуына қарамастан ары қарай жалғаса
береді. Тармақталу құрылымы төрт негізгі нұсқалардан тұрады: егер - онда;
егер – онда - әйтпесе; таңдау; таңдау - әйтпесе.
"Цикл" базалық құрылымы. Цикл денесі деп аталатын кейбір әрекеттер
жиынтығының бірнеше мәрте орындалуын қамтамасыз етеді.
Күрделі есептер үшін алгоритм құру кезінде декомпозициялар (жоғарыдан
төменге қарай жобалау) және синтездің (төменнен жоғарыға қарай жобалау)
қатысуымен жүйелік бағыт қолданылады. Күрделі жүйе құрылымын құру кезінде
де, алгоритмді қалыптастыру кезінде де дедуктивті және индуктивті әдістер
қолданылады. Алгоритмдерді құрудың көптеген әдістері бар, бірақ келесі
негізгілерді атап өту қажет: жеке мақсаттар әдісі (декомпозициялар); өрлеу
әдістері; шекара және тармақ әдістері; кері өңдеу әдістері; мәліметтер
құрылымына негізделген әдістер, динамикалық бағдарламалау және т.б.
әдістер.
Негізгі әдебиеттер: 1, 4, 5
Қосымша әдебиеттер: 12, 14
5-лекция Тақырып: Бағдарлама құру технологиялары және оларды жүзеге
асыру.
Есептерді компьютердің көмегімен шешу қандай да бір бөлігі компьютердің
қатысынсыз жүзеге асырылатын келесі негізгі кезеңдерден тұрады.
1. Есептің қойылуы: есеп туралы ақпараттарды жинау; есеп шартын
фоpмальдау; есепті шешудің соңғы мақсаттарын анықтау; нәтижелерді беру
пішімдерін анықтау; мәліметтерді сипаттау (олардың типін, диапазонын,
құрылымын және т.б.).
2. Есепті, моделді зерттау және талдау: бар аналогтарды талдау;
техникалық және бағдарламалық құралдарды талдау; математикалық моделді
құру; мәліметтер құрылымын құру.
3. Алгоритм құру: алгоритмді жобалау әдісін таңдау; алгоритмді беру
тәсілін таңдау (блок-сызбалар, псевдокод және т.б.); тестер және
тестілеу әдістерін таңдау; алгоритмді жобалау.
4. Бағдарламалау: бағдарламалау тілін таңдау; мәліметтерді ұйымдастыру
тәсілдерін анықтау; бағдарламалаудың таңдалған тілінде алгоритмді
жазу.
5. Тестілеу және жөндеу: синтаксистік жөндеу; семантиканы және логикалық
құрылымды жөндеу; тестілік есептеулер және тестілеу нәтижесін талдау;
бағдарламаның жетілуі.
6. Есепті шешу нәтижелерін талдау және қажет жағдайда 2-5 кезеңдерді
қайталай отырып математикалық моделді дәлдеу.
7. Бағдарламаны сүйемелдеу: нақты есептер шешу үшін бағдарламаны аяқтау;
шешілген есепке, алгоритмге, бағдарламаға, тестер жинағына, қолдануға
құжаттаманың құрастырылуы.
Бағдарламаның верификациялануы (verification) – бағдарлама жұмысының
дәлдігі және оның басқа да есептер шешу инструменті ретінде мүмкіндіктері.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 19
6-лекция Тақырып: Бағдарламалау әдістемелері.
Бағдарламалаудың келесі парадигмалары бар: процедуралық немесе
императивтік; декларативтік; функционалдық; объектілі-бағытталған.
Бағдарламалау әдістемелеріне дұрыстық, сенімділік, түсініктілік, тиімділік
және т.б. қасиеттерге ие жақсы бағдарламаларды құру әдістеріне байланысты
сұрақтар жиыны жатады. Бағдарламалау әдістемелері: операциальды-
бағытталған; процедуралы-бағытталған; құрылымды; объектілі-бағытталған;
декларативті (функциональды және логикалы); параллельді.
Құрылымды бағдарламалау негізінде кез келген есепті шешу үшін тек
тізбектік, тармақталу, цикл құрылымдарын ғана қолдануға болады деген
теорема (бағдарламалау теориясында дәлелденген) жатыр. Құрылымдық бағыттың
маңызды ерекшеліктері: нақты есеп шарттарына сәйкес базалық құрылымдардың
суперпозицияларын құрастыру мүмкіндіктері; модульдік; декомпозициялау
мүмкіндіктері, яғни бағдарламаны жоғарыдан төмен жобалау.
Модуль – бұл бағдарламаның жеке бөлігі ретінде құралған логикалық
байланысты операциялар тізбегі.
Бағдарламалық жасақтамалар құру әдістемелерін жасау БЖ жобалау
мәселелерінің негізгі міндеттерінің бірі болып табылады. Бағдарламаны
жобалаудың белгілі әдістемелері төменнен жоғары қарай және жоғарыдан төмен
қарай жобалау болып табыладыя. Төменнен жоғары қарай жобалау – күрделі
есептерді шешу үшін әрқайсысы негізгі есепке бағынатын және жеке модульдік
процедуралармен жүзеге асатын қарапайым бағыныңқы есептер иерархиясы арқылы
құрастырылатын жобалау. Жоғарыдан төменге қарай жобалану – жүйені құрудың
жобалануы жүйенің жеке есептерін анықтаудан басталады және осы есептердің
шешілуі абстрактілі құралдар ретінде күрделі есептерде қалай қолданылуы
талқыланады.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 19
7-лекция Тақырып: Алгоритмдер күрделілігін талдау және бағалау.
Алгоритмді құрған кезде екі ұғымды ескерген жөн: ол – алгоритмнің
тиімділігі мен дұрыстығы. Жалпы алып қарағанда, тиімділік ұғымы алгоритм
жұмысына қажетті барлық есептеу ресурстарвмен байланысты. Тиімділік
алгоритмнің шекті уақытта ғана емес, мүмкін шекті уақытта орындалатындығын
көрсетеді. Алгоритм мен сәйкес бағдарламаның дұрыстығын тексеру өте
маңызды, ал тексерудің тиімді әдістерін іздеу есептеу техникасында өзекті
мәселелер болып табылады. Алгоритмнің дұрыстығын тексерудегі ізденістердің
бір бағыты – формальды логиканың әдістерін қолдану. Бұл жолдың негізгі
ұстанымы: дұрыстықты тексеру үрдісін формальдау процедурасына әкелу
интуитивті болжауларға сүйенген қателіктерден құтқарады.
Алгоритмнің тағы бір негізгі мінездемелерінің бірі – оның күрделілігі.
Әдетте алгоритмдер күрделілігінің дәрежесі оперативті жады және
процессорлық уақыт сияқты қолданылатын компьютер ресурстарының көлемімен
бағаланады. Осыған байланысты алгоритмнің уақыт бойынша күрделілігі және
көлем бойынша күрделілігі анықталады. Көп жағдайда уақыт бойынша шектеулер
басым рөл атқаратындықтан уақыт бойынша күрделілік маңызды болып
есептеледі. Уақыт бойынша күрделілік орындалатын операциялар санымен
анықталады, алғашқы мәліметтерге тәуелді (олардың көлеміне және шамасына)
Алгоритмнің уақыт бойынша күрделілігі – алгоритмнің есепті шешуіне
жұмсаған уақыты, ол есептің өлшемі n-ге тәуелді функция. Бұл күрделіліктің
есептің өлшемі өсудегі шектік мінездемесі асимптотикалық уақыт бойынша
күрделілік деп аталады. Көлем бойынша күрделілік және асимптотикалық көлем
бойынша күрделіліктер де осыған сәйкес анықталады Мысалы, егер алгоритм n
өлшемді енгізулерді cn2 уақытында, мұнда c – қандай да бір тұрақты, өңдесе,
онда уақыт бойынша күрделілік ((n2) деп айтады. Алгоритмдерді талдауда ең
жақсы, ең жаман және орта жағдайлар қарастырылады, сәйкес бағалаулар
беріледі. Алгоритмдерді құру мен талдауда олардың тиімділігін салыстыру
үшін теоретиктермен қарапайым жол ұсынылған: полиномиалдық және
экспоненциалдық алгоритмдер арасындағы айырмашылық.
Егер алгоритмнің уақыт бойынша күрделілігі есеп өлшемі n-нің
полиномиалдық функциясы түрінде өрнектелсе, онда алгоритм полномиалдық деп
аталады. Алгоритмнің уақыт бойынша күрделілігі мұндай бағалуға бағынбаса,
онда ол экспоненциалдық деп аталады. Есепті шешудің қарапайым алгоритмінің
күрделілігі осы есептің күрделілігі деп аталады. Егер есепті шешудің уақыт
бойынша күрделілігі ((f(n))-ге тең алгоритмі бар болса, онда есептің
күрделілігі ((f(n))-ға тең, мұнда f(n) – қандай да бір n-ге тәулді
функция,. Сондай-ақ бұл есепті O(f(n)) класының есебі деп атайды. Егер есеп
O(f(n)) класында жататын болса, мұнда f(n) –полином, немесе бұл өрнек
полиноммен шектелген, онда ол полиномиалдық деп аталады,. Барлық
полиномиалдық есептердің жиынтығы P (тізімде ізду, сұрыптау есептері және
т.б.) деп белгіленеді. Егер есеп үшін полиномиалдық алгоритм құру мүмкін
емес болса, яғни P-ға тиісті емес, онда ол қиын шешілетін есеп деп аталады.
Детерминделмеген алгоритмнің көмегімен полиномиалдық уақыт көлемінде
шешілетін есепті детерминделмеген полиномиалдық есеп немесе NP-есеп (
коммивояжер есебі және т.б.) деп атайды. NP-есептер класы NP деп
белгіленеді. Барлық P есептері NP-да жатады, ал кері тұжырым жоқ. NP класы
P класымен сәйкес пе деген сұрақты зерттеу NP класында жаңа есептер класын
- NP-толық есептер деп аталатын класты ашты. Сөйтіп есептер шешілетін
(алгоритмдік шешімі бар) и шешілмейтін (алгоритмдік шешімдері жоқ)
болатындығы анықталды. Сонымен қатар шешілетін есептер класында екі ішкі
класстар: –полиномиалдық есептер және полиномиалдық емес есептер бар.
Жіктелмейтін жұмбақ NP-есептер де (шифрлеу есептері және т.б.) бар.
Негізгі әдебиеттер: 1, 4, 5
Қосымша әдебиеттер: 12
8-лекция Тақырып: Мәліметтер құрылымдары және олардың ұйымдастырылуы.
Мәліметтер – бұл белгілі бір пішімде берілген және ары қарай
пайдалануға арналған қандайда бір жүйені, құбылысты, үрдісті немесе объекті
сипаттайтын мағлұматтар. Ақпарат және мәліметтер ұғымдарының арасындағы
арақатынас тұрғысынан алып қарағанда: мәліметтер – бұл ақпараттың мазмұнын
көрсететін нақты пішім; мәліметтер – бұл пайдаланушы үшін маңызды және
онымен қандай да бір есептерді шешуге қолданылады. Мәліметтерге бірнеше
классификациялық мінездемелер меншіктеледі. Олардың ішіндегі ең маңыздысы
мәліметтер типі болып табылады. Мәліметтер типі мүмкін мәндер жиынын;
олардың өңделу ережелерін (түрлендіру); сақтау кезінде ОСҚ және ССҚ-да
олардың орналасу ретін; оларға қатынау ретін анықтайды. Негізгі мәліметтер
типтері: стандарттық, қарапайым, шектелген, күрделі құрылымдық және т.б.
Мәліметтер типтерінің концепциясы пайдаланушыға мәліметтерді беру, сақтау,
қолдану есептерін тиімді шешуде көп мүмкіндіктер береді; мәліметтердің
жинақтылығына әсер етеді. Сонымен қатар мәліметтер элементарлық (қарапайым)
құрылымданбаған және құрылымданған (күрделі) болып жіктеледі. Элементарлық
мәліметтерге символдар, сандар және логикалық мәліметтер жатады, олардың
әрқайсысы бір мәнмен және атпен анықталады. Мәліметтерді және олардың
арасындағы байланыстарды біріктіретін ақпараттық массивті құрылымданған
мәліметтер деп атайды. Біріктірілетін қарапайым мәліметтердің тізімі,
олардың мінездемелері, сонымен қатар арасындағы байланыстардың
ерекшеліктері мәліметтер құрылымын анықтайды. Күрделі мәліметтер де мәнімен
және атымен анықталады. Өңдеу үрдісінде мәндерінің өзгеруіне байланысты
(қарапайым және құрылымдық мәліметтер үшін) мәліметтерді айнымалы және
тұрақты деп бөледі. Өңдеудің қай кезеңінде қолданылуына байланысты
мәліметтерді алғашқы(енетін), аралық, қорытынды(шығатын) мәліметтер деп
бөледі.
Сақтауда және өңдеуде мәліметтерді беру үш негізгі есепті шешуді қажет
етеді: элементарлық мәліметтерді беру әдістерін анықтау; мәліметтердің
құрылымға бірігу әдістерін анықтау; мәліметтердің материалдық тасуышта
орналасуын анықтау. Мәліметтерді берудің үш деңгейін анықтайды:
концептуалдық, логикалық және физикалық. Концептуалдық деңгейде ақпараттық
массивтің жалпы құрылымы анықталады, ол мәліметтер моделі деп аталады.
Мәліметтер моделдерінің негізгілері: иерархиялық, желілік, реляциялық,
объектілі-бағытталған.
Қатынастарының мінездемелеріне байланысты мәліметтер құрылымдарының
бірнеше жіктелу белгілерін анықтауға болады: мәліметтердің реттері бойынша
– реттелген және реттелмеген, қатынастарының мінездемелері бойынша –
сызықтық және сызықтық емес, құрылымдағы мәліметтер типтеріне байланысты –
біртекті және біртексіз, мәліметтерге қатынау әдістеріне байланысты – тура
жететін және тізбектік жететін, ақпараттық массивтің өлшемінің өзгеру
мүмкіндігіне байланысты – статикалық және динамикалық.
Негізгі күрделі құрылымдар: массив, жиын, кезек, стек, ағаш (екілік
ағаш), граф, тізімдер (логикалық жазба). Мәліметтерді ұйымдастыруда үш
типті қолданады: сызықтық(тізбектік), кестелік, иерархиялық.
Негізгі әдебиеттер: 1, 4, 5,
Қосымша әдебиеттер: 12, 20
9-лекция Тақырып: Арифметика алгоритмдері, көпмүшеліктерді есептеу.
Сандық есептеулер бүтін сандар жиынында немесе нақты сандар жиынында
жүргізілуі мүмкін. ЭЕМ-де бүтін сандық арифметика нақты сандармен
арифметкамен салыстырғанда үш маңызды артықшылыққа ие: бүтін сандар әрқашан
да өздерінің дәл мәндерімен беріледі; бүтін сандық арифметиканың
операциялары дәл нәтижелер береді; бүтін сандық арифметиканың операциялары
жылдамырақ орындалады. Бүтін санды мәліметтердің кемшілігі олардың мүмкін
мәндері диапазонының тарлығы.
Нақты сандар жадта жуық мәндерімен сақталады, яғни өздерінде қателіктер
сақтайды, бұл қателіктер машиналық жуықтау қателіктері деп аталады.
Реккуренттік тізбектерді есептеулерді бағдарламалау келесі есептер
түрлерімен байланысты: тізбектің берілген (n-ші) элементін есептеу,
тізбектің белгілі бір бөлігін математикалық өңдеу (мысалы, қосындыны
есептеу); тізбектің берілген аралығында белгілі шарттарды қанағаттандыратын
элементтер санын есептеу; тізбек элементтерінің берілген санын есептеп
және жадта сақтау; белгілі шартты қанағаттандыратын тізбектің алғашқы
элементін анықтау.
Негізгі әдебиеттер: 1, 4, 5, 8
Қосымша әдебиеттер: 12, 14, 13, 20
10-лекция Тақырып: Сұрыптау алгоритмдері. Массивтерді сұрыптау (ішкі
сұрыптау).
Алгоритмдерді әдетте сандық (есептеу) және сандық емес (есептеусіз) деп
бөледі. Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге
арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен
жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау
және іздеу табылады. Объектілердің берілген тізбегін қандай да бір
анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды.
Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді
жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді,
сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау
алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау
алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар
массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен
анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті
элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі
орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы
мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив.
Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды
пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды
жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері
бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау (көбікше
әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі
кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау
(пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау).
Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,..., ai-1
және кіретін тізбекке ai,..., an бөлінеді, содан кейін әрбір қадамда, i=2
бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін
алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең
кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын
ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше
сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең
жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең
жақсысы болып табылады.
Негізгі әдебиеттер: 1, 2-6.
Қосымша әдебиеттер: 13-15, 18.
11-лекция Тақырып: Сұрыптау алгоритмдері. Файлдарды сұрыптау (сыртқы
сұрыптау).
Сыртқы сұрыптау алгоритмдері – бұл сыртқы жадтағы мәліметтерді сұрыптау
алгоритмдері, мұнда қолайлы құрылым - файл . Негізгі ерекшелігі - өңдеудің
әрбір уақыт мезетінде тек бір ғана элементі(компонента) жетімді. Файлдарды
сұрыптау әдістерінің көпшілігі (доступных в данный момент) тоғыстыру
процедурасына негізделеді. Тоғыстыру – екі (немесе одан да көп) тізбектерді
бір тізбекке біріктіру, ол тізбек элементтері қайталанатын таңдау арқылы
реттелген . Қарапайым тоғыстыру келесі қадамдардан тұрады:
1. a тізбегі b және c екі жартыға бөлінеді;
2. b және c тізбектері жеке элементтерді реттелген жұптарға біріктіру
арқылы тоғыстырылады;
3. Алынған тізбек a деп аталады, содан кейін 1 және 2 қадамдар
қайталанады; бұл жолы реттелген жұптар реттелген төрттіктерге
тоғыстырылады;
4. Алдыңғы қадамдар қайталады; төрттіктер сегіздіктерге тоғыстырылады,
барлық үрдіс бүкіл тізбек реттелгенше жалғасады; тоғыстырылатын жарты
тізбектер ұзындықтары екі еселеніп отырады.
Табиғи тоғыстыру – бұл әр тоғыстыруда мүмкін ең ұзын ішкі тізбектер
біріктірілетін тоғыстыру..
Негізгі ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz