Методы программирования. Кулаков Ю.В - 4 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

ВВЕДЕНИЕ
Целью дисциплины "Методы программирования" являются обучение студентов принципам построения и
анализа алгоритмов, развитие логического мышления, формирование научного мировоззрения и привитие
склонности к творчеству. При изучении этого курса используются знания, полученные студентами по дисцип-
линам "Математический анализ", "Теория вероятностей" и "Языки программирования высокого уровня". Зна-
ния и практические навыки, полученные в курсе "Методы программирования", используются обучаемыми в
научных дисциплинах, а также при выполнении курсовых и дипломных работ.
Задачей дисциплины "Методы программирования" является преподавание основ: структур данных; оценки
сложности алгоритмов; алгоритмов сортировки; алгоритмов поиска; алгоритмов на графах; алгоритмов генерации
случайных последовательностей; алгоритмов генерации подстановок.
В результате изучения дисциплины студенты должны иметь представление: о способах оценки сложно-
сти работы алгоритмов, о возможности модификации алгоритмов с учетом конкретных практических задач;
знать: принципы, лежащие в основе алгоритмов сортировки и поиска информации, принципы хранения и об-
работки информации в алгоритмах сортировки, поиска и алгоритмах на графах, методы генерации случайных
последовательностей и подстановок; уметь: формулировать задачу и использовать для ее решения известные
методы, применять полученные знания к различным предметным областям, реализовывать алгоритмы на язы-
ках программирования высокого уровня, выбирая структуры данных для хранения информации; иметь навыки:
написания и отладки программ, реализующих алгоритмы сортировки, поиска и алгоритмы на графах, получе-
ния эмпирических оценок трудоемкости алгоритма.
Учебным планом на изучение дисциплины отводится 200 часов, из которых примерно половину составля-
ют аудиторные занятия, а остальное время занимает самостоятельная работа студентов. В процессе обучения
планируется проведение четырех контрольных работ. Дисциплина изучается студентами на протяжении двух
семестров, в каждом из которых выполняется одно домашнее задание; в конце первого семестра предусмотрен
зачет, а в конце второго – экзамен.
Т е м а 1. СТРУКТУРЫ ДАННЫХ
Программа
1.1. Линейные информационные структуры
Стеки, очереди и деки. Последовательное распределение памяти. Связанное распределение памяти. Цик-
лические списки. Списки с двумя связями. Массивы и ортогональные списки.
1.2. Деревья
Прохождение бинарных деревьев. Представление деревьев в виде бинарных деревьев. Другие представле-
ния деревьев.
Методические указания
1.1. Линейные информационные структуры
Начните изучение информационных структур с определения понятий: информационной структуры,
структурных отношений, списка, узла списка, указателя (связи) узла списка, пустой связи, переменной связи.
Усвойте понятие такой информационной структуры, которая называется линейным списком. Установите
перечень операций, которые могут выполняться с линейными списками. Рассмотрите наиболее часто встре-
чающиеся линейные списки: стеки, очереди и деки. Проанализируйте общие свойства и принципиальные отли-
чия этих списков.
Познакомьтесь с последовательным распределением памяти при хранении линейных списков и понятием
базового адреса. Оцените удобство последовательного распределения при работе со стеком. Рассмотрите опе-
рации включения элемента в стек, а также исключения элемента из стека. Изучите некоторые ухищрения, необ-
ходимые для последовательного представления очереди. Рассмотрите операции включения элемента в очередь,
а также исключения элемента из очереди. Уделите внимание проблеме выхода очереди за пределы отведенной для
нее памяти и решению этой проблемы "замыканием" очереди в кольцо. Рассмотрите операции включения элемен-
та в стек и в очередь, а также исключения элемента из стека и очереди с учетом возникающих ситуаций: нехватка
и переполнение.
Оцените ситуацию в памяти, когда некоторая программа работает не с единственным списком, а с не-
сколькими списками, размер каждого из которых динамически изменяется. Рассмотрите случай очень хорошего
сосуществования двух последовательных списков переменного размера, если им позволено расти навстречу
друг другу. Убедитесь в том, что нет способа, который позволяет хранить три или более трех списков перемен-
ного размера так, чтобы переполнение возникало, когда суммарный размер всех списков превышает отведен-
ную для них область памяти, и "нижний" элемент каждого списка имеет фиксированный адрес. Рассмотрите

Страницы