Программа дисциплины «Информатика и программирование»

Вид материала

Программа дисциплины

Содержание Задачи к теме «Формальные языки и грамматики» Задачи по теме «Рекурсия» (и «Формальные языки») Задания по теме «Линейные списки» Создание списков Обработка и преобразование списков

Подобный материал:

• Программа дисциплины "Программирование" для направления, 488.76kb.
• Программа дисциплины по кафедре Прикладная математика т информатика алгоритмические, 564.02kb.
• Программа дисциплины «Введение в программирование»  для направления 080700 «Бизнес-информатика», 101.22kb.
• Рабочая программа дисциплины «Информатика и программирование» Направление подготовки, 282.17kb.
• Программа учебной дисциплины «Информатика и программирование» Программа дисциплины, 135.24kb.
• Рабочая программа для направления (специальности), 175.95kb.
• Программа дисциплины Информатика и программирование для направления 080700 «Бизнес-информатика», 272.37kb.
• Рабочая программа дисциплины информатика и программирование ен., 337.93kb.
• Рабочая программа дисциплины информатика направление ооп, 210.09kb.
• Рабочая программа по дисциплине "алгоритмизация и программирование" для специальности, 140.41kb.

Задачи к теме «Формальные языки и грамматики»

1. Постройте синтаксическую диаграмму, описывающую идентификаторы, длиной не более четырех символов.

2. Постройте металингвистическую формулу, описывающую целые числа со знаком, включающие не более 5 цифр (используйте металингвистические формулы показателем кратности).

3. Сколько слов в языке, грамматика которого задается правилами:

1) S ::= DBC

2) B ::= aCb

3) C ::= b | 1 | a

4) D ::= a | 0

4. Сколько слов порождает следующая металингвистическая формула:

10 | 110 | 101[1 | 0 | 01 | 000]0

5. Расширим металингвистические формулы показателем кратности: конкатенацию n экземпляров цепочки  будем записывать в виде ⁿ . Сколько различных слов задает формула

0011³0⁴ [1 | 10]ⁿ | 0ⁿ 1ⁿ | [1ⁿ | 005]ⁿ

6. Две формулы назовем эквивалентными, если они порождают одно и то же множество слов. Являются ли следующие формулы эквивалентными?

F1 = 00 | 11 | {0 | 01}; F2 = {10 | 0}

7. Описать пересечение и объединение множеств цепочек, порождаемых следующими двумя формулами:

F3 = 00 | 111 | {0 | 01}; F4 = {10 | 0}²

Задачи по теме «Рекурсия» (и «Формальные языки»)

1. Нарисовать дерево вызовов процедур при синтаксическом анализе выражения

S+T* (6+d*e)*f–q*h+8

2. Нарисовать дерево вызовов процедур при синтаксическом анализе выражения

(((5))+(((4) – s + d)) + 3)


Приложение 4


Примерный перечень задач по теме «Рекурсивные типы данных»

Задания по теме «Линейные списки»¹

Создание списков

1. Напишите процедуру создания линейного списка, в информационные поля элементов которого последовательно заносятся номера с 1 до N (N водится с клавиатуры в главной программе). Рассмотрите два варианта процедуры:
   
   1. первый включенный в список элемент, имеющий номер 1, оказывается в хвосте списка (последним);
      
   2. первый включенный в список элемент, имеющий номер 1, оказывается в голове списка (первым).
      
2. Напишите рекурсивную процедуру создания линейного списка, в информационные поля элементов которого последовательно заносятся номера с 1 до N (N водится с клавиатуры в главной программе и передается в процедуру в качестве параметра). Рассмотрите два варианта процедуры, как и в предыдущем задании.
   
3. Напишите процедуру создания линейного списка, в информационные поля элементов которого заносятся числа, считываемые из файла (файл может оказаться пустым). Имя файла вводится с клавиатуры в главной программе и передается в процедуру в качестве параметра. Рассмотрите следующие варианты создания списка:
   
   1. первый включенный в список элемент оказывается в хвосте списка (последним);
      
   2. первый включенный в список элемент оказывается в голове списка (первым);
      
   3. элементы включаются в список в порядке возрастания: в информационном поле первого элемента списка должно быть записано минимальное значение, а последнего элемента – максимальное;
      
   4. элементы, содержащие отрицательные значения, заносятся всегда в конец списка, а положительные – в начало (в порядке считывания из файла), нулевые – между положительными и отрицательными.
      

Перепишите все процедуры, написанные при выполнении заданий 1 3, для создания:

• циклического списка и
  
• двунаправленного списка.
  

Обработка и преобразование списков

4. В программе построен линейный список. Напишите функцию подсчета количества его элементов (рекурсивный и нерекурсивный варианты).
   
5. В программе построен линейный список. Напишите функцию подсчета суммы всех значений, занесенных в информационные поля его элементов (рекурсивный и нерекурсивный варианты).
   
6. В программе построен линейный список. Напишите процедуру подсчета двух сумм: всех положительных и всех отрицательных значений, записанных в информационные поля элементов списка
   
7. В программе построен линейный список. Напишите функцию подсчета разности между суммами всех четных и всех нечетных значений, записанных в информационные поля элементов списка.
   
8. В программе построен линейный список. Напишите процедуру, создающую два новых линейных списка:
   
   1. список, включающий все положительные значения из элементов исходного списка, и список, включающий все отрицательные значение из элементов исходного списка; при включении элементов в новые списки, они удаляются из исходного списка; например:
      

2. список, включающий элементы, ссылающиеся на элементы исходного списка, содержащие в информационных полях положительные значения, и список, включающий элементы, ссылающиеся на элементы исходного списка, содержащие в информационных полях отрицательные значения.
   

9. В программе построен линейный список. Напишите итерационную и рекурсивную процедуры «обращения» списка – создания нового списка, включающего элементы, содержащие те же значения в информационных полях, что и элементы исходного списка, но в обратном порядке (первый элемент исходного списка должен стать последним, второй – предпоследним и т.д., последний – первым).
   
10. В программе построен линейный список. Напишите итерационную и рекурсивную процедуры уничтожения списка.
    
11. В программе построен линейный список. Напишите итерационную и рекурсивную процедуры удаления из списка элементов с повторяющимися в информационных полях значениями.
    

Перепишите все процедуры, написанные при выполнении заданий 4 7, 10, 11 для обработки:

• циклического списка и
  
• двунаправленного списка.