3. Элементы теории кодирования Основные определения и понятия темы

Алфавит, слово, длина слова, кодирующая функция, декодирующая функция, сообщение, код сообщения, m-ичное кодирование, взаимно-однозначное кодирование, алфавитное кодирование, элементарный код, алфавитный код, префикс слова, постфикс слова, префиксная схема кодирования, кодирование с минимальной избыточностью, самокорректирующиеся коды..

Основные теоремы и утверждения темы

Алгоритм распознавания взаимной однозначности декодирования, теорема редукции, алгоритм построения кода с минимальной избыточностью (алгоритм Хаффмена), алгоритм Фано, алгоритм построения и декодирования кодов Хемминга.

Рекомендуемая литература

1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

2. Левенштейн В. И. Элементы теории кодирования. – В. сб. Дискретная математика и математическая кибернетика. Т. 1. / Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Наука, 1974. – С. 207-305.

Задание 3.1.Выяснить, является ли кодирование со схемой взаимно однозначным. Если нет, то указать слово, декодируемое неоднозначно:

1. : ,,,,,,;

2. : ,,,,,,;

3. : ,,,,,;

4. : ,,,,,;

5. : ,,,,,,;

6. : ,,,,;

7. : ,,,,,;

8. : ,,,,,,;

9. 

10. ;

11. ;

12. ;

13. 

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.2. Построить схему оптимального префиксного алфавитного кодирования по методу Хаффмена для распределения вероятностей появления букв алфавитав сообщении при-ичном кодировании.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.3.Дано распределение вероятностей появления букв алфавитав сообщении. Построить схему алфавитного кодирования по алгоритму Фано.

1. ;

2. ;

3. ;

4. ;

5. 

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.4.Построить по методу Хэмминга код сообщения .

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 3.5. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга для сообщения . Было получено кодовое слово. Восстановить слово.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

4. Элементы комбинаторного анализа Основные определения и понятия темы

Сочетания, размещения и перестановки без повторений, сочетания, размещения и перестановки с повторениями.

Основные теоремы и утверждения темы

Правило суммы и правило произведения, формулы для числа сочетаний, размещений и перестановок без повторений, формулы для числа сочетаний, размещений и перестановок с повторениями, бином Ньютона, полиномиальная теорема.

Рекомендуемая литература

1. Виленкин Н.Я, Виленкин А.Н., Виленкин П.А. Комбинаторика. – М: МЦНМО, 2006 г.

2. В.В. Тишин Дискретная математика в примерах и задачах. – СПб: БХВ-Петербург, 2008.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

Задание 4.1. Решить комбинаторные задачи:

1. Сколькими способами можно нанизать на нить 3 красных, 4 желтых и 2 зеленых бусины?

2. На железнодорожной станции имеется 5 светофоров. Сколько может быть дано различных комбинаций сигналов, если каждый светофор имеет два состояния «красный» и «зеленый»?

3. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен?

2. 1. Сколькими способами можно выбрать из 10 кандидатов трех человек на три различные должности?

   2. Сколькими способами можно расставить следующие шахматные фигуры король, ферзь, 2 ладьи, 2 слона и 2 коня на одной линии шахматной доски, состоящей из 8 клеток?

   3. Пять девушек и трое юношей играют в городки. Сколькими способами они могут разбиться на две команды по четыре человека в команде, если в каждой команде должен быть хотя бы один юноша?

3. 1. Сколько различных слов можно составить, вставляя пропущенные буквы в слово «ро**на», если можно использовать 32 буквы русского алфавита?

   2. Сколькими способами можно выбрать из 10 кандидатов трех человек на три одинаковые должности?

   3. Сколькими способами можно выбрать из 16 лошадей шестерку для запряжки так, чтобы в нее вошли 3 лошади из шестерки AA′BB′CC′, но не вошли ни одна из пар AA′, BB′, CC′ ?

4. 1. В магазине имеется 15 различных видов коробок конфет. Сколько можно сделать покупок, состоящих из 3-х коробок конфет?

   2. Каким числом способов можно рассадить 12 гостей на имеющихся 12 различных стульях?

   3. Сколько различных четырехзначных нечетных чисел можно составить из цифр 1, 2, 3, 4, 5?

5. 1. Имеется 10 символов для составления двухбуквенного кода электронного документа. Сколько кодов можно составить из этих символов?

   2. Сколькими способами можно распределить 10 путевок в санаторий между 90 работниками предприятия?

   3. Сколькими способами можно переставить буквы слова «опоссум» так, чтобы буква «п» шла непосредственно после буквы «о»?

6. 1. Сколько различных слов можно образовать, переставляя буквы слова «банан»?

   2. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов?

   3. Из колоды в 52 карты двое выбирают по 4 карты каждый. Сколько существует различных способов выбора? Во скольких случаях один из них получит 4 туза, а другой – 4 короля?

7.1. На предприятии работают 30 сотрудников. В командировку необходимо отправить 4 человека. Сколькими способами это можно сделать?

7.2. Номер удостоверения должен состоять из 8 цифр. Сколько таких номеров можно составить?

7.3. Сколькими способами можно переставить буквы слова «перешеек» так, чтобы 4 буквы «е» не шли подряд?

8.1. Сколькими способами можно выбрать три гласные буквы из слова «теория»?

8.2. Сколько различных чисел можно получить, переставляя цифры числа 1123353?

8.3. Сколькими способами можно рассадить пять человек А, В, С, D и Е на пяти местах, если А и Е не должны сидеть рядом?

9.1.В видеопрокате имеется 80 видеокассет. Сколькими способами можно взять в видеопрокате 4 кассеты?

9.2. Сколькими способами можно составить список 10 факультетов ВУЗа?

9.3. Сколько номерных знаков для автомобилей можно составить, если в номере используется четырехзначное число, в котором первые три цифры не нули, и трехбуквенное слово из 30 букв русского алфавита?

10.1. Сколькими способами можно составить набор из 25 карандашей, если имеются карандаши 10 цветов?

10.2. Сколькими способами можно распределить золотую, серебряную и бронзовую медали между 10 участниками соревнований?

10.3. На собрании должны выступить 5 человек А, Б, В, Г и Д. Сколькими способами можно расположить их в списке ораторов при условии, что Б не должен выступать раньше А?

11. 1. Сколькими способами можно составить новогодний подарок, который должен содержать 100 конфет, если в наличии имеется 15 сортов конфет?

    2. На железнодорожной станции имеется 6 светофоров. Сколько может быть дано различных комбинаций сигналов, если каждый светофор имеет три состояния «красный», «желтый» и «зеленый»?

    3. Сколькими способами можно переставить буквы слова «фацетия» так, чтобы не менялся порядок гласных букв?

12.

12.1. Сколькими способами можно разложить в два кармана девять монет различного достоинства?

12.2. В ящике 5 красных и 4 зеленых яблока. Сколькими способами можно выбрать три яблока из ящика?

12.3. Сколькими способами можно переставить буквы слова «параллелизм» так, чтобы не менялся порядок гласных букв?

13.

13.1. Восемь мешков постельного белья доставляют на пять этажей гостиницы. Сколькими способами это можно сделать?

13.2. Сколькими способами можно купить пять обложек для книг в магазине, если в нем имеются обложки трех видов?

13.3. Сколькими способами можно переставить буквы слова «логарифм» так, чтобы второе, четвертое и шестое места были заняты согласными буквами?

14.

14.1. Сколько трехзначных чисел можно составить из нечетных цифр, если каждую цифру можно использовать не белее одного раза?

14.2. На предприятии работает 30 сотрудников. В командировку необходимо направить 4 человек. Сколькими способами это можно сделать?

14.3. Сколькими способами можно переставить буквы слова «кофеварка» так, чтобы гласные и согласные буквы чередовались?

15.

15.1. Сколькими способами можно вытащить две карты пиковой масти из колоды в 36 карт?

15.2. Номер удостоверения должен состоять из 10 цифр. Сколько таких номеров можно составить?

15.3. Сколько четырехзначных чисел, составленных из нечетных цифр, содержит цифру 3 (цифры в числах не повторяются)?

16.

16.1. Сколько различных слов можно образовать, переставляя буквы слова «студент»?

16.2. Из 2 математиков и 10 экономистов должна быть составлена комиссия в составе 8 человек. Сколькими способами это можно сделать?

16.3. Сколькими способами можно расположить группу из 10 человек в ряд так, чтобы между двумя студентами А и Б оказалось два человека?

17.

17.1. Сколькими способами можно составить расписание занятий на понедельник, если должно быть по одному уроку математики, истории, информатики, философии и психологии?

17.2. Сколько можно получить различных пятизначных чисел, вставляя пропущенные цифры в число 76**9?

17.3. Акционерное собрание компании выбирает из 50 человек президента компании, председателя совета директоров и 10 членов совета. Сколькими способами это можно сделать?

18.

18.1. Предложены три билета в различные театры. Сколькими способами они могут быть распределены между 25 студентами, если каждый из них может получить только один билет?

18.2. Сколькими способами можно расположить на полке 10 томов энциклопедии?

18.3. Сколько существует семизначных номеров телефонов, в первых трех цифрах которых не встречаются цифры 0 и 9?

19.

19.1. В селении 1000 жителей. Докажите, что по крайней мере двое из них имеют одинаковые инициалы.

19.2. В правление избрано 9 человек. Из них надо выбрать председателя, заместителя председателя и секретаря. Сколькими способами это можно сделать?

19.3. В купе железнодорожного вагона имеется два противоположных дивана по пять мест в каждом. Из 10 пассажиров четверо желают сидеть по ходу движения поезда, трое – против движения, остальным троим безразлично, как сидеть. Сколькими способами могут разместиться пассажиры?

20.

20.1. Во скольких девятизначных числах все цифры различны?

20.2. Сколько различных слов можно составить, переставляя буквы слова «информатика»?

20.3. Сколькими способами можно выбрать из натуральных чисел от 1 до 30 три числа так, чтобы их сумма была четной?

	a	b	n
11		3	13
12	4		10
13		2,5	21
14	3		18
15		2,3	17
16		2,5	11
17	3,5		10
18		3,3	13
19		2,8	15
20	2,8		19

Задание 4.2. Найти наибольший член разложения бинома .

	a	b	n
1		3	17
2		10	17
3		2	13
4	3		12
5		3	15
6	3		19
7		4	14
8	3		13
9		3	12
10	4		11

Задание 4.3. Найти ииз пропорции:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .

Задание 4.4. Найти коэффициент при в разложении данного выраженияпо полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. .